Question

At all times, an urn contains \(N\) balls?-some white balls and some black balls. At each stage, a coin having probability \(p, 0

Short answer

In summary: (a) \(\{X_n, n \geq 0\}\) is a Markov chain because the future state only depends on the current state. (b) The classes of the Markov chain are the number of white balls in the urn, with the chain being irreducible, states having a period of 1, and all states recurrent. (c) The transition probabilities are: \(P_{ij} = (1-p)\frac{N-i}{N}\) for i ≤ N - 1 and j = i + 1, \(P_{ij} = p\frac{i}{N}\) for i ≥ 1 and j = i - 1, and \(P_{ij} = p\frac{i}{N} + (1-p)\frac{N-i}{N}\) when j = i. (d) For N = 2: \(\pi_0 = \frac{1 - p}{4 - 2p}\), \(\pi_1 = \frac{1}{4 - 2p}\), and \(\pi_2 = \frac{p}{4 - 2p}\). (e) The guessed limiting probability for the general case is \(\pi_i = \frac{\binom{N}{i}p^i(1-p)^{N-i}}{2^N - (-1)^N}\) for i = 0, 1, 2, ..., N. (f) The guess is proven to satisfy the Detailed Balance Equations. (g) For p = 1, the expected time until there are only white balls in the urn can be found using the recursive formula: \(T(i) = 1 + \frac{i}{N}T(i-1) + \frac{N-i}{N}T(i+1)\) with boundary conditions T(0) = 0 and T(N) = 0.

Step-by-step solution

(a) Determine if the process is a Markov chain

We need to check if the given process, \(\{X_n, n \geq 0\}\), satisfies the Markov property. The Markov property states that the future state only depends on the current state, not the past states. In this case, the number of white balls in the urn after the nth stage only depends on the current state (number of white balls), and not the outcomes of previous coin flips. So, \(\{X_n, n \geq 0\}\) is a Markov chain.

(b) Identify the classes, periods, and transience/recurrence of the Markov chain

The classes of this Markov chain are the number of white balls in the urn, ranging from 0 to N. Since we can go from any state to any other state (depending on the coin flips), the Markov chain is irreducible. Each state has period 1, as loops transition from state i to state i are possible in one step, i.e., replacing a white ball with a white ball, or a black ball with a black ball. As the Markov chain is finite and irreducible, all states are recurrent.

(c) Compute the transition probabilities

Let's compute the transition probabilities \(P_{ij}\) for this Markov chain. \(P_{ij}\) denotes the probability of transitioning from state i to state j, where i and j indicate the number of white balls in the urn. (i) If 0 ≤ i ≤ N - 1 and j = i + 1, we are replacing a black ball with a white ball after getting tails. \(P_{ij} = (1-p)\frac{N-i}{N}\) (ii) If 1 ≤ i ≤ N and j = i - 1, we are replacing a white ball with a black ball after getting heads. \(P_{ij} = p\frac{i}{N}\) (iii) If j = i, we have two cases: Replacing a white ball with a white ball after getting heads, or replacing a black ball with a black ball after getting tails. \[P_{ij} = p\frac{i}{N} + (1-p)\frac{N-i}{N}\]

(d) Calculate the proportion of time in each state for N = 2

For N = 2, we can write down the transition matrix P: \[P = \begin{bmatrix}1-p & p & 0 \\ \frac{1 - p}{2} & 0 & \frac{1 + p}{2} \\ 0 & p & 1 - p \end{bmatrix}\] Now, let's find the stationary distribution \(\pi\), which represents the limiting probabilities or the proportion of time the chain spends in each state. The stationary distribution satisfies the following equation: \(\pi P = \pi\) By summing the rows, we obtain: \(\pi_0(1-p) + \pi_1(1 - p) = \pi_0\) \(\pi_0p + \pi_1p = \pi_1\) \(\pi_1(1+p) + \pi_2p = \pi_2\) Solving these equations and normalizing the probabilities (i.e., \(\pi_0 + \pi_1 + \pi_2 = 1\)), we get: \(\pi_0 = \frac{1 - p}{4 - 2p}\) , \(\pi_1 = \frac{1}{4 - 2p}\), and \(\pi_2 = \frac{p}{4 - 2p}\)

(e) Guess the limiting probability in the general case

Based on the solution in part (d) and using intuition, we can guess the limiting probabilities for the general case: \(\pi_i = \frac{\binom{N}{i}p^i(1-p)^{N-i}}{2^N - (-1)^N}\) for i = 0, 1, 2, ..., N

(f) Prove the guess in part (e) using Equation (4.7) or results of Example 4.35

We will prove the guess in part (e) using Equation (4.7) (also called the Detailed Balance Equations). The detailed balance equation states: \(\pi_ip_{ij} = \pi_jp_{ji}\) Consider any two states i and j: (i) If j = i + 1, then \(\pi_ip_{ij} = \frac{\binom{N}{i}p^i(1-p)^{N-i}}{2^N - (-1)^N}(1-p)\frac{N-i}{N}\), and \(= \frac{\binom{N}{i+1}p^{i+1}(1-p)^{N-(i+1)}}{2^N - (-1)^N}p\frac{i+1}{N}\) These two expressions are equal according to our conjecture, as shown by simplifying them: \(\frac{\binom{N}{i}p^i(1-p)^{N-i}}{2^N - (-1)^N}(1-p)\frac{N-i}{N} = \frac{\binom{N}{i+1}p^{i+1}(1-p)^{N-(i+1)}}{2^N - (-1)^N}p\frac{i+1}{N}\) (ii) If j = i - 1, we can perform a similar analysis to show that the detailed balance equations hold based on our guess. Since our guess satisfies the detailed balance equations, it is the limiting probability distribution for the general case.

(g) Calculate the expected time until there are only white balls in the urn

Since p=1, the process will always replace a ball with a white ball. Let T(i) denote the expected time until there are only white balls in the urn if initially there are i white and N-i black balls. We have the following recursive formula for T(i): \[T(i) = 1 + \frac{i}{N}T(i-1) + \frac{N-i}{N}T(i+1)\] For i = N (all white balls initially), T(N) = 0. The boundary condition is then T(0) = 0. Using these conditions, we can solve the recursive formula to find the expected time, T(i), until there are only white balls in the urn.