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

Distribution of throws of die rigged to never produce twice in a row the same result

A die is “fixed” so that each time it is rolled the score cannot be the same as the preceding score, all other scores having probablity 1/5. If the first score is 6, what is the probability that the ...
4
votes
1answer
79 views

Markov chain ergodicity

$(X_n)_n$ is a discrete-time, time-homogenous Markov chain. I have have the following transition matrix and want to show whether the chain is ergodic. $$P = \begin{pmatrix} \frac{1}{2} & 0 & ...
4
votes
1answer
124 views

$P^n$ transition matrix of a Markov chain

The setup: We have an unlimited supply of balls and $k$ boxes. In every step, we randomly (all of them have the same probability) choose a box and put a ball in it. Let $X_n$ be the number of ...
4
votes
1answer
310 views

Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t &...
4
votes
1answer
391 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 ...
4
votes
3answers
849 views

What is the difference between the forward and backward equations in a CTMC?

Given that the Forward equation in a CTMC (Continuous Time Markov Chain) is: $P'(t)=P_t G$, and the Backward equation is: $P'(t)=G P_t$, which equations should I use of the two depending on the case I ...
4
votes
3answers
401 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
1answer
2k views

coin flips and markov chain

Consider the case of an infinite (or finite $n$) string of coin tosses, and let $q$ and $1-q$ be the probabilities that the coin comes up tails and heads, respectively. (For simplicity, we can take $...
4
votes
1answer
36 views

Getting all positive integer solution (All possible states of a chemical system) to undertermined linear system (Conservation law from stoichiometry)

Let a chemical system be defined as $${A<=>B<=>C}$$ Then the stoichiometry is given as $$S=\begin{bmatrix} -1& 1& 0& 0\\ 1& -1& -1 & 1\\ 0 & 0 & 1 &-...
4
votes
1answer
93 views

Ehrenfest Chain: stationary distribution

In the Ehrenfest Chain model: There are M balls which are divided between urn A and urn B. At each stage, if a ball is chosen, then it would be moved into a different urn. Let $X_n$ be the # of ...
4
votes
1answer
72 views

If $τ_x^k$ is the time of the $k$-th entrance of a Markov chain into $x$, then $\text P_x[τ_y^k<∞]=\text P_x[τ_y^1<∞](\text P_y[τ_y^1<∞])^{k-1}$

Let $E$ be at most countable and equipped with the discrete topology and $\mathcal E$ be the Borel $\sigma$-algebra on $E$ $X=(X_n)_{n\in\mathbb N_0}$ be a discrete Markov chain with values in $(E,\...
4
votes
2answers
116 views

Ergodic components of Markov chain by transition matrix

I would like to find an algorithm for obtaining all ergodic components of a finite Markov chain with discrete time defined by its transition matrix (i.e. ergodic subchains into which the given chain ...
4
votes
1answer
100 views

Expectation and limit of a stop-and-go traveler markov chain

The velocity $V(t)$ of a stop and go traveler is a two-state Markov chain whose generator is given by $$ \begin{array}{cc} &\begin{matrix}0&1\end{matrix}\\ \ \begin{matrix}0\\ 1\end{matrix} &...
4
votes
1answer
53 views

Expected number of turns for SPROUT

As a mathematical father (and with apparently plenty of time on my hands) I long ago computed the expected number of turns for a number of children's games that are effectively Markov maps. (Chutes ...
4
votes
1answer
42 views

How do stochastic matrices really converge?

We are given the matrix $A=\begin{bmatrix}0.9&0.5\\0.1&0.5\end{bmatrix}$ and any initial vector $X^{(0)}=\begin{bmatrix}a\\b\end{bmatrix}$. The matrix $A$ has the following eigensystem: $\...
4
votes
1answer
102 views

An irreducible Markov chain is a martingale

Let $\{X_n\}$ be an irreducible Markov chain. Does exist example of such $\{X_n\}$ which is also a martingale given that: a. $\{X_n\}$ is recurrent with finite number of states (but bigger than $...
4
votes
1answer
125 views

Exercise from Norris' book on Markov chains

Let $(X_n)$ be a Markov chain on $\mathbb{N}$ with transition probabilities satisfying: $$p_{0,1}=1,\quad p_{i,i-1}+p_{i,i+1}=1,\quad p_{i,i+1}=\left(\frac{i+1}{i}\right)^{\alpha}p_{i,i-1}$$ The ...
4
votes
1answer
341 views

Derivative of conditional expectation

Let $\left( {{X_t}:t \in \left[ 0 \right.\left. {, + \infty } \right\rangle } \right)$ be a continuous time Markov chain on a probability space $\left( {\Omega ,\mathcal{F},\mathbb{P}} \right)$ with a ...
4
votes
1answer
119 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
110 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
163 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. $p(i,...
4
votes
2answers
831 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. a)...
4
votes
1answer
300 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
3answers
222 views

Markov chain stationary probability simulation

Having a defined markov chain with a known transition matrix, rather than to calculate the steady state probabilities, I would like to simulate and estimate them. Firstly, from my understanding there ...
4
votes
1answer
132 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
71 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
4
votes
2answers
102 views

What is the probability this Markov chain does not reach state $r$?

Consider a random walk on the non-negative integers. You start at $0$, and in each step you either move $1$ higher, or $2$ lower (but can't go below $0$). The direction is picked w.p. $1/2$ ...
4
votes
0answers
87 views

Weak convergence of a sequence of stationary distributions to another stationary distribution

Let $\{X_n(t) \in \mathbb{R}^+\}$ for each $t \in (0,1)$ denote a discrete time Markov chain (with time index $n$ and parameterized by $t$). For each $t$, the Markov chain $\{X_n(t)\}$ has a unique ...
4
votes
1answer
74 views

Simple random walk: What is the probability that the hitting time is exactly 2n?

I refer to the random walk $(S_n)_{n \geq 1}$ where $S_n = X_1 + \cdots + X_n$ and $X_i$ are i.i.d random variables taking values $\pm 1$ with equal probability. I want to know how to show that $$\...
4
votes
0answers
252 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 following ...
4
votes
0answers
80 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
1answer
151 views

Markov Chains Proof using Statistics

Source: This came from "Introduction to probability" by Charles Miller Grinstead, and James Aurie Snell. It was located on page 407 and is Theorem 11.1 in the section 11.1 Introduction. Theorem: The ...
4
votes
0answers
111 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
157 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 $(\alpha_{t+1}|\alpha_{...
4
votes
1answer
193 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
0answers
118 views

maximum renewal rate of a Markov chain

Consider a Markov chain $(X_t)$ on a state-space with a countably generated $\sigma$-algebra and assume this Markov chain allows for small sets of order one. This means there exist sets $\mathfrak{S}$ ...
4
votes
0answers
281 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
184 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
2answers
6k views

What does the steady state represent to a Markov Chain?

I'm a little confused as to the interpretation of the steady state in the context of a Markov chain. I know Markov chains are memoryless, in that each state only depends on its immediate predecessor, ...
3
votes
2answers
99 views

Under what conditions does $(I-N)^{-1}$ exist?

Given an nxn matrix N and $I=I_n$, under what conditions does $(I-N)^{-1}$ exist? On one hand $(I-N)(I + N + N^2 + ...) = (I + N + N^2 + ...) - (N + N^2 + ...) = I?$ On the other hand, $(I-N)(I + N +...
3
votes
3answers
428 views

Characterize stochastic matrices such that max singular value is less or equal one.

By a stochastic matrix, I mean any non-negative square real matrix with rows summing to one. It is well-known that singular values of stochastic matrices can be more than one. Is there a ...
3
votes
2answers
465 views

Transition Matrix eigenvalues constraints

I have a Transition Matrix, i.e. a matrix whose items are bounded between 0 and 1 and either rows or columns sum to one. I would like to know if it is possible that in any such matrices the ...
3
votes
1answer
665 views

If $P$ is a regular transition probability matrix then $P^{n^2}$ has no zero element

A transition probability matrix $P\in M_{n\times n}$ is regular if for some $k$ the matrix $P^k$ has all of its elements strictly positive. I read that this can be tested by using the following result....
3
votes
3answers
975 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 i\leq98$...
3
votes
2answers
513 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
1answer
300 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
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
220 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
1answer
26 views

Show that a matrix satisfying certain conditions is non-singular

I have a square matrix $A$ satisfying the following conditions: The elements on the diagonal are negative; All other elements are non-negative; All row sums are less than or equal to $0$; There is ...
3
votes
2answers
3k 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 ...