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
1answer
921 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. ...
3
votes
1answer
787 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
605 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 ...
3
votes
2answers
67 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 ...
3
votes
1answer
57 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
105 views

Doubly stochastic matrix proof

A transition matrix $P$ is said to be doubly stochastic if the sum over each column equals one, that is $\sum_i P_{ij}=1\space\forall i$. If such a chain is irreducible and aperiodic and ...
3
votes
1answer
29 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
64 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
63 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
178 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
900 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
96 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
124 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
423 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 ...
3
votes
1answer
43 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
33 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
79 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
73 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
176 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 ...
3
votes
1answer
229 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
196 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
298 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
677 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
149 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 ...
3
votes
1answer
109 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
1answer
213 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
196 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
163 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 ...
3
votes
1answer
161 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
273 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
335 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
856 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
395 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 ...
3
votes
1answer
40 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
34 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
88 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 ...
3
votes
1answer
41 views

Does the measurability of $x\mapsto\operatorname P_x[A]$ imply the measurability of $x\mapsto\operatorname E_x[X]$?

Let $(\Omega,\mathcal A)$ and $(E,\mathcal E)$ be measurable spaces $(\operatorname P_x)_{x\in E}$ be a family of probability measures on $(\Omega,\mathcal A)$ such that $$E\ni x\mapsto\operatorname ...
3
votes
1answer
112 views

Irreducible Markov chain and invariant measure

We consider a Markov chain $\left(X,P\right)$ on a finite state space $X$. We denote $P:=\left(p_{x,y}\right)_{x,y\in X}$ and for $n\in\mathbb{N}$ $P^{n}:=\left(p_{x,y}^{(n)}\right)_{x,y\in ...
3
votes
1answer
84 views

Application of diagonalization of matrix - Markov chains

Problem: Suppose the employment situation in a country evolves in the following manner: from all the people that are unemployed in some year, $1/16$ of them finds a job next year. Furthermore, from ...
3
votes
2answers
123 views

Markov Chains - Strong Markov Property

I'm struck with an exercise. I tried, but the results don't seem to fit to those proposed. Exercise: Two players play the following game. The one who begins draws two cards from a deck of 40 cards ...
3
votes
1answer
38 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...
3
votes
1answer
32 views

non-stationary Markov chain n-step

When I search for the long term behaviour of a stationary markov chain I just multiply the transition matrix with itself for the number of steps: P(n) = P(0)^n. But how do you go about doing it ...