Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

learn more… | top users | synonyms

1
vote
0answers
22 views

A Markov Chain Problem.(Change the color of ball)

There are $n$ different color balls in a box. Take two balls in turns, and change color of the second ball to the first. (This is one operation). Let $k$ be the (random) number of operations needed to ...
0
votes
0answers
14 views

Dining philosophers using markov chains

We have 5 philosophers sitting at a table, where between each pair of philosophers is a single chopstick. They alternatively think and eat. When they want to eat, they pick up the chopsticks either ...
-1
votes
0answers
12 views

Prove this is markov chain [on hold]

Let $Y_i = i$ with probability $p_i$. Let $X_i = max[Y_i , Y_i-1, ...]. $ We have $i={0,1,2,3,4,...}. $ Prove that $X_i$ is a Markov chain and write down its matrix.
1
vote
1answer
21 views

Markov property for discrete Markov chains. A question about “adjacent random variables”

Consider a discrete Markov chain (with values in $\mathbb R$) $\{X_n:\, n\in\mathbb N\}$: namely the state space $S$ is a countable subset of $\mathbb R$ and the random variables are $X_0, X_1, ...
0
votes
1answer
25 views

M/G/1 queue has embedded Markov chain

I tried to prove that the M/G/1 queue has an embedded discrete-time Markov chain. But I'm not sure if I have done it right and properly. Specially I'm not 100% sure if i calculated right the ...
0
votes
1answer
35 views

How to apply the strong Markov property in this case?

I'm trying to understand the following proof: Theorem: Let $(X_n)$ be an irreducible $(\alpha, \mathbf p)$-Markov chain with a finite state space $S$. Then $(X_n)$ is positive recurrent. ...
0
votes
0answers
18 views

A linear-algebraic property of stochastic matrices.

All matrices are real, $n \times n$. By a stochastic matrix, I mean any non-negative real matrix with rows summing to one. Denote the set of all stochastic matrices by $\mathcal{S}$. By $I_k$ I mean ...
1
vote
1answer
33 views

How to find the conditional expectation of the following random variable?

Let $\{N_n; n=1,2,3,\dots,\}$ be an irreducible and aperiodic Markov chain with transition probability matrix $\mathcal{P}=\begin{pmatrix} p_{0,0} & p_{0,1}&p_{0,2}&\cdots \\p_{1,0} & ...
0
votes
0answers
16 views

Gambler's ruin - expected time to go from 3 to 5 units

If we have a gambler's ruin problem, with p=0.4 and N=7 and we start with 3 units, a) what is the expected time the gambler has 5 units? b) what is the expected time to go fråm 3 to 5 units? ...
1
vote
0answers
20 views

Cereal boxes - Mean time spent in transient states

Problem: A cereal company gives 2 images in each cereal box it has. There are a total of 5 images. Once a buyer have 5 images she wins a prize. No box contains 2 images that are the same. What is the ...
0
votes
0answers
19 views

Ross probability models questions [closed]

I am studying for a course and have no professors to talk to live, so I hope some members here can be kind enough to help me. Rather than writing everything out, and splitting it up into different ...
0
votes
0answers
22 views

Continuous time Markov chain autocorrelation [closed]

Given a stationary distribution $\pi = [a/(a+b), b/(a+b)]$ and state space $S = \{0,1\}$, how do I calculate $E[X(t)X(s)]$ as $t,s \rightarrow \infty$? I'm stumped here.
1
vote
1answer
23 views

Branching process: Why does the population die or explode?

Consider a population such that each member, independently from other members, at a certain instant of time is replaced by its offspring. Lets denote with $X_n$ $({n\ge 1})$ the amount of the ...
1
vote
1answer
18 views

Max of independent and identical random variables is Markov

I'm supposed to show that given a sequence $\{Y_n\}$ of i.i.d the stochastic process $$X_n=\max(Y_0, Y_1...,Y_n)$$ is a Markov of chain. I think I could do it by induction but I would rather see how ...
1
vote
0answers
30 views

Markov Property as given in Norris' book on Markov chains vs standard formulation

In the book, Markov Chains, the following theorem is mentioned: Let $(X_n),n≥0$ be Markov$(λ,P)$. Then, conditional on $X_m=i,(X_{m+n})_{n≥0}$ is Markov$(\delta_i,P)$ and is independent of the random ...
0
votes
0answers
48 views

Follow-up on solution to markov process equation

I asked a question here about solving a system related to an absorbing markov chain. I now have a variation where there are $m$ types (of student, job seeker, etc) each of which applies to ...
-1
votes
0answers
51 views

Represent math problems as Markov chains [closed]

