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
2
votes
1 answer

Using Strong Markov Property

Let $X_n$ be a DTMC, with transition matrix P and state-space I. Let $Y_m=X_{T_m}$ for $m \in \mathbb{N}$. Define $T_0=\inf\{n\geq0:X_n\in J\subset I\}$ and $T_{m+1}=\inf\{n> T_{m}:X_n\in J\subset I\}$. These are stopping times, so we can use the…
An old man in the sea.
  • 5,241
2
votes
1 answer

Interpretation for squared Markov kernel?

Assume a Markov chain on a measurable state space $(E,\Sigma)$ is given, denoted by $(X_n)_{n\in \mathbb{N}}$ with Markov kernel $p$ and stationary measure $\mu$. In this case, we have $$ \mathbb{P}[X_0 \in A , \, X_1 \in B] = \int_A p(x,B) \,…
Adam
  • 3,679
2
votes
1 answer

Why is the movement of a Chess King aperiodic?

Imagine we have a king by itself on a chess board, making random moves around the board. Although it is apparently aperiodic, wouldn't the corresponding Markov chain to the King's movements be periodic since the King could only return to a square i…
zthomas.nc
  • 427
2
votes
1 answer

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 of flips until one of them runs out of money? So I…
Saketh Malyala
  • 13,637
2
votes
1 answer

Algorithm for identifying Markov chain communicating classes

Let $P$ be a transition matrix of a time-homogeneous Markov chain with at least one closed communication class. Is there an algorithm / optimization problem that outputs the identification of the communication classes? For example, if…
yoki
  • 1,431
2
votes
3 answers

Aperiodicity of Markov chain

If a markov chain which has many states but only one state has a self-loop edge, then does it mean that the markov chain is aperiodic? Or every state in the markov chain has to have self-loop? For instance, in the following markov-chain, only state…
John Miller
  • 23
2
votes
1 answer

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 square of a chess board to the top-right square for…
Mahdi Dolati
  • 48
2
votes
0 answers

Find condition on $X$ so that $P(\exists n\in\mathbb{N}: N_n=0)=1$

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. $X$ is identically distributed as all $X_{n,k}$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ if…
Salamo
  • 1,094
2
votes
1 answer

Find conditions on the distribution on $X$, but what is meant by $X$?

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ if }N_{n-1}=0\\X_{n,1}+\cdots+X_{n,N_{n-1}}, & \text{ if…
Salamo
  • 1,094
1
vote
1 answer

Show that $\mathbb{P}((X_{n+1},...,X_N)\in F|X_n\in A, (X_{n-1},...,X_0)\in G)=\mathbb{P}((X_{n+1,}...,X_N)\in F|X_n\in A)$

In our reading we had the following Theorem concerning Markov chains: Take $0
mathfemi
  • 2,631
1
vote
1 answer

Which of the following processes are Markov chains?

A dice is thrown an infinite number of times. Which of the following procsses are Markov chains or not? Justify your answer. For those processes that are Markov chains give the transition probabilities. For $n\in\mathbb{N}$ consider (1) $U_n$ to be…
mathfemi
  • 2,631
1
vote
1 answer

Demonstrate that is a Markov Chain

I've got a box with 10 balls inside, 5 reds 5 blacks. Every step i take a ball. If it is black i hold it out, if it is red i put all the blacks ball that are out and the red one inside the box. Called $X_{n}$ the number of balls that are outside the…
user22849
  • 131
1
vote
1 answer

Law of Total Probability in Markov Chains

I'm reading about Markov Chains and have come across the following: $ P_x (X_2 = y) = \sum\limits_{z\in \mathbb S} P_x (X_1 = z).P_x(X_2 = y|X_1 = z) $ where $ P_x (X_1 = z) = p(X_1 = z|X_0 = x) $ which is obtained through the law of total…
user131983
  • 445
1
vote
2 answers

$(S_0+\ldots + S_n)_{n\geq 0}$ not a Markov chain

Assume that $Y_0,\ldots , Y_n$ are independent random variables with the following identical distribution: $Y_i=1$ with propability $p$ and $Y_i=0$ with propability $1-p$. Also set $S_0=0$ and $S_n=Y_0+\ldots + Y_n$. It's quite trivial that…
Sertii
  • 109
  • 7
1
vote
0 answers

Cereal boxes - Mean time spent in transient states

Problem: A cereal company gives 2 images in each cereal box it has. There are a total of 5 images. Once a buyer have 5 images she wins a prize. No box contains 2 images that are the same. What is the expected value of the number of packages you'll…
jacob
  • 2,965
1 2 3
…
30 31