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

3
votes
2answers
602 views

What does it mean for MCMC to converge?

I know that a Markov Chain is a discrete random process where the current state decides the next and in a random walk, the probability that we move from node u to v is 1/N(u). An MCMC sample will ...
3
votes
2answers
54 views

Example of a markov chain that has a distribution that converges to some limit.

Can someone give me an example of a Markov chain that has a distribution that converges to some limit which depends on the initial distribution?
3
votes
2answers
49 views

Determine periodicity from transition matrix?

I have a two part question. Let's say we have a transition matrix T: \begin{bmatrix} 0 & 0.2 & 0.8 & 0 & 0 \\ 0.7 & 0 & 0.3 & 0 & 0 \\ 0.6 & 0.4 &...
3
votes
2answers
70 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...
3
votes
1answer
44 views

Coupling between two CTMCs

Suppose I have two random processes $X(t)$ and $Y(t)$ starting at time $t=0$ and $X(0)=Y(0)=0$. The processes obey the following transition rates: $$ X(t):\begin{cases} 0\to 1,\text{at rate } A\\ ...
3
votes
4answers
76 views

Determining vector equations

Let $A\in \Bbb R^{n\times n}$ be a matrix such that $\mathrm{rank}(A) = n-1$ and consider the equation $$ Ax = 0. $$ Clearly, its solutions span a $1$-dimensional space, thus an additional ...
3
votes
2answers
66 views

Is there a proof that the observations of a hidden Markov chain is not itself a Markov chain?

