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
185 views

Markov Chains and Linear Transformations

I just have a quick question about Markov Chain and linear algebra. Background. Let $\{M_n: n= 0, 1, 2, \dots \}$ be a Markov Chain. We can represent the transition probabilities $_{n}Q^{(i,j)}$ in a ...
3
votes
2answers
2k views

Null-recurrence of a random walk

In a random walk on $\mathbb{Z}$ starting at $0$, with probability 1/3 we go +2, with probability 2/3 we go -1. Please prove that all states in this Markov Chain are null-recurrent. Thoughts: it is ...
3
votes
1answer
2k views

Calculating stationary distribution of markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below: \begin{bmatrix} 0 & 1 \\ \frac{1}{n} ...
3
votes
2answers
586 views

Simple proof that stationary birth-death chains are reversible

A Markov chain with state space $\mathbb{Z}$ is a birth-death chain if the transition probabilities satisfy $p(x,y) = 0$ for $|x-y| > 1$. That is, the only possible transitions are to move one ...
3
votes
2answers
415 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
52 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
42 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
74 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
477 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
1answer
46 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
57 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
135 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
302 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
76 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
116 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
210 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
73 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
46 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
420 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
108 views

Question about Markov chain

We know that if $\{X_n\}$ is a Markov chain, then $X_{n+1}$ is independent with the past states $X_0,\ldots,X_{n-1}$ given current state $X_n$, that is ...
3
votes
1answer
130 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
89 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
655 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
179 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
127 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
138 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
109 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
248 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
274 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
743 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
385 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
2answers
36 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
31 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
66 views

Joint density function Poisson Process

We did an example in class that I'm not sure how we came up with the answer. The problem is: If I let X(t) be a Poisson process of rate $\lambda$. I'm supposed to validate the identity ...
3
votes
1answer
63 views

Stochastic matrices with orthogonal eigenvectors

I stumbled across an odd fact while thinking about Markov chains, and I have an odd proof for it. Claim: Let $P$ be the transition matrix of a finite irreducible aperiodic Markov chain, and assume ...
3
votes
1answer
26 views

Show that $p_{ii}^{(k+l)}\geqslant p_{ij}^{(k)}\cdot p_{ji}^{(\ell)}$

Let $(X_n)_{n\in\mathbb{N}_0}$ be an irreducible Markov chain with state space $E$ and Transition Matrix $P=(p_{ij})_{i,j\in E}$. Set $$ ...
3
votes
1answer
79 views

Gambler's ruin: Distribution of the maximum fortune along the game conditioned to lose

I having troubles with this problem: Let $(X_n)$ a gambler's ruin Markov chain on $\{0,\dots,N\}$ i.e. a Markov chain with state set $E=\{0,\dots,N\}$ and probability transitions $$p(k,k+1)= ...
3
votes
1answer
88 views

Mean exit time / first passage time for a general symmetric Markov chain

Suppose I have a Markov chain as depicted in the following figure: where $N$ is even. State 0 and $N$ are the two sinks of the chain. The transition probabilities have the following property: ...
3
votes
1answer
109 views

What does a customer see when it begins to be served in $M/M/1$ queue?

In queueing theory, the PASTA (Poisson Arrivals See Time Averages) principle [wiki] justifies $a_n = P_n$ where $$a_n = \text{proportion of customers that find } n \text{ customers in the system when ...
3
votes
1answer
172 views

A linear growth model with immigration

Ill give some background first before asking questions.(the text below is straight out of the book) Each individual in the population is assumed give birth at an exponential rate of $\lambda$ in ...
3
votes
1answer
571 views

Sum of two Markov processes another Markov process?

Let $dX_{t} = m_1(l_1-X_{t})dt+\sigma_1 dW_{t}$ and $dY_{t} = m_2(l_2-Y_{t})dt+\sigma_2(\rho dW_{t}+\sqrt{1-\rho^2}dW_{t}^{1})$ where the $m_i$'s, $l_i$'s and $\sigma_i$'s are constants, $\rho \in ...
3
votes
1answer
26 views

The expectation of total number of different states in N time points

[Conditions] (1) An object has K possible states. (2) This object can have only one state at a single time point. (3) The probability of each state at any single time point is 1/K, and each time ...
3
votes
1answer
293 views

A basic question on irreducible periodic markov chain

For an irreducible periodic (period $2$) Markov Chain I know that both of the following two quantities are same and equal to $\pi(i)$: $$ \lim_{n\to \infty} \frac{1}{2}(p_n(j,i) + p_{n+1}(j,i))$$ $$ ...
3
votes
1answer
654 views

Proof about Steady-State distribution of a Markov chain

Consider $A$ as a matrix, that when normalized represents an finite-state time-homogeneous Markov chain $M$ with entries $0\leq p_{i,j}\leq 1$, where each row sums up to $1$. We can also assume that ...
3
votes
1answer
1k views

Acceptance probability of Metropolis-Hastings

I am an IT guy writing my masters thesis on MCMC methods for use in predicting the outcome of football(soccer) matches. Right now I am trying to wrap my head around MCMC and Metropolis-Hastings in ...
3
votes
1answer
157 views

what's the generalized approach to this infinite state markov chain problem

Say, a bag has 10 balls, in which 9 are red, 1 is black. Each red ball is worth 1 point, each black is worth 4 points. I have 8 picks from the bag to start with (the bag refills itself after each ...
3
votes
1answer
595 views

Countable state Markov chain: detailed balance consequences

Let $S$ be a countable set and $\pi$ a probability distribution on $S$. A discrete-time Markov chain $(X_n)$ with state space $S$ is said to be in detailed balance with respect to $\pi$ (or simply in ...
3
votes
1answer
1k views

Probability distribution of markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 2/3 & 0 ...
3
votes
1answer
96 views

What happens to a regular Markov matrix that has more than one steady state/stationary distribution?

It is known that for a regular Markov matrix $M,$ $M^{n}$ has the steady-state vector as all of its columns as $n \to \infty.$ I learned this in class, but what if there is more than one steady-state ...