Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [markov-chains]

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.

A Markov chain is a stochastic process on a discrete (finite or countably infinite) space in which the distribution of the next state depends only on the current state. These objects show up in probability and computer science both in discrete-time and continuous-time models. For Markov processes on continuous spaces please use .

A discrete-time Markov chain is a sequence of random variables $\{X_n\}_{n\geq1}$ with the Markov property, namely that the probability of moving to the next state depends only on the present state and not on the previous states, i.e. $$\mathbb P(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\mathbb P(X_{n+1}=x\mid X_{n}=x_{n}),$$ if both conditional probabilities are well defined, i.e. if $\mathbb P(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.$

5938 questions
3
votes
1 answer

Rational Thief Problem, optimal stopping strategy

A thief goes out stealing every day and has a chance of $p_j$ of stealing a sum $j$ with $0\leq j \leq N$. But there's also a chance $p$ of getting caught, in which case he loses everything he got until that moment. When should he stop stealing? The…
markovman
  • 77
2
votes
1 answer

Discrete-time random process is Markov iif... (Proving a theorem)

First some background: We say that $(X_n)_{n\geq 0}$ is a Markov chain with initial distribution $\lambda$ and transition matrix $P$ if (i) $X_0$ has distribution $\lambda$; (ii) for $n\geq 0$, conditional on $X_n=i$, $X_{n+1}$ has distribution…
user34632
2
votes
2 answers

finding the generating function $\phi(s) = \mathbb{E}(s^{H_0})$.

i just started the course of markov chains and i'm having a few problems with one of the excercises. Let $Y_1,Y_2, \dots$ be i.i.d random variables with: $\mathbb{P}(Y_1 = 1) = \mathbb{P}(Y_1 = -1) = \frac{1}{2}$ and set $X_0 = 1, X_n = X_0 + Y_1+…
Kees Til
  • 1,958
2
votes
1 answer

Markov Property as given in Norris' book on Markov chains vs standard formulation

In the book, Markov Chains, the following theorem is mentioned: Let $(X_n),n≥0$ be Markov$(λ,P)$. Then, conditional on $X_m=i,(X_{m+n})_{n≥0}$ is Markov$(\delta_i,P)$ and is independent of the random variables $X_0,\dots,X_m$. This is proved by…
Philip
  • 79
2
votes
1 answer

Random walk on connected graph: show $E_vT_w \ne E_wT_v$

Let $G$ be a connected graph on at least 3 vertices in which the vertex $v$ has only one neighbor, namely $w$. Let $(X_t)_{t \ge 0}$ be a simple random walk on $G$, where $X_t$ is the current vertex at time $t$. Show   $$E_vT_w \ne E_wT_v$$ where…
user14108
2
votes
1 answer

Proving that a HMC state is recurrent or transient?

Looking at the HMC $$\begin{bmatrix} 1-\alpha & \alpha \\ 0 & 1 \end{bmatrix} $$ How do I prove that the state 2 is recurrent and that state 1 is transient? What does it actually mean by state 1 and state 2? Thanks for any guidance
Sarah Jayne
  • 563
  • 2
  • 17
2
votes
0 answers

How to solve this simple 2D Markov chain

I have 2D Markov chain like below : I have already solved for $p_{b,0}$ and $p_{0,d}$ like this : $$p_{b,0} = \rho^bp_{0,0}$$ $$p_{0,d} = \rho^dp_{0,0}$$ But I don't know how to get $p_{b,d}$. So far I know that…
bnbfreak
  • 219
2
votes
2 answers

A Card game problem related to Markov chain

This card game problem originates from the killer game Sanguosha. We assume that all cards drawn in the game procedures below are with replacement, in order to keep the probabilities fixed when a card is drawn. The game procedure: Draw a card from…
ferrarisf50
  • 21
2
votes
2 answers

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain?

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain? My attempt: Consider the case, $P(Y_{n+1}=3|Y_n=1)=\frac{1}{6}$ if the current maximum is bigger than 3, but $P(Y_{n+1}=3|Y_n=1)=0$ if…
Yellow Skies
  • 1,710
2
votes
1 answer

$\psi$-irreducibility of m-skeletons.

In Proposition 5.4.5 of Meyn and Tweedie's Markov Chains and Stochastic Stability, it is said that if a chain $\Phi$ is $\psi$-irreducible and aperiodic, then every $m$-skeleton of it is also $\psi$-irreducible and aperiodic. The authors did not…
942kid
  • 21
  • 1
2
votes
0 answers

Irreducible Markov: harmonic function based on stationary distribution

Let $P$ be the transition matrix of an irreducible Markov chain on a finite state space $\Omega$. Let $\pi_1$ and $\pi_2$ be two stationary distributions for $P$. Is the function $$h(x)={\pi_1(x) \over \pi_2(x)}, x \in \Omega $$ harmonic for $P$. I…
user14108
2
votes
1 answer

Random walk with single absorbing boundary

There is a random walk on a linear lattice of size $\{0,N\}$, where $0$ is the origin and a reflecting boundary and $N$ is the absorbing boundary. It moves forward or backward one step at a time with $\frac12$ probability. The number of times a…
dexter
  • 45
2
votes
1 answer

Markov Chains- Show state is recurrent

Q's: I suspect this is true: if two states in a markov chain communicate and one is recurrent, then the other is recurrent. My approach is, lets say i and j are two states that communicate and as i is recurrent, this means you are guaranteed to…
Raul
  • 938
2
votes
1 answer

Markov chains: simple random walk $S_n$

In the case of a simple random walk $\{S_n, n \ge 0\}$ what is $S_n$. I see this for $P\{S_n=i |\ |S_n|=i_{n-1},...,|S_1|=i_1 \} = \frac{p^i}{p^i+q^i}$ What does this mean? is it: the probability of going to state i after n steps (not sure about…
knk
  • 359
  • 4
  • 16
2
votes
2 answers

Markov chain: closed, finite classes are recurrent?

In Norris: Markov Chains the closed class C is defined as one for which $i\in C$ and $P_i(X_n=j \text{ for some }n\ge0)>0$ implies that $j\in C$. Here's theorem 1.5.6 from the book with proof Every finite closed class is recurrent. Proof: Suppose C…
adamG
  • 665
  • 1
  • 10
  • 23
1 2 3
…
30 31