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

1
vote
1answer
70 views

Two definitions of the strong Markov property

In Durrett's textbook, the strong Markov property is defined as follows: For every bounded and measurable $\varphi$ and stopping time $N$: ...
1
vote
0answers
101 views

Compute transition probability in n step in infinte markov chain

I want to calculate the probability of transition in n step from state 0 to state 0 ($p_{00}^{(n)}$) in below Markov-Chain : if self loop in state 0 doesn't exist, probability computed with Catalan ...
0
votes
2answers
221 views

Are irreducible, positiv-definite Markov chains aperiodic?

If $M$ is the transition matrix of a discrete Markov chain, and $M$ is both irreducible, symmetric and positiv-definite, is the resulting Markov chain necessarily aperiodic? In my intuition, ...
2
votes
0answers
89 views

Invariant Probability of Discrete Time MC from Continuous Time Markov Chain

Given rates α of an irreducible continuous-time MC on finite state space and told that π is the invariant probability measure of this chain, we define a discrete time MC as having transition ...
3
votes
1answer
68 views

Prove matrix is positive semi-definite

$P$ is a stochastic matrix (square, non-negative, rows sum to 1). $\Xi$ is a diagonal matrix with a left principal eigenvector of $P$ on the diagonal and zeros elsewhere (stationary distribution if ...
1
vote
1answer
237 views

Random Walk on Clock Hands

We do a random walk on a clock. Each step the hour hand moves clockwise or counterclockwise each with probability 1/2 independently of previous steps. If you start at 1 what is the expected number ...
2
votes
1answer
130 views

Why can a Markov chain having two states and no self-loop have a stationary distribution?

Why does a Markov chain having two states and no self-loop can have a stationary distribution? Lets consider a markov chain with two nodes = $\{A, B\}$ and the transition matrix: $P = ...
2
votes
0answers
224 views

How to prove a matrix norm inequality?

$P$ is a stochastic matrix i.e. square, non-negative, rows sum to one. Let $\Phi$ be a real matrix of size $n \times k$ with independent columns and $k < n$. Let $\Xi$ be the diagonal matrix with a ...
1
vote
1answer
46 views

Prove $\Xi (I - P)$ has eigenvalues in the non-negative real half-plane.

Let $P$ be a stochastic matrix (square, non-negative,rows sum to one). Let $\Xi$ be a diagonal matrix with any left principal eigenvector of $P$ on the diagonal and zeros elsewhere (stationary ...
3
votes
0answers
142 views

Prove or disprove: If $h$ is harmonic on $E$, then $h$ is constant on each $C_i$

For a general finite Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E$ and transition matrix $P=(p_{x,y})_{x,y\in E}$, not necessarily irreducible, we define the linear space of ...
0
votes
1answer
49 views

Convergence of the number of visits in a Markov Chain

Suppose we have an irreducible and recurrent discrete-time Markov chain with states over the finite set $\mathcal{X}$. Let $N_t (x)$ denote the number of visits to state $x$ up to time $t$. Let ...
2
votes
2answers
135 views

Stationary probability in an M/M/$1$ queue with a lazy server

Customers arrive to a single server queue according to a Poisson process with rate $\lambda$. Each customer requires Exponential($\mu$) service time. In the beginning when there are $0$ ...
5
votes
1answer
152 views

Conditions for birth and death process having only finitely many deaths.

Consider a birth and death process on $\mathbb{N}=\left\{0,1,2,\ldots\right\}$, given by the transition probabilities $p(n,n+1)=\lambda_n$ and $p(n,n-1)=\mu_n$ (those are the birth and death rates, ...
1
vote
1answer
38 views

Determining invariant probability measure and calculating $\lim_{n}p_{ij}^{(n)}$

Consider the Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E=\left\{1,2,3\right\}$ and transition matrix $$ P=\frac{1}{2}\begin{pmatrix}0 & 1 & 1\\1 & 0 & 1\\1 ...
1
vote
0answers
25 views

Checking the closeness of probability distributions

Suppose I have a Markov chain that satisfies all the conditions of ergodicity and has a stationary distribution pi. I want to find the time when the probability distribution of the markov chain is ...
0
votes
1answer
73 views

Calculating the probability in $m$ steps of a Homogeneous Markov Chain

I have the next problem: Consider a homogeneous Markov chain $\{X_n: n = 0,1,2, ... \} $ with state space $E = \{0,1,2, ... \} $, with the following transition probabilities where $ 0 <\theta ...
1
vote
2answers
87 views

Entropy of a Markov chain (right result?)

Consider the Markov chain with state space $E=\left\{0,1,2,3,4,5,6\right\}$ and transition matrix $$ \begin{pmatrix}1/5 & 3/5 & 0 & 0 & 1/5 & 0 & 0\\0 & 0 & ...
1
vote
1answer
96 views

Bound spectral radius of a certain matrix.

Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi = \text{diag}(\xi)$ to be a diagonal matrix with a principal left eigenvector $\xi$ of $P$ (i.e. ...
0
votes
2answers
55 views

Does the function of a random variable have the same transition matrix as the variable itself?

If I have a variable X, that follows a Markov Chain with a transition density $\rho(X)$ does a function of that variable f(X) have the same density or is there a one to one mapping to the density of ...
4
votes
1answer
122 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 ...
1
vote
1answer
76 views

Simple Markov Chain: Random Walk on $\mathbb{Z}$

We are given a random walk on $\mathbb{Z}$, where $p_{i, i+1}= p < \frac{1}{2}$ and $p_{i,i-1}=1-p > \frac{1}{2}$, starting at $0$. Now we have to compute the probability that we eventually ...
1
vote
1answer
48 views

Prove a certain matrix is positive semidefinte.

Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi$ to be a diagonal matrix with a principal left eigenvector of $P$ on the main diagonal and zeros ...
1
vote
1answer
25 views

Interval of probabilities which satisfy a Markov chain

Given the following markov chain, where T1 is the start state, the labels are shown on the state( 'a' in this case) and p and 1-p are probabilities for that transition happening: Now, for what ...
0
votes
0answers
36 views

What is the limiting distribution of this Markov Chain?

Take a Markov Chain with state space $\left\{ 0, 1, \dots, 20 \right\}$. Then we have the rule that given $X_n$: Compute $Z = X_n + 1$ or $Z = X_n - 1$ with probability $\frac{1}{2}$ each (if the ...
1
vote
1answer
952 views

Markov Chain Expected value

Let $(X_n)_{n\in\mathbb{N}}$ be a Markov chain with State space $E=\{1,2,3\}$ and transission matrix $$P=\begin{bmatrix} 0 & 1/3 & 2/3 \\ 1/4 & 3/4 & 0 \\ 2/5 & 0 & ...
1
vote
1answer
56 views

Does the steady state distribution of a Markov chain change, when minimizing it?

Say I have this Markov chain. Then I perform bisimulation on it, where I find the largest relation between the states of the Markov chain. Finally I can construct a bisimulation quotient/minimization ...
0
votes
1answer
45 views

Markov Chain Expected Value notation.

I have question to answer regarding $X_n$ where $X_n$ is a Markov chain, $n$=$0$,$1$,$2$,... I am loking for What I don't understand is what this $3$ on $X_{n+1}$ is! Any ideas?
1
vote
1answer
114 views

Is this stochastic process a Markov chain?

I have been struggling sometime now with the following question and I feel like I am stacked. Let $X_n : n= 0,1,\ldots$ be a sequence of iid discrete random variables with $$P(X_n=j)=a_j>0 \qquad ...
2
votes
1answer
250 views

A Markov Chain Flea Problem

A Flea moves around the vertices of a triangle in the following manner: Whenever it is at vertex i it moves to its clockwise neighbor vertex with probability $p_i$ and to the counterclockwise neighbor ...
1
vote
1answer
237 views

variance of number of steps in markov chain (rook move to top right)

I encountered this problem while studying Markov chains and I want to calculate the variance of the problem, i.e. variance of number of steps that a random walker rook make to reach from down-left ...
1
vote
1answer
299 views

Gambler's ruin and Markov Chain, coin toss and stakes

I'm considering a classical problem about Markov Chains: A gambler has $£8$ and wishes to get to $£10$. A coin is tossed repeatedly : if it comes down tails, the gambler loses his stake, and if it ...
4
votes
1answer
192 views

A die whose score cannot be as before (Markov chains)

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 probability $1/5$. Given that the first score is 6, what is the probability ...
2
votes
2answers
254 views

Markov Chain: Moving on a circle

A particle moves on 12 points situated on a circle. At each step it is equally likely to move one step in the clockwise or in the counterclockwise direction. Find the mean number of steps for ...
0
votes
1answer
47 views

Expected number of visits to a state of a Markov chain up to a certain time

Let $P=\{p_{ij}\}$ be a stochastic matrix (with rows and columns indexed by a countable set) and let $p^{(k)}_{ij}$ be the entries of $P^k$. I'm trying to prove that, if the associated Markov chain is ...
0
votes
1answer
77 views

Understanding steady state distribution

I need some help verifying that my understanding of steady state distribution is indeed correct. I have a transition diagram (model). With around 100 states and 6 variables. I have used a software ...
0
votes
1answer
29 views

Markov Chains (State transitions)

I was wondering which part I am misunderstanding about the individual-by-individual updating scheme from the book of Jackson M. (Social and Economic Networks, 2008) . The full transition matrix in the ...
1
vote
2answers
70 views

Given a Markov chain $X \rightarrow Y \rightarrow Z$, why is $I(X;Y|Z) \leq I(X;Y)$?

A Markov chain $X \rightarrow Y \rightarrow Z$ is given, where $X,Y,Z$ are random variables characterized by the probability distribution $p(x,y,z) = p(x)p(y|x)p(z|y)$. It follows that $I(X;Y) \geq ...
0
votes
1answer
56 views

Markov chain: if $X\rightarrow Y\rightarrow Z$, then why is $Z\rightarrow Y\rightarrow X$ true?

in a Markov chain, given three random variables $X,Y,Z$, we have $X\rightarrow Y\rightarrow Z$, which means $p(x,y,z) = p(x)p(y|x)p(z|y)$. The right arrow symbol $\rightarrow$ is used to denote a ...
2
votes
0answers
17 views

Monte Carlo Markov Chain Simulation Issues

The Markov Chain is uniformly distributed across all $50$x$50$ matrices of entries $0$ and $$1 with no neighboring $1's$. I am supposed to run a MC simulation to check the probability that the ...
0
votes
1answer
27 views

Markov Chain (Learning)

If I have a Matrix like the one below, what is the probability $p_t$ that at a certain time $t$, we are still not able to arrive at state $z$ $$ \begin{array}{c|lcr} \text{States} & x & y ...
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 ...
1
vote
0answers
131 views

Random Walk, Markov Process

I'm stuck on a homework question and am wondering if anyone can offer some hints. Suppose we have some straight line graph G over the set $ V = \{1, 2, 3, ... , n\} $ of vertices, with an edge between ...
2
votes
1answer
129 views

Finite state Markov chain

Under what conditions a Markov chain can be considered as finite (and not infinite)? Thank you!
0
votes
0answers
46 views

Did I show correctly that $0$ is null recurrent or did I produce nonsense?

Suppose that you have a Markov chain with state space $E$ containing $0$. Assume that $$ p_{00}^{(2n)}=\binom{2n}{n}\left(\frac{1}{2}\right)^{2n-1}~~~\text{ and ...
1
vote
1answer
139 views

How to show positive recurrence/ null recurrence?

Suppose that you have a Markov chain with state space $E$ containing $0$. Assume that $$ p_{00}^{(2n)}=\binom{2n}{n}\left(\frac{1}{2}\right)^{2n-1}~~~\text{ and ...
0
votes
1answer
57 views

Recurrence Equation and Markov Chain: How to get the base case

I established the reccurence equation for a Markov Chain but are not able to finde the base cases. We are interested in whether the sum of $t$ throws of a fair die is divisible by $k$ for some $k ...
1
vote
2answers
938 views

Finding steady state probabilities by solving equation system

(I know that there are numerous questions on this, but my problem is in actually solving the equations, which isn't the problem in other questions.) I'm trying to figure out the steady state ...
0
votes
1answer
53 views

Likelihood of a function of different types of random variables

Is there a general way of expressing the likelihood of some known, but non-trivial function of several random varaibles. For example, suppose that we need to calculate the parameters of a process ...
2
votes
0answers
29 views

The independence of random variables

Here is my question: Consider a homogeneous ergodic Markov chain on a finite state space $X=\{1,\ldots,r\} $. Define the random variables $\tau_n \,,n\ge1$ as the consecutive times when the Markov ...
0
votes
0answers
488 views

Random walk on infinite binary tree (recurrence, transience)

Consider a random walk on the infinite binary tree with root $x$ which has the following transition probabilities. $$ p_{x,0}=p_{x,1}=\frac{1}{2},~~~p_{y,y0}=p,~~~p_{y,y1}=q,~~\text{and ...