Determing a transition probability matrix

Question

I need some support with this homework exercise: An urn contains at most $N$ balls. Let $X_n$ be the number of balls in the urn after the $n$-th execution of the following procedure: If the urn is not empty, we take a ball and flip a coin, having a probability $p =1/2$ of landing with heads. If heads appears, we put the ball back into the urn, otherwise not. If the urn is empty, we flip a coin again and if heads appears, the urn remains empty, ortherwise we fill the urn with $N$ balls.

The goal is to describe this game with a Markov chain and to determine the transition matrix. How is $X_n$ for $n \in \mathbb{N}$ distributed?

My approach:

Concerning the transition probablities, I am having a hard time to unterstand this. I know that we have to consider the urn for $n$, $0 < n < N$ and for $N$ balls...

Can anyone help me?

Answer 1

The transition matrix is an $N \times N$ matrix given by

$\mathbf{P} = \begin{pmatrix} 1/2 & 0 & 0 & \cdots & 0 &1/2 \\ 1/2 & 1/2 & 0 &\cdots &0 &0 \\ 0 & 1/2 & 1/2 & \cdots &0&0 \\ \vdots & & \ddots & \ddots && \vdots \\ \vdots &&&\ddots&\ddots &\vdots\\ 0 & \cdots & \cdots &0&1/2&1/2\end{pmatrix} \\$

Then $X_n$ has the distribution given by the row vector $\mathbf{\pi} \cdot \mathbf{P}^n$ where $\mathbf{\pi}= \begin{pmatrix} \pi_0 & \pi_1 & \cdots & \pi_N \end{pmatrix}$ represents the distribution for the starting state. i.e. you interpret that there are $i$ balls in the urn when you start with probability $\pi_i$.

Answer 2

If there are currently $0$, then you either go to $N$ with probability $1/2$ or stay at $0$ with probability $1/2$.

If there are currently $0<n\leq N$, then you either go to $n-1$ with probability $1/2$ or stay at $n$ with probability $1/2$.

(I honestly don't know how to give just a hint for this part, since I basically just read off the content of the question.)

From there you can assemble the transition matrix; I use the convention that $P_{ij}$ is the probability to go from $i$ to $j$, and write it for $N=4$, where the states are $0,1,\dots,4$.

$$P=\begin{bmatrix} 1/2 & 0 & 0 & 0 & 1/2 \\ 1/2 & 1/2 & 0 & 0 & 0 \\ 0 & 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 0 & 1/2 & 1/2 \end{bmatrix}.$$

Again, this is just organizing the information. The pattern will continue like this as you increase $N$; only the first row breaks the pattern (since the urn is completely filled when it is empty and the appropriate flip occurs).