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

0
votes
0answers
37 views

Definition of Past in Markov Property

Usually in textbooks, the definition of the Markov Property reads as: \begin{equation} P(X_n\leqslant x_n|X_{n-1}\leqslant x_{n-1},...,X_{0}\leqslant x_{0})=P(X_n\leqslant x_n|X_{n-1}\leqslant x_{n-1}...
0
votes
1answer
37 views

A cycle of an irreducible Markov chain

Suppose we have a discrete-time Markov chain with $n$ states, with transition matrix $P$. The definition of irreducibility tells us that for any two states $x$ and $y$, there exists an integer $t$ ...
1
vote
1answer
60 views

Prove that this Markov chain is irreducible if and only if there exist infinitely many $k\geq0$ such that $q_{k}>0$

We consider the Markov chain $\left(X_{n}\right)_{n\geq0}$ on $\mathbb{N}$ whose transition matrix $P=\left(p_{k,l}\right)_{k,l\geq0}$ given by $$\forall k\in\mathbb{N} p_{k,k-1}=q_{k},p_{k,k+...
0
votes
1answer
70 views

Gambler's Ruin with changing probabilities

I have the following Markov Chain and am trying to evaluate the probability that the Chain reaches state 4 before it returns to state 1, given it starts in state 1. I've seen many typical problems ...
1
vote
1answer
70 views

A tricky conditional probability question on Markov chains

Let $X_1,X_2,\ldots,X_n$ be a time-homogeneous discrete-time ergodic Markov chain on a finite state space $\mathcal{S}.$ You can assume stationarity and time-reversibility as well, if you like. Fix $...
1
vote
0answers
42 views

Euler-summability of a convergent sequence and its limit

In the book Finite Markov Chains by John G.Kemeny and J.Laurie Snell, the authors introduce the following concept of Euler-summability of a sequence: Having a sequence $(s_n)_{n \geq 0},$ we ...
2
votes
1answer
105 views

Markov chain with infinitely many states

I am stumped on the following infinite Markov Chain. Given the this transition matrix for a Markov chain, how do I determine what values of $x$ the chain is positive recurrent/null recurrent/...
0
votes
1answer
154 views

How to compute transition matrix for the following Markov chain?

Each morning a runner leaves his house and goes for a jog. He is equally likely to leave either from his front or back door. Upon leaving the house, he chooses a pair of sports shoes (or goes for a ...
0
votes
1answer
24 views

Explicit transition matrix

An urn $U$ contains always $N$ balls, some white and some black balls. Fix $p \in ]0,1[$; at each stage a coin having probability $p$ of landing heads is flipped. If heads appear, then a ball is ...
0
votes
0answers
23 views

Metropolis algorithm and formula

In the article by M. Creutz and B. Freedman "Statistical Approach to Quantum Mechanics" authors provide a formula for Metropolis algorithm: $$ W(x_j, x'_j) = \frac{1}{N_0} \left( \theta \left[ S(x_j) ...
1
vote
1answer
65 views

An elementary question on Markov chain

We consider the Markov chain $\left(X_{n}\right)_{n\geq0}$ on $\left\{ 1,2,3,4,5\right\}$ with transition matrix $P=\left(\begin{array}{ccccc} 1/2 & 1/2 & 0 & 0 & 0\\ 1/2 & 1/...
3
votes
1answer
116 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 X}$....
0
votes
1answer
159 views

Finding steady state vector

When I see examples of getting the steady state vector with markov chains, the sum of each column or row is usually one, but it isn't in my case. What do I do then? If I have a $3\times 3$ matrix ...
11
votes
1answer
143 views

Can there be a Diaconis-Shahshahani Upper Bound Lemma for Compact Groups?

Let $G$ be a finite group and $\nu\in M_p(G)\subset \mathbb{C} G$ a probability measure on $G$ and let $\pi$ be the uniform distribution on $G$. Denote by $d_\rho$ the dimension of a non-trivial ...
2
votes
1answer
64 views

Gambler's Ruin Duration with 10 Chips, 50% Chance of Ruin

Abraham and Blaise each have $\$10$. They repeatedly flip a fair coin. If it comes up heads, Abraham gives Blaise $\$1$. If it comes up tails, Blaise gives Abraham $\$1$. What is the expected number ...
0
votes
1answer
46 views

Markov processes: Hitting times for a point form an i.i.d. sequence

Say that I have a recurrent time-homogenous diffusion process X (continuous strong markov process) and two points $x,y$. If $X_t$ goes from $y$, to $x$ and then back to $y$ again we denote it as a "...
2
votes
0answers
21 views

a conceptual question on markov chain [duplicate]

Suppose $\{X_n,n\ge 0\}$ and $\{Y_n,n\ge0\}$ are two independent discrete-time markov chains (DTMC) with state space $S=\{0,1,2,\ldots\}$. Prove or give a counterexample to: $\{X_n+Y_n,n\ge 0\}$ is ...
0
votes
0answers
28 views

How to Compute Distributions in Hidden Markov Models?

Let $Z_1, Z_2, ..., Z_n$ be the latent variables, and $X_1, X_2, ... X_n$ be the observed ones in a hidden Markov models. Let's assume that the parameters of the hidden Markov models are known: the ...
2
votes
1answer
73 views

Error in Billingsley?

Problem 8.25 in the third edition of Probability and Measure by Billingsley (1995, p. 142) is as follows: Suppose that an irreducible [Markov] chain of period $t>1$ has a stationary ...
0
votes
0answers
29 views

Difference between AR model and Markov Chain

We know that Markov Chain can be represented as $$x_t=ax_{t-1}+\epsilon_t,$$ where $\{x_t\}$ are states, $\epsilon$ is noise, and $a\neq 0 \in R$. For the AR model, we know that, the first order ...
-1
votes
1answer
71 views

How many steps would it take to get to the top of this staircase?

There are 26 steps in a staircase. You have a 51% chance to step onto the next step, and a 49% chance to step back down to the step prior. Assuming you are already on the first step, how many steps ...
0
votes
1answer
22 views

Find $P(\eta_t=m)$, $m=0,1,2,\dots,$

Let $\epsilon_t$, $t=1,2,\dots$ independent random variables with $P(\epsilon_t=1)=p$ and $P(\epsilon_t=-1)=1-p$. If $\eta_0=0,\eta_t=\eta_{t-1}+\epsilon_t$ , $t=1,2,\dots$ where $\eta_t$ is ...
4
votes
2answers
114 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 ...
0
votes
0answers
28 views

Can an irreducible, recurrent continuous time Markov chain have spontaneous states?

Let $(X_t)_{t\geq0}$ be a continuous time Markov chain on some (possibly countably infinite) state space $S$ with Q-Matrix $q(\cdot,\cdot)$, transition function $p_t(\cdot, \cdot)$ and invariant ...
0
votes
1answer
94 views

Combinatorics Statistics Probability of a Letter Chain

What formula could help me quantify the probability of a chain of three letters (English Alphabet) where each letter is based on the previous one (stochastic modeling, Markov-chains, probabilities) ...
0
votes
0answers
21 views

Metropolis Markov Chain and Mixing Time

I have a statistical mechanical system, which I would like to sample with the Gibbs distribution using a Metropolis-Markov chain. I think the following are standard questions, but I am not sure what ...
1
vote
1answer
77 views

Show that if $\{X_n\}$ is a Markov Chain

Show that, if $\{X_n\}$ is a Markov Chain then $$P(X_n=j\mid X_k=l,X_m=i)=P(X_n=j\mid X_m=i),0\leq k<m<n$$ What I did is $$P(X_n=j\mid X_k=l,X_m=i)=\frac{P(X_n=j,X_k=l,X_m=i)}{P(X_k=l,X_m=i)...
2
votes
0answers
21 views

How to compute Generalized Group Inverse?

Given a transition matrix $P \in \mathbb{R}^{n \times n}$, i.e. $\sum_j P_{ij} = 1$ and $P_{ij} \geq 0$ for all $i,j$. One can show that there exists a unique group inverse $B$ of $A:= I - P$ which ...
1
vote
0answers
26 views

How to write spectral form of probability matrix

I am trying understand Markov chain in genetics process. In book that I am using (Mathematical Population Genetics) (pag 87): (P is matrix transition probability). $E_0$ and $E_M$ are absorbing ...
2
votes
1answer
35 views

Survey on large deviation bounds of queuing delay in CSMA scheduling

I am trying to do some literature survey on the theoretical guarantees in uplink scheduling algorithms. I found there exist a series of papers from UIUC and UC Berkeley by L.Jiang, J. Walrand, R. ...
1
vote
1answer
169 views

Population exercise with Markov chains

I am totally stuck with this exercise on Markov chains. Maybe someone can help me :). Red and green bacteria A growth medium at time $t = 0$ has 500 red bacteria and 500 green bacteria. Each ...
2
votes
2answers
84 views

Markov chains and conditioning on impossible events

Consider a Markov chain $(X_0,X_1,\ldots)$ with a state space $S\equiv\{s_1,s_2\}$ and the following matrix of “transition probabilities” (I will explain the use of quotation marks below): \begin{...
0
votes
2answers
41 views

Markov chain periodicity

Can a Markov chain have 5 states, one open and one closed class and all the states be periodic (e.g. period 2)? I tried the following: https://www.dropbox.com/s/v818oqlizaci23m/Untitled.png?dl=0 but ...
2
votes
1answer
98 views

Stationary distribution in continuous-time Markov chain

Consider a barbershop with one barber who can cut hair at rate 4 (people per hour), and three waiting chairs. Customers arrive at rate 5 per hour. Customers who arrive to a fully occupied shop ...
1
vote
0answers
41 views

Interpolation of random processes

Let $\left(\Omega, \mathcal{F}, \left\{\mathcal{F}_{t}\right\}_{t\geq 0}, P \right)$ be a complete probability space with a nondecreasing family of right continuous sub-$\sigma$-algebras $\mathcal{F}$...
1
vote
0answers
70 views

Markov Chain- Internet Router Buffer

At each time slot, a router's buffer receives a packet with probability $p$, or releases one with probability $q$, or stays the same with $r$. Initially empty, what is the distribution of the packets ...
2
votes
0answers
195 views

How to Derive Gibbs Sampling Update Formula for Hidden Markov Model?

I want to understand how to derive the update formula for Gibbs sampling for Hidden Markov Model, for example, in here: $$p(z_t | \mathbf{x}, \mathbf{z}_{\setminus t}, \boldsymbol{\alpha}, > \...
2
votes
0answers
11 views

The restriction of the green function is non-degenerate

On the context of irreducible Markov chains on a finite graph one defines $$G = \sum_{k=0}^\infty \hat{Q}^k $$ where $\hat{Q}$ is the restriction of a stochastic matrix to a subset (one can think ...
0
votes
1answer
30 views

What is the practical meaning of probability vectors?

I have been reading a lot about probability vectors, as a part of "Introduction to Probability" course. Now, whenever it was mentioned, it was defined theoretically as a vector whose entries add up to ...
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 ...
0
votes
1answer
40 views

What is wrong with matrix [[1,.5,0] [0,0,0] [0,.5,1]] steady state?

I know that Markov matrices have steady state since they always have eigenvalue $\lambda = 1$. We just solve the system of equations $A\vec x = 1 \cdot \vec x$ or $$\begin{cases} k_{a\to a} a + k_{b\...
1
vote
0answers
46 views

Transition density of an AR(1) process?

If we have an AR(1) process, i.e: $X_{t+1} = \alpha X_t + e_{t+1}$ with $X_0=0$ then what is its Markov Chain transition density? We know that for a Markov chain, the following holds: $P(X_{t+1}\leq ...
1
vote
0answers
46 views

Relaxation time and Mixing time of Markov chains

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer. Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
1
vote
1answer
119 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
-1
votes
1answer
74 views

Billingsley Exercise 8.8 (Markov Chains)

I am studying from Billingsley and would like some hints on the following exercise. Suppose $S = \{0,1,2,...\}$, $p_{00} = 1,$ and $f_{i0} > 0$ for all $i$. Here, $S$ represents the state ...
7
votes
1answer
252 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
1
vote
2answers
221 views

When to stop checking if a transition matrix is regular?

The definition that I have of a Transition Matrix for a Markov Chain is: A transition matrix is regular if some power of it is positive. Doesn't this mean though that in theory, you could keep ...
0
votes
1answer
125 views

Expected time until reaching absorbing state of Markov chain

I currently try to model nucleation as an absorbing Markov chain. I have an idea how to do that but, however, I cannot convince myself that it is correct. The state space consists of the number of ...
0
votes
0answers
26 views

Reference for General state space Markov chain

What is a good reference for general state space Markov chains? Is there a reference which assumes only familiarity with finite/countable state space Markov chains and then extends the results (e.g., ...
1
vote
2answers
58 views

Confusion regarding Burke's theorem

Arrivals occur at rate $\lambda$ according to a Poisson process the service time have an exponential distribution with parameter $1/\mu$ in an M/M/1 queue, where $\mu$ is the mean service rate where $\...