Markov Chain matrix issue

Question

I'm doing the following problem that upsets me : Let's consider an urn with $n+1$ red and white balls ( at least one white ball at the beginning ) in it and repeat the experiment : - Pick two balls from the urn:

$\bullet$ If they are of the same color we replace them by one red and one white.

$\bullet$ If they are from different color we put them back in the bowl.

Let $X_k$ be the number of white after $k$ manipulations and $U_k=P(X_k=i)$ for $i$ between $1$ and $n$

I’m studying the case where $n=4$ and I need to find the matrix $A$ such that $$U_{k+1}=AU_k.$$

I used that $$P(X_{k+1}=p)=\sum_{i=1}^n P(X_k=p | X_k=i) P(X_k=i)$$ Hence I've deduced $$A_{ij}=P(X_{k+1}=i+1| X_k=j)$$

Seeing the problem, the non null values of the matrix are when $\left|j-i\right| \leq 1$ which gives by taking each experiment in account : \begin{align*} P(X_{k+1}=i | X_k=i) &= \frac{i\left(n+1-i\right)}{n(n+1)}, \\ P(X_{k+1}=i-1 | X_k=i) &= \frac{i\left(i-1\right)}{n(n+1)}, \\ P(X_{k+1}=i+1| X_k=i) &= \frac{(n-i)\left(n+1-i\right)}{n(n+1)}. \end{align*}

The matrix I've found evaluating with $i$ and $j$ is $$ \frac{1}{20} \begin{pmatrix} 4 & 2 & 0 & 0 \\ 12 & 6 & 6 & 0 \\ 0 & 6 & 6 & 12 \\ 0 & 0 & 2 & 4 \end{pmatrix} $$

which is false and I wonder why and how I could find the matrix $A$. Any help ?

Answer 1

Look closely at your expression for making no change to $i$: it is wrong by a factor of $2$. If you double the diagonal elements of your matrix, it should be OK. I'm guessing you calculated the probability of drawing a white ball followed by a red one, and neglected to consider the probability of doing it the other way round.

Answer 2

The three expressions that you have for the nonzero transition probabilities don’t add up to $1$, so the problem lies there. They’re all governed by a hypergeometric distribution, so you should have $$\Pr(X_{k+1}=i-1 \mid X_k=i) = {\binom i 2 \binom{n-i+1} 0 \over \binom {n+1}2} \\ \Pr(X_{k+1}=i \mid X_k=i) = {\binom i 1 \binom{n-i+1} 1 \over \binom {n+1}2} \\ \Pr(X_{k+1}=i+1 \mid X_k=i) = {\binom i 0 \binom{n-i+1} 2 \over \binom {n+1}2}.$$ If you simplify these expressions, you’ll find that the probability for no change in the number of white balls is off by a factor of two.