I have two urns A and B containing a total of N balls. An experiment is performed where a ball is selected at random (all selections equally likely) at time t(t=1,2,…) from the totality of N balls. Then an urn is selected at random (A is chosen at probability p and B at probability q) and the ball previously drawn is placed in this urn. The state of the system at each trial is represented by the number of balls in A. How would I determine the transition probability matrix?
[Math] Urn Problem-Determining the Transition Probability Matrix
markov chainsmarkov-processstochastic-analysis
Related Solutions
Yes, this is a Markov chain
The state of the system is defined by the number of white balls in the first box.
There are four states:
The figure above depicts both boxes the left one being the one in which we count the white balls.
Based on the description of the experiment we can declare that this is a discrete time Markov chain. Obviously, if we are in a state it does not matter how we got there; the probability of the next state depends on the actual state.
Now, here are the state transition probabilities:
$$ p_{ij}: \begin{bmatrix} &\mathbf j&\mathbf0&\mathbf1&\mathbf2&\mathbf3\\ \mathbf i&\\ \mathbf0&&0&1&0&0\\ \mathbf1&&\frac19&\frac49&\frac49&0\\ \mathbf2&&0&\frac49&\frac49&\frac19\\ \mathbf3&&0&0&1&0 \end{bmatrix}.$$
$\mathbf i$ stands for the state the system actually is at, and $\mathbf j$ stands for the state the system is to jump to.
For example
$$p_{22}=\frac49$$
because we need to randomly select either of the white balls ($\frac23$) in the left box and the white ball in the right box ($\frac13$) or either of the black balls in the right box ($\frac23$) and the black ball in the left box ($\frac13$); the events are independent. The following figure shows the four equally likely pairs of choices resulting in $2\to 2$.
Note that the system does not remain in state $\mathbf3$ rather it jumps to state $\mathbf 2$ with probability one.
Let $[P_0 P_1 P_2 P_3]^T$ denote the stationary probabilities. These probabilities are the solutions of the following system of linear equations:
$$[P_0 \ P_1 \ P_2\ \ P_3] \begin{bmatrix} 0&1&0&0\\ \frac19&\frac49&\frac49&0\\ 0&\frac49&\frac49&\frac19\\ 0&0&1&0 \end{bmatrix}=[P_0\ P_1 \ P_2\ P_3]. $$
It is easy to check that
$$[P_0 \ P_1 \ P_2\ P_3]^T=\left[\frac1{20} \ \frac{9}{20}\ \frac{9}{20}\ \frac1{20}\right]^T.$$
Best Answer
Let $p_{ij}$ be the probability that we go to state $j$ from $i$.
Suppose we are in state $i$. There are three cases: The state increases by $1$, decreases by $1$ or stays the same.
The state decreases by $1$ if and only if we draw a ball from $A$ and place it into $B$. The probability for that is $\frac{i}{N}q$. Similarly the probability that the state increases by $1$ is $\frac{N-i}{N}p$. So
$p_{ij} = \begin{cases} \frac{N-i}{N}p & j=i+1\\\frac{i}{N}q & j=i-1\\1- \frac{N-i}{N}p-\frac{i}{N}q &j=i\\0&\text{otherwise} \end{cases}$