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

4
votes
2answers
132 views

Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$. So since this Markov chain has only a single ...
4
votes
3answers
205 views

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain. I don't know what this exercise has been so difficult for me, I've been playing around with the ...
4
votes
3answers
3k views

Why Markov matrices always have 1 as an eigenvalue

Also called stochastic matrix. Let $A=[a_{ij}]$ - matrix over $\mathbb{R}$ $0\le a_{ij} \le 1 \forall i,j$ $\sum_{j}a_{ij}=1 \forall i$ i.e the sum along each column of $A$ is 1. I ...
4
votes
1answer
544 views

Return time of a markov chain

I'm having trouble deriving the return time for a Markov chain. The graph has $n$ vertices and is connected by $n - 1$ edges. So we can draw this as a horizontal line of nodes with node $1$ all the ...
4
votes
1answer
878 views

Strong Markov property - Durrett

I recently had great success with my first question here so I will boldly go on to a second. Here goes: I'm studying Markov Chains in Rick Durrett - Probability: Theory and example and I'm stuck with ...
4
votes
3answers
325 views

From a deterministic discrete process to a Markov chain: conditions?

When will a probabilistic process obtained by an "abstraction" from a deterministic discrete process satisfy the Markov property? Example #1) Suppose we have some recurrence, e.g., $a_t=a^2_{t-1}$, ...
4
votes
1answer
60 views

Finding Hitting probability from Markov Chain

I have a Markov chain with states {1,2,3,4,5} which has the following transition matrix: $$P= \begin{bmatrix} 0.3 & 0 & 0.7 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0.5 & 0 ...
4
votes
1answer
67 views

Joint Probability from Marginal Probabilities

$X, Y_1, Y_2$ are random variables with (possibly) different finite alphabets. For given conditional probability mass functions $\mathbb{P}(Y_1|X)$ and $\mathbb{P}(Y_2|X)$, is it always possible to ...
4
votes
2answers
125 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. ...
4
votes
1answer
283 views

question involving Markov chain

Let $S_{2m}$ be the group of all permutations $\pi$ of $\{1, 2, \ldots, 2m\}$. The following transition kernel $S$ generates the random transposition walk $$ Ch(\pi, \pi')= \begin{cases} \frac{1}{2m} ...
4
votes
1answer
230 views

Does every continuous time minimal Markov chain have the Feller property?

Consider a Q-matrix on a countable state space. (A Q-matrix is a matrix whose rows sum up to $0$, with nonpositive finite diagonal entries and nonnegative offdiagonal entries). As explained for ...
4
votes
1answer
110 views

random walk along edges of tetrahedron — which face gets hit last?

Suppose we have a tetrahedron $abcd$, and start at edge $ab$. Now walk to any "adjacent" edge (i.e. in this case any edge other than $cd$), each with equal probability $1/4$. This gives a stationary ...
4
votes
0answers
19 views

Harmonic functions and null recurrence

Let $(X_n)_{n \geq 0}$ be a irreducible Markov chain defined on a countable state space $S$. It is known some ways to figure out if this chain is recurrent or not looking for superharmonic functions ...
4
votes
0answers
126 views

6-digit password - a special decoding method

Consider the situation of decoding a 6-digit password that consists of the symbols A to Z and 0 to 9, where all possible combinations are tried randomly and uniformly. Consider the ...
4
votes
0answers
52 views

Markov chains and natural filtration

I have the following problem Consider a homogeneous Markov chain $(X_n)$ with countable state set $E$. Suppose that $A$ is a proper subset of $E$ and consider the stopping times $\tau^0=0 $ and ...
4
votes
0answers
51 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
4
votes
0answers
78 views

A Continuous-Time Markov Process Taking All Possible Values

Let $\mathbb{N}$ be the set of positive integers. For each $n \in \mathbb{N}$, let $X^{(n)}=\{ X^{(n)}(t): t \geq 0 \}$ be a Markov chain with state-space the two point set $\{0,1\}$ and $Q$-matrix ...
4
votes
0answers
138 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for ...
4
votes
1answer
185 views

Lower bound for multivariate recurrence

I have a recurrence that looks like $$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$ $$p(i,0,k) = 1$$ $$p(i,j,0) = 0$$ $$p(0,j,k) = 0$$ The base cases are to be considered in ...
4
votes
1answer
280 views

Intuition on Harris recurrence

I am trying to get some intuition on Harris recurrence in Markov chains. Define state space $\mathcal S$ comprising a single communication class, $f_{ii}^{(n)}=P(X_n=i, X_{n-1}\ne i,\ldots X_1\ne ...
4
votes
0answers
192 views

estimation of transition probabilities from aggregate data

Please, O mathematicians, help me understand the approach to the problem of estimating transition probabilities given only aggregate data in Kalbfleisch & Lawless' 1984 paper "Least-Squares ...
4
votes
1answer
144 views

Behavior of explosive random process

Inspired somewhat by this problem, I've been investigating the behavior under iteration of the following discrete random process: Given $n\in\mathbb{N}$, choose an integer from $\{0,1,\ldots,n\}$ ...
3
votes
3answers
737 views

Probability of absorption in a discrete Markov chain

Let $\{X_{n}\}$ be a Markov Chain on the state space $S=\{1,...,100\}$ with $X_{0}=30$, and transition probabilities given by $p_{1,1}=p_{100,100}=1$, $p_{99,100}=p_{99,98}=1/2$ and for $2\leq ...
3
votes
1answer
273 views

Expected number of runs

Let $S[16]$ be a binary array i.e, elements of $S$ are 0/1 with elements $S[i]$ are taken uniformly and independently form $\{0,1\}$. Let $k$ be a random element taken uniformly from $\{0,1\}$. I have ...
3
votes
2answers
438 views

Irreducible and aperiodic Markov chain : $P^t(x,y)>0$

Consider a Markov chain $X$ with transition probability $P$ and finite state space $\Omega$. Which of the following statement is true? If $X$ is irreducible then $\exists t>0 \ni P^t(x,y)>0, ...
3
votes
2answers
168 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
1k 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
1k 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
1answer
4k views

Kendall notation's “General distribution”, what does that mean?

The first and second parameters for the Kendall's notation may have a G value, which stands for General distribution, see here. But what does that mean? What is a ...
3
votes
2answers
483 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
1answer
3k views

How can I compare two matrices?

I have a matrice A. It is model probability matrice for some process (Markov chain). Then, I have estimated matrice B. I have to somehow compare these two matrices to tell whether process that gave ...
3
votes
4answers
73 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
392 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
512 views

Markov chain with uncountable state space

I'm self-studying probability theory and struggling with understanding Markov chains on uncountable state spaces, notably I would like to solve the following exercise from this book. ...
3
votes
1answer
54 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
109 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
36 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
1answer
170 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
72 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
201 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
1answer
56 views

Applying MCMC Metropolis algorithm

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up. The path is a sequence $ ...
3
votes
1answer
39 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
83 views

When are stable continuous time Markov chains Feller? Always?

This is a question is similar to this 2 year-old one that never got answered (truthfully it's pretty much the same question except that I'm adding a bit more detail and the assumption that the $Q$ ...
3
votes
1answer
275 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
89 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
114 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
76 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
162 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
101 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 ...