The step by step that takes to solve a math problem (algebra, calculus, etc.) could be seen as a Markov chain? When solving a problem, the next math rule that you are going to apply only depends of ...
1
vote
1answer
13 views

Limit distribution is invariant

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with a countable (but not necessarily finite) state space $S$. Suppose that there exists a limit distribution $\pi$, namely: ...
1
vote
1answer
20 views

About homogeneous Markov chains

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with discrete state space $S$. Now consider the map $$T_{ij}=\text{min}\{n\in\mathbb N\,:\, X_n=j\mid X_0=i\}$$ where $T_{ij}$ is defined ...
0
votes
0answers
13 views

Distributive Law on Sum Product

I am reading a tutorial on Conditional Randome Fileds, Here is the link: http://people.cs.umass.edu/~mccallum/papers/crf-tutorial.pdf in the equation 1.24 it defines: $p(x,y) = \prod_{t=1}^{T} ...
0
votes
0answers
14 views

Markov Models and Applications

I am looking for resources in Markov models and its applications. I'm looking for tutorials, videos, books etc which provide the following Explain Markov chains in layperson terms and provide ...
0
votes
0answers
11 views

Definition of Perron-Frobenius eigenvalue

Consider a Markov chain with state space $X$ and transition prob. matrix $P=(p_{ij})$. Then a paper claims the following : Let $\theta \in X$ denote some fixed state. The Perron-Frobenius eigenvalue ...
-1
votes
0answers
14 views

positive kernel induced by the transition probability P and the function F

Consider a markov chain $\{X_n\}$ and let $F:X \to \Bbb R_+$ a fixed, positive-valued function on $X$. Consider the process $\{F(X_n)\}$. Then what is meant by the positive kernel induced by the ...
1
vote
1answer
40 views

Why are points from this matrix geometric sequence co-planar?

Let $ M= \left[ {\begin{array}{ccc} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \\ \end{array} } \right] $, such ...
3
votes
0answers
29 views

A basic doubt on Markov chain/ergodicity

Consider a finite state (no. of state $N$) Markov chain $\{X_n\}$ (all the random variables are bounded) such that there is a state $i*$ such that $$ \sum_{i=1}^{N}p_{ii*}^{(n)} > 0$$ for all ...
2
votes
1answer
59 views

For finite Markov Chain, time average distribution is always a stationary distribution?

Given some finite state space $\Omega\equiv\{\omega_1,\ldots,\omega_n\}$ be given, and let any Markov chain $\{X_t\}$ with $n\times n$ transition matrix $A$ on $\Omega$ be given. I would like to know ...
-1
votes
0answers
29 views

A question about a Markov Chain

I encountered a question about Markov Chains which looks interesting. Given a homogeneous, irreducible, non cyclic Markov Chain with $K$ possible states and a transition matrix $Q$. We define $T_i$ ...
0
votes
1answer
24 views

Supply the transition matrix for these (possible) Markov chains

Reading Grimmet, Stirzaker: Probability and Random Processes, which unfortunately doesn't have solutions. Trying to make sure I understand Markov chains. A die is rolled repeatedly. Which of these ...
0
votes
0answers
15 views

Probabilities in a Markov Model

I am reading a paper on Markov Models and I am trying to figure out how to compute the probabilities for the $\alpha$-pass. I am given an $N\times N$ matrix $A$, that has the probabilities of ...
0
votes
0answers
28 views

Can ergodic theorem be used here

Suppose I have an ergodic Markov Chain $\{X_n\}$ where $X_n$ are bounded. Now, Can I say anything on the limit $$ \lim_{n\to\infty} \frac{1}{n}\ln E\left[e^{\sum_{i=0}^{n} X_i}\right]$$ I don't ...
0
votes
0answers
29 views

Treatment of Markov process with absolute states

In the standard treatment of a markov process, the state vector is a probability vector, whose elements can be between zero and one. But I have a need to constrain the state vector to zeros or ones. ...
1
vote
0answers
23 views

Conditional return time of simple random walk

Consider a simple random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0 = 0$. The probability to jump to the right neighbour is $p \geq \frac{1}{2}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, ...
1
vote
1answer
49 views

Markov Chain with Memory

One of the defining characteristics of a Markov Chain is that it is memoryless: the next state depends only on the current state, and not on the set of preceding states. I'm looking for a ...
1
vote
1answer
29 views

Measuring the entropy of a graph representing a transition probability matrix of a first order markov chain

There's a research project i'm currently working on which requires me to analyze various aspects of "worlds" represented by transition probability matrices, where the nodes represent objects in the ...
0
votes
0answers
12 views

