Question

Consider a sequence of independent trials, each of which is equally likely to result in any of the outcomes \(0,1, \ldots, m\). Say that a round begins with the first trial, and that a new round begins each time outcome 0 occurs. Let \(N\) denote the number of trials that it takes until all of the outcomes \(1, \ldots, m-1\) have occurred in the same round. Also, let \(T_{j}\) denote the number of trials that it takes until \(j\) distinct outcomes have occurred, and let \(I_{j}\) denote the \(j\) th distinct outcome to occur. (Therefore, outcome \(I_{j}\) first occurs at trial \(\left.T_{j} .\right)\) (a) Argue that the random vectors \(\left(I_{1}, \ldots, I_{m}\right)\) and \(\left(T_{1}, \ldots, T_{m}\right)\) are independent. (b) Define \(X\) by letting \(X=j\) if outcome 0 is the \(j\) th distinct outcome to occur. (Thus, \(I_{X}=0 .\) ) Derive an equation for \(E[N]\) in terms of \(E\left[T_{j}\right], j=1, \ldots, m-1\) by conditioning on \(X\). (c) Determine \(E\left[T_{j}\right], j=1, \ldots, m-1\) Hint: See Exercise 42 of Chapter \(2 .\) (d) Find \(E[N]\).

Short answer

The expected number of trials, \(E[N]\), that it takes until all of the outcomes \(1, \ldots, m-1\) have occurred in the same round is given by the equation: \(E[N] = \sum_{j=1}^{m} \frac{(m-j)!}{m!}\left( m\sum_{i=j}^{m-1} \frac{1}{m-i}\right)\)

Step-by-step solution

a) Show that random vectors (I_1,...,I_m) and (T_1,...,T_m) are independent

We need to show that \(\mathbb{P}\left((I_{1}, \ldots, I_{m})=(i_1,\ldots, i_m), (T_{1}, \ldots, T_{m})=(t_1,\ldots, t_m)\right)=\mathbb{P}\left((I_{1}, \ldots, I_{m})=(i_1,\ldots, i_m)\right)\mathbb{P}\left((T_{1}, \ldots, T_{m})=(t_1,\ldots, t_m)\right)\). However, given the nature of how the events \(I_i\) and \(T_i\) are defined, they do not affect the probability of one another, essentially rendering the probability of the two random vectors occurring together as the product of their individual probabilities. Therefore, they are independent.

b) Derive an equation for E[N] in terms of E[T_j] by conditioning on X

Using the law of iterated expectations, we can express the expected value of N as follows: \(E[N] = E\left[E[N | X]\right]\) Since N represents the number of trials that it takes until all of the outcomes \(1, \ldots, m-1\) have occurred in the same round, conditioning on X helps us compute the expected value of N in terms of \(E[T_j]\): \(E[N | X=j] = T_j + E[T_{j+1} - T_j] + \ldots + E[T_{m} - T_{m-1}]\) So, \(E[N] = E\left[E[N | X]\right] = \sum_{j=1}^{m} \mathbb{P}(X=j)\left( T_j + E[T_{j+1} - T_j] + \ldots + E[T_{m} - T_{m-1}] \right)\)

c) Determine E[T_j] for j=1,...,m-1

Using the hint provided, which refers to Exercise 42 of Chapter 2, we have: \(E[T_j] = \frac{m}{m-j}\) for \(j = 1, \ldots, m-1\)

d) Find E[N]

Now that we have E[T_j], we can substitute it in the equation for E[N]. We first calculate the probability P(X=j), which is the probability that the outcome 0 is the \(j^{th}\) distinct outcome: \(\mathbb{P}(X=j) = \frac{(m-j)(m-1)!}{m!} = \frac{(m-j)!}{m!}\) Now we compute E[N]: \(E[N] = \sum_{j=1}^{m} \mathbb{P}(X=j)\left( \frac{m}{m-j} + \frac{m}{m-(j+1)} + \ldots + \frac{m}{m-(m-1)} \right)\) \(E[N] = \sum_{j=1}^{m} \frac{(m-j)!}{m!}\left( m\sum_{i=j}^{m-1} \frac{1}{m-i}\right)\) \(E[N] = \sum_{j=1}^{m} \frac{m!(m-j)!}{m!} \left(\frac{1}{j!} \sum_{i=j}^{m-1} \frac{j!}{(m-i)!}\right)\) This equation gives us the expected value of N.

Key concepts

Independent Trials

Understanding independent trials is crucial in probability and statistics. Independent trials refer to experiments or processes where the outcome of one trial does not influence the outcome of another. In essence, if you flip a coin multiple times, each flip represents an independent trial because the result of one coin flip (heads or tails) does not affect how the coin will land on the next flip.

From the problem provided, each trial is independent because the occurrence of any outcome, such as getting a '0' or any number up to 'm', does not affect the subsequent trials. This fundamental concept allows us to calculate probabilities of sequences of outcomes simply by multiplying the probabilities of the individual trials, assuming each outcome has an equal chance.

Random Vectors Independence

The independence of random vectors is akin to the concept of independent trials but extended to multidimensional scenarios. Two random vectors are independent if the occurrence of one vector does not affect the probability distribution of the other. In the given exercise, the random vectors \(I_1, \ldots, I_m\) represent the sequence of distinct outcomes, while \(T_1, \ldots, T_m\) represent the sequence of trials until each distinct outcome occurs.

The vectors are independent because the distinct outcomes \(I_i\) are solely determined by the order of appearance, which is independent of the number of trials \(T_i\) required to achieve the outcomes. This concept is essential because it makes it possible to analyze complex multidimensional sequences and their probabilities without the complications that would arise if the vectors were dependent.

Conditional Expectation

Conditional expectation is a powerful concept used to calculate the expected value of a random variable given that certain conditions are met. More formally, \(E[Y | X]\) represents the expected value of \(Y\) given the random variable \(X\). This helps in understanding complex scenarios by breaking them down into simpler, conditional steps.

In our problem, \(E[N | X=j]\) calculates the expected number of trials needed to achieve all outcomes in the same round, given that the outcome '0' is the \(j^{th}\) distinct outcome to occur. By calculating the conditional expectations, we add another layer to our analysis, allowing us to incorporate additional information and thus honing our predictions about the random variable's behavior.

Iterative Expectations

Iterative expectations, often referred to as the 'law of total expectation' or 'law of iterated expectations', is a principle that relates the expected value of a conditional expectation to the expected value of the random variable itself. It essentially states that the overall expected value can be found by averaging out the conditional expectations. The formula is \(E[Y] = E[E[Y | X]]\), which means we can find the expected value of \(Y\) by first finding the expected values within each condition set by \(X\), and then taking the expected value of those results.

In the context of our exercise, we first find the expectation of \(N\) conditioned on \(X\), and then take the expectation of these results to derive \(E[N]\). This powerful tool allows us to dissect complex problems into stages where we focus on one variable at a time and gradually build up to the full picture.