Question

Consider a miner trapped in a room that contains three doors. Door 1 leads him to freedom after two days of travel; door 2 returns him to his room after a four-day journey; and door 3 returns him to his room after a six-day journey. Suppose at all times he is equally likely to choose any of the three doors, and let \(T\) denote the time it takes the miner to become free. (a) Define a sequence of independent and identically distributed random variables \(X_{1}, X_{2} \ldots\) and a stopping time \(N\) such that $$ T=\sum_{i=1}^{N} X_{i} $$ Note: You may have to imagine that the miner continues to randomly choose doors even after he reaches safety. (b) Use Wald's equation to find \(E[T]\). (c) Compute \(E\left[\sum_{i=1}^{N} X_{i} \mid N=n\right]\) and note that it is not equal to \(E\left[\sum_{i=1}^{n} X_{i}\right]\) (d) Use part (c) for a second derivation of \(E[T]\).

Short answer

Using the given random variables and stopping time, we can derive the expected time for the miner to become free using Wald's equation, which gives us \(E[T] = 12\). Additionally, using the conditional expectation \(E\left[\sum_{i=1}^{N} X_{i} \mid N=n\right] = (n - 1)4 + 2\), we get the same expected value, confirming that the miner takes an expected time of 12 days to become free.

Step-by-step solution

Part (a) - Define Random Variables and Stopping Time

Let's define the random variables as follows: - \(X_i\): The time the miner takes to become free in the \(i^{th}\) step. These random variables \(X_i\) are independent and identically distributed with a probability mass function given by: $$ P(X_i = x) = \begin{cases} \frac{1}{3}, & x = 2 \\ \frac{1}{3}, & x = 4 \\ \frac{1}{3}, & x = 6 \\ 0, & \text{otherwise} \end{cases} $$ Now, let's define the stopping time \(N\) as the first time the miner chooses door 1. This stopping time is determined by a geometric random variable with success probability \(\frac{1}{3}\). Therefore, we have: $$T = \sum_{i=1}^{N} X_{i}$$

Part (b) - Use Wald's Equation to Find E[T]

Wald's equation states that \(E[T] = E[N] \times E[X_i]\) when \(N\) is a stopping time and \(X_i\)'s are independent and identically distributed random variables. We know that \(N\) has a geometric distribution with a success probability of \(\frac{1}{3}\). Therefore, its expected value is given by \(E[N] = \frac{1}{\frac{1}{3}} = 3\). Now, we need to compute \(E[X_i]\). $$ E[X_i] = \sum_{x} xP(X_i = x) = 2\left(\frac{1}{3}\right) + 4\left(\frac{1}{3}\right) + 6\left(\frac{1}{3}\right) = 4 $$ By using Wald's equation, we have: $$ E[T] = E[N] \times E[X_i] = 3 \times 4 = 12 $$

Part (c) - Compute Conditional Expected Value

Now, let's calculate the expected value of \(\sum_{i=1}^{N} X_{i}\) given \(N = n\). Since \(N = n\) and the miner chooses door 1 exactly on the nth trial, the miner chooses doors 2 or 3 in the first \(n - 1\) trials: $$ E\left[\sum_{i=1}^{N} X_{i} \mid N=n\right] = E[X_1 + X_2 + \cdots + X_{n-1} + 2] $$ Because \(X_{i}\) is independent and identically distributed, we have: $$ E\left[\sum_{i=1}^{N} X_{i} \mid N=n\right] = (n - 1)E[X_i] + 2 = (n - 1)4 + 2 $$ Note that this is not equal to \(E\left[\sum_{i=1}^{n} X_{i}\right]\).

Part (d) - Second Derivation of E[T] Using Part (c)

Using the result from part (c), we can calculate \(E[T]\) as: $$ E[T] = E\left[E\left[\sum_{i=1}^{N} X_{i} \mid N=n\right]\right] = \sum_{n=1}^{\infty} P(N = n)E\left[\sum_{i=1}^{N} X_{i} \mid N=n\right] $$ Using the geometric distribution of \(N\) and the expression for the conditional expectation, we have: $$ E[T] = \sum_{n=1}^{\infty} \left(\frac{2}{3}\right)^{n-1} \left(\frac{1}{3}\right) ((n-1)4 + 2) $$ $$ E[T] = \frac{1}{3}\left(\sum_{n=1}^{\infty} \left(\frac{2}{3}\right)^{n-1} (4n - 2)\right) $$ Now, you can evaluate the sum, which results in the value \(E[T] = 12\). Both methods (using Wald's equation and the conditional expectation) give the same expected value for the time it takes the miner to become free, which is \(E[T] = 12\).