Question

A particle moves among \(n+1\) vertices that are situated on a circle in the following manner. At each step it moves one step either in the clockwise direction with probability \(p\) or the counterclockwise direction with probability \(q=1-p\). Starting at a specified state, call it state 0 , let \(T\) be the time of the first return to state 0 . Find the probability that all states have been visited by time \(T\). Hint: Condition on the initial transition and then use results from the gambler's ruin problem.

Short answer

The probability that all states have been visited by the time the particle returns to state 0 can be found by conditioning on the initial transition and using the concept of gambler's ruin. The resulting probability is given by: \[ P_n = p \left[ 1 - \frac{1 - (\frac{p}{q})^{n-1}}{1 - (\frac{p}{q})^n} \right] + q \left[ 1 - \frac{1 - (\frac{p}{q})^{-1}}{1 - (\frac{p}{q})^n} \right] \]

Step-by-step solution

(Step 1: Define state space and transition probabilities)

We consider a discrete-time Markov chain with \( n+1 \) states, numbered from 0 to \( n \). Let \( X_k \) be the state occupied by the particle at step \( k\geq 0 \) . The transition probabilities can be defined as follows: - Clockwise movement: \( P_{ij} = p \) if \( (i+1) \) mod \( (n+1) = j \) - Counterclockwise movement: \( P_{ij} = q \) if \( (i-1) \) mod \( (n+1) = j \)

(Step 2: Use conditioning on the initial transition)

Let \( P_n \) denote the probability that all states have been visited by time \( T \). We can condition on the outcome of the first step. By conditioning on whether the particle moves clockwise or counterclockwise initially, we have: \[ P_n = p P^{(1)}_n + q P^{(-1)}_n \] where: - \( P^{(1)}_n \) is the probability that all states have been visited by time \( T \) given that the particle moves clockwise in the first step. - \( P^{(-1)}_n \) is the probability that all states have been visited by time \( T \) given that the particle moves counterclockwise in the first step.

(Step 3: Connect the problem to gambler's ruin)

By considering the direction of the first step as the initial choice of direction the particle needs to move for the states to be visited, the problem can be viewed as a one-sided gambler's ruin problem. In gambler's ruin, the probability of winning with \( a \) starting sum before reaching the target sum is \( \frac{1 - (\frac{p}{q})^a}{1 - (\frac{p}{q})^n} \). In our case, when the particle moves clockwise in the first step, the probability is: \[ P^{(1)}_n = 1 - \frac{1 - (\frac{p}{q})^{n-1}}{1 - (\frac{p}{q})^n} \] Similarly, when the particle moves counterclockwise in the first step, the probability is: \[ P^{(-1)}_n = 1 - \frac{1 - (\frac{p}{q})^{-1}}{1 - (\frac{p}{q})^n} \]

(Step 4: Compute the probability of visiting all states)

Combining the probabilities found in step 2 and step 3, we have: \[ P_n = p \left[ 1 - \frac{1 - (\frac{p}{q})^{n-1}}{1 - (\frac{p}{q})^n} \right] + q \left[ 1 - \frac{1 - (\frac{p}{q})^{-1}}{1 - (\frac{p}{q})^n} \right] \] This gives us the probability that all states have been visited by the time the particle returns to state 0.