How to write this Markov chain problem in a transition probability matrix form

markov chainsprobabilitytransition matrix

Mister X has a memory problem.Every night he forgets some people that he knows. More specifically, if he remembers $i$ people before he goes to sleep, the next morning he might remember $0,1,2,\dots,i$ persons each with probability $\frac{1}{i+1}$. The doctor that watches him, learns him every day a new person, different from the other persons that Mister X knows up until that time.

If we let $X_{n}$ the persons which he remembers the night of the $n^{th}$ day, the state space of the markov chain to be $\mathbb{N}=\{1,2,\dots\}$ with first order probabilities : $$p_{k,1}=\dots=p_{k,k+1} = \frac{1}{k+1}, \forall k \in \mathbb{N}.$$

If the night of any day he remembers $k$ persons, the next day he knows one more (from the doctor) and still remembers $ m \in \{0,1,\dots,k \}$ from the previous day. In total he remembers $m+1$ persons with probability that he remembers $m$ persons from the previous day, i.e $\frac{1}{k+1}$.

The chain is irreducible because all states $k<m$ communicate each other and all the states communicate with state 1 with one step with probability $\frac{1}{k+1}$.And from state 1 to state $k$ with $k-1$ steps with probability $\frac{1}{k!}$.

The stationary distribution of the chain is :$$\pi(n) = \sum_{k=0}^{\infty} p(k,n)\pi(k)= \frac{1}{e}\frac{1}{(n+1)!}$$

Is there a way of creating a transition probability matrix for this problem ?

My effort:

$$\mathbf{P} = \begin{pmatrix}
0 & 1 & 0 &0 & 0&\dots\\
2/3 & 0 & 1/3 & 0 & 0 &\dots\\
3/4 & 0 & 0 & 1/4 & 0&\dots\\
4/5 & 0 & 0 & 0 & 1/5&\dots\\
5/6 & 0 & 0 & 0 & 0&\dots\\
\vdots &\vdots & \vdots &\vdots & \vdots &\vdots\\
\end{pmatrix}$$

Best Answer

If you are currently in state $i$, then the $i$'th row of the transition matrix tells you in which state you will be the next day. If $i=1$, then the next day will be either $i=1$ (remembering $0$, learning $1$ new) or $i=2$ (remembering $1$, learning $1$ new), both with probability $1/2$. There is zero probability to reach anything higher (in this one step). Therefore the first row of the matrix should be $$\begin{pmatrix}1/2 & 1/2 & 0 & \dots \end{pmatrix}.$$ Similarly, starting at $i=2$, the next day will be at $i=1,2,3$, all with equal probability $1/3$, so the second column is $$\begin{pmatrix}1/3 & 1/3 & 1/3 & 0 & \dots\end{pmatrix}.$$

Continuing this process yields: $$\mathbf{P} = \begin{pmatrix} 1/2 & 1/2 & 0 &0 & 0&\dots\\ 1/3 & 1/3 & 1/3 & 0 & 0 &\dots\\ 1/4 & 1/4 & 1/4 & 1/4 & 0&\dots\\ 1/5 & 1/5 & 1/5 & 1/5 & 1/5&\dots\\ \vdots &\vdots & \vdots &\vdots & \vdots &\\ \end{pmatrix}$$

Hope this helps.

Note: there are different conventions on how to write the transition matrix. Some literature will have rows/columns switched, which means the matrix is simply transposed. I have written this in a way that matches your formula for the stationary distribution.

Related Question