Suppose $\{X_n\}$ is the hidden Markov chain, and $\{Y_n\}$ is the series of observations, where $\mathbb{P}\{Y_n = j| X_n = i\}$ is the same for all $n$ (please correct me if I have not stated the ...
3
votes
1answer
952 views

example of irreductible transient markov chain

Can anyone give me a simple example of an irreductible (all elements communicate) and transient markov chain? I can't think of any such chain, yet it exists (but has to have an infinite number of ...
3
votes
2answers
3k views

Markov chain with infinitely many states

I understand that a Markov chain involves a system which can be in one of a finite number of discrete states, with a probability of going from each state to another, and for emitting a signal. Thus,...
3
votes
1answer
818 views

Show that two states in the same communicating class of a Markov chain must have the same period

How would you go about showing that two states in the same communicating class of a Markov chain must have the same period? Any help would be greatly appreciated.
3
votes
2answers
658 views

How can I compare two Markov processes?

There is a discrete-time irreductible Markov process with $r$ possible states. $k$ observations were performed. At each observation a state of process was determined. $T_0 = \lbrace 0,1,\dots ,k-1\...
3
votes
2answers
68 views

Defining the states when we roll one single die repeatedly

We roll a single die and the game stops as soon as the sum of two successive rolls is either 5 or 7. We want to find the probability that the game stops at a sum of 5. It seems like Markov chain ...
3
votes
1answer
63 views

Markov Chain with two components

I am trying to understand a question with the following Markov Chain: As can be seen, the chain consists of two components. If I start at state 1, I understand that the steady-state probability of ...
3
votes
1answer
30 views

Arguing a stationary distribution exists

I am trying to show that there exists a stationary distribution when $q>p$ for the Markov process with one-step transition matrix $$ \begin{bmatrix} q & p & 0 & 0 & \...
3
votes
1answer
75 views

Question about random walk markov chain

For a random walk, let $a$ denote the probability that the markov chain will ever return to state $0$ given that it is currently in state $1$. Because the markov chain will always increase by $1$ with ...
3
votes
1answer
64 views

Recurrence/Transience of random walk with +2/-1 steps

Consider the Markov chain with state space $S=(0,1,2,...)$ and transition probabilities: $p(x,x+2)=p$ , $p(x,x-1)=1-p$, $\forall$ $x>0$. $p(0,2)=p$ , $p(0,0)=1-p$. For which values of $p$ is this ...
3
votes
1answer
184 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 ...
3
votes
1answer
1k views

Markov chains: is “aperiodic + irreducible” equivalent to “regular”?

I have two books on stochastic processes. In one book, it says that the limiting matrix is possible to find if the matrix is regular, that is, if for some $n$ $P^n$ has only positive values. The ...
3
votes
1answer
998 views

Markov Chain Initial Distribution

Suppose $\{X_0,X_1,X_2,\dots\}$ is a discrete-time Markov chain taking values in a finite set $\{1,\dots,N\}$ with initial distribution $p_i(0) = P(X_0 = i)$ for $i\in\{1,\dots,N\}$ and transition ...
3
votes
2answers
99 views

Random walk on one-dimensional lattice - understanding the expression $pe^{i\theta} + qe^{-i\theta}$

I've started reading the book - First Steps in Random Walks and in the very first example in Chapter 1 they talk about a random walk on a one-dimensional lattice. If we consider a particle starting ...
3
votes
2answers
93 views

What's the probability that A wins finally

Suppose A has \$2 and B has \$3. They play a game, each game gives the winner \$1 from other. A has a probability $\frac{3}{5}$ to win each game. They play this game until one of them is bankrupt. ...
3
votes
1answer
126 views

How to find the limit of a markov chain

Given a markov chain where the next state is related to the previous state by the following matrix: $$\begin{array}{c|ccc} & A & B & C\\ \hline A & p_1 & q_1 & r_1\\ B & ...
3
votes
1answer
241 views

Conditional probability of a general Markov process given by its running process

I have a question as follow: "Let $X$ be a general Markov process, $M$ is a running maximum process of $X$ and $T$ be an exponential distribution, independent of $X$. I learned that there is the ...
3
votes
2answers
439 views

Calculating probabilities (Markov Chain)

Let $\mathcal{X}=(X_n:n\in\mathbb{N}_0)$ denote a Markov chain with state space $E=\{1,\dots,5\}$ and transition matrix $$P=\pmatrix{1/2&0&1/2&0&0\\1/3&2/3&0&0&0\\0&...
3
votes
1answer
45 views

Rigorous argument of the Markov property used in discrete-time Markov chains

I am reading an example related to discrete-time Markov chains which I do not really understand rigorously. Suppose that $\{ X_n \}_{n \in \mathbb{N} }$ is a time-homogeneous discrete-time Markov ...
3
votes
1answer
35 views

Uniqueness of the solution to a discrete boundary value problem

Given a Markov chain with state space $\Omega$ and transition matrix $P$, and $A\subset \Omega$, define function$f(x)=\Bbb E _x(\tau_A)$, where $\tau_A$ is the "stopping time into set $A$", meaning ...
3
votes
1answer
88 views

Computational methods for the limiting distribution of a finite ergodic Markov chain

We wish to show what can be discovered about the limit of a finite, homogeneous, ergodic Markov Chain $X_1, X_2, \dots,$ using simple methods of computation and simulation. Specifically, consider the ...
3
votes
1answer
86 views

Random Walk Threshold Problem with a Time-Dependent Threshold

For any constant threshold in a random walk, the probability we cross the threshold at some time goes to 1 as time goes to infinity. But how can we approach the problem if the threshold is time ...
3
votes
1answer
198 views

Fano's Inequality Proof

For an information theory class, I am studying the proof for Fano's inequality, i.e.: $H(P_e) + P_elog(|X|) \geq H(X|\hat{X}) \geq H(X|Y)$ Where $H(X)$ is the entropy of the random variable X $\hat{...
3
votes
1answer
242 views

The expected time until reaching a specified set in a Markov chain

I am reading an article in which they discuss a specific Markov chain in an example, and it turns out I need to sharpen up my Markov knowledge. First the setup. I have a continuous time Markov chain ...
3
votes
2answers
230 views

Limiting probability that the sum of the values of a die is a multiple of 13

A fair die is thrown repeatedly. Let $X_n$ denote the sum of the $n$ first throws. I have to find $\lim_{n\rightarrow \infty}P(X_n \text{ is multiple of 13})$. Now follows what I tried, which I don't ...
3
votes
1answer
48 views

Is it true that $\|\text{diag($\pi$)} P\|_2 \leq 1$ for $P$ stochastic and $\pi P = \pi$.

$\| \cdot \|_2 $ is the matrix norm induced by $L_2$. $P$ is any given real square $n \times n$ non-negative matrix with rows summing to one, i.e. $P1 = 1$, where $1$ is the vector of ones. There is ...
3
votes
1answer
340 views

Safe small wins vs. risky large wins at roulette

Short statement of problem : Two players play roulette at a casino. They both start with the same initial amount. Each player always plays his favorite bet each time, and stops playing as soon as he ...
3
votes
1answer
716 views

Elementary proof of geometric / negative binomial distribution in birth-death processes

The birth-death process concerns a population of $n_0$ individuals, each of which reproduce and die at a constant rate as time $t$ increases from $t=0$. Each individual splits into two individuals (...
3
votes
1answer
154 views

Markov chain problem with finite states

Consider any Markov chain on a state space with exactly $r$ states. We want to find the largest $N>0$ such that there exists states $i,j$ for every $n < N$ we have $p_{ij}^{(N)} > 0$ and $p_{...
3
votes
1answer
115 views

Random walk where increment depend on current position

Consider the following stochastic process, $$b(i+1) = b(i) + \xi_i (b_i),$$ where $\xi_i(b_i) \in \{-1, k \}$ are the independent increments having the following distribution: $$\begin{align} P (\xi =...
3
votes
2answers
227 views

Expected number of random binary vectors to make matrix of order n

I have the following problem: I pick random vectors from $\mathrm{F}_2^n$. The chance that position $i$ is $1$ equals $p_i$, $0$ otherwise (each position is picked independently). Let $X$ be a random ...
3
votes
1answer
199 views

recurrence criterion for random-walk like (simple) inhomogeneous Markov chain

This question is to some degree a follow-up of this question. Suppose we have a random-walk like Markov chain, i.e. state space is the set of all integers from $-\infty$ to $\infty$, the transition ...
3
votes
1answer
174 views

Sojourn time of a CTMC

Soujourn time of a CTMC at time $t$ is defined as : $$T(t)= \inf\{ s > 0 : X(t+s) \neq X(t)\}$$ My question is why "inf", not min ? Here $T(t)$ belongs to the set $\{ s > 0 : X(t+s) \neq X(t)\...
3
votes
1answer
164 views

Probability with Markov chains

I need some hint about Markov chains. So here is my homework. Let $\{ X_t : t = 0,1, 2, 3, \ldots, n\}? $ be a Markov chain. What is $P(X_0 =i\mid X_n=j)$? So I need to calculate if it's $j$ ...
3
votes
1answer
4k views

Irreducible, finite Markov chains are positive recurrent

I am under the impression that an irreducible, finite Markov chain is necessarily positive recurrent. How might I show this? Regards, Jon
3
votes
1answer
120 views

Limit of a probability regarding a random walk

Consider a random walk on the integers starting at 0, where in each step you move either 1 or 2 meters (back or forth alike). As soon as you reach either the $N$ or $N+1$ meter mark, you stop. What is ...
3
votes
2answers
277 views

a theorem on transient and recurrent state in a DTMC

Is the following statement true: In a finite Markov chain, if $i$ is a transient state then there is at least one recurrent state $j$ such that $j$ is reachable from $i$.
3
votes
2answers
342 views

Martingale associated to Markov chain

$X$ is a (continuous time) Markov chain with generator matrix $\Lambda$ and finite state space $G$. I know that for $g\colon G \to R$ $$ M_t = g(X_t) - g(X_0) - \int_0^t (\Lambda g)(X_s)\, ds $$ is a ...
3
votes
1answer
2k views

Finding the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\mathbb{N}_0$, $q_n >0$ for all $n \in \mathbb{N}_0$ and transition matrix below: \begin{bmatrix} q_0 &...
3
votes
2answers
870 views

Proof of Markov property for Ehrenfest urn

[the question got downvoted on MO with the recommendation to ask here] In many books Ehrenfest Urn is used as an example of a homogeneous Markov chain, where entries in transition probabilities ...
3
votes
2answers
400 views

Expectation of a stopping time uniquely determined by a function

Let $(X_t)_{t\ge0}$ be a Markov chain on a finite state space $\Omega$, with transition probability $P$. Let $T$ be a stopping time such that $T=\min \{t\ge 0;X_t \in A \subset \Omega \}$.  If $f(x)=...
3
votes
1answer
73 views

Example of a Continuous-Time Markov Process which does NOT have Independent Increments

1. Given a discrete-time Markov chain without independent increments, is the embedding of it into a continuous time Markov chain (i.e. via the use of exponential waiting times) an example of a ...
3
votes
1answer
35 views

Poisson: $P(N(4)-N(2)=5|N(4)=8)$

Let {N(t), t ≥ 0} be a Poisson process of rate 2. Determine: a) $P(N(4)-N(2)=5|N(4)=8)$ Attempt: The conditional poisson distribution is uniformly distributed between the interval [0,4]. Therefore, ...
3
votes
2answers
100 views

If $X$ is a right-continuous, discrete Markov process, then $\displaystyle\lim_{t\downarrow 0}\operatorname P_x\left[X_t=x\right]=1$

Let $E$ be an at most countable Polish space and $\mathcal E$ be the discrete topology on $E$ $X=(X_t)_{t\ge 0}$ be a discrete Markov process with values $(E,\mathcal E)$ and distributions $(\...