For a general absorbing markov chain, if we have that $I-Q$ can be inverted, is it possible to prove the chain covers all stationary distributions?

If I have a general absorbing markov chain, there are nice properties when $I-Q$ is invertible. In my book, it claims it can be shown that a vector: $(0,0,0,...,0,v_1,...,v_{N-r+1} \in ...
0
votes
0answers
28 views

Exact probability distribution for hitting time of simple random walk

Consider simple random walk on the line starting from the site $y \in \mathbb{N}$. With probability $p$ the walker moves to the right and with probability $1-p$ to the left. Call $\tau$ the first time ...
0
votes
1answer
33 views

Application of Conjugate Gradient Method to non-symmetric matrices

I am currently working on a problem in which I am using the Conjugate Gradient method to solve for the steady state solution of a continuous time Markov chain. I am applying the algorithm found in ...
2
votes
0answers
22 views

Green's function of a Markov Chain, and maybe of a Feller Process?

How are the Green's functions of a Markov chain related to the notion from PDE theory? For instance, if the Markov chain (i.e. discrete state space) is continuous time, then the Green's function I'm ...
0
votes
0answers
28 views

Proof of Hammersley and Clifford theorem in Besag's paper

I am reading Besag's paper on Spatial Interaction and the Statistical Analysis of Lattice Systems, see http://www.cise.ufl.edu/~anand/fa11/Besag_Spatial_interaction.pdf. In section 3, it introduces ...
0
votes
1answer
60 views

Continuous time markov chains, is this step by step example correct

I have some questions regarding CTMC... and most importantly whether the step-by-step example I provide below is correct. My main sources about CTMC are: ([1], and [2]). Let's assume 3 possible ...
2
votes
1answer
35 views

Why left multiplication when it comes to Markov chains?

When working with Markov chains and transition matrices $P$ we multiply from the left, meaning that for example $\mu^{(n)} = \mu^{(0)}P^n$ or that the stationary distribution satisfies $\pi = \pi P$. ...
0
votes
1answer
38 views

Can the transition probabilities of an inhomogeneous Markov chain be written as an exponential?

If $Z_t$ is a homogeneous continuous-time Markov chain with finite state space $E=\{1,\ldots,p\}$, transition matrices $(P(t))$ and intensity matrix $Q$, it holds that $$ P(t) = \exp(tQ), $$ see for ...
0
votes
0answers
19 views

Initializing MCMC walkers with ambiguous direction (-/+)

I'm running a sampler program where there are observations given as sample data which are derived from an equal sized population of parameters that are converted to the observations using a known ...
2
votes
1answer
31 views

Finding the probability of ever visiting a transient state for a zero-seeking device for a Markov Chain?

A zero-seeking device operates as follows: if it is in state $j$ at time $n$, then at time $n+1$, its position is $0$ with probability $\frac{1}{j}$ or $k$ with probability $\frac{2k}{j^2}$, where $k$ ...
1
vote
1answer
19 views

Producing transient and recurrent examples for birth-death chains with mixed birth- and death-probabilities

Suppose we have a birth-death chain with a state space $$ S = \{0,1,2,\ldots\} $$ and transition probailities: $$p(x,y)=\begin{cases}q_x, &\text{if } y = x-1, &\text{i.e. death}\\ ...
1
vote
0answers
25 views

A question about Markov

There is a continuous-time markov chain,and we know the probability transition matrix P.The time between 2 states can be formulated as a exponential distribution whose u is related to the 2 states.Now ...
0
votes
1answer
33 views

Board Game Markov Process - Transient Probabilities

I need to write an essay on the Game of Life board game, and so I studied up on Markov Chains to help me calculate the probabilities and average payoffs for the spaces; however I'm not sure whether ...
0
votes
0answers
16 views

Simultaneous multiple perturbations in Markov chain Monte Carlo

I'm coding a McMC algorithm for geophysical applications. Using the Metropolis-Hastings scheme to accept/reject the proposed models is smth that i thought i completely understood, but i don't. To be ...
0
votes
1answer
27 views

Control principal eigenvector of a row stochastic matrix

I am just trying to consider the classical discrete-time Markov Chain problem. Consider the transition matrix P, which transforms state vector $x(k)$ to $x(k+1)$, satisfying: $x(k+1)$ = $P*x(k)$ It ...
0
votes
1answer
28 views

Q-matrix vs. P-matrix description of a Markov chain

Consider a continuous time Markov chain $(X_t)_{t \geq 0}$ on some state space $S$ with transition matrix (P-matrix) $p_t(x,y)$, the probability density of jumping from $x$ to $y$ in time $t$. The ...