Urn with balls, distribution of random variable

Question

From an urn containing $6$ balls numerated $1,\ldots,6$ we randomly choose one, then again and stop only when we picked the ball with number $1$ on it. Let $X$ be the greatest number that appeared on balls we already pulled out. What's the distribution of $X\ $? And $\mathbb{E}X=\ ?$

Answer 1

Edit: Later on, we describe a fast solution. But for reasons of nostalgia, we keep our first slow way.

The slow way: We assume that the balls are removed one at a time and not replaced. Then the probabilities can be found with a careful examination of cases.

With probability $\frac{1}{6}$ we have $X=1$.

We have $X=2$ precisely if we got the sequence $2,1$. This has probability $\frac{1}{6\cdot 5}$.

We have $X=3$ in several ways: the sequence $3,1$, the sequence $2,3,1$ and the sequence $3,2,1$. The combined probability is $\frac{1}{6\cdot 5}+\frac{2}{6\cdot 5\cdot 4}$.

For the number of ways in which $X=4$, note that this happens with the sequences $4,1$, or $4,2,1$, or $2,4,1$, or $3,4,1$ or $4,3,1$, or $x,y,z,1$, where $x,y,z$ is one of the $6$ permutations of $2,3,4$. The probability is $\frac{1}{6\cdot 5}+\frac{4}{6\cdot 5\cdot 4}+ \frac{6}{6\cdot 5\cdot 4\cdot 3}$.

And so on. Actually, we are almost finished, since once we find $\Pr(X=5)$, we know $\Pr(X=8)$, since the probabilities add to $1$. It may still be a good idea to do an independent computation of $\Pr(X=6)$, as a check.

Once we have the probability distribution of $X$, finding $E(X)$ is mechanical.

A much faster way: The computations can be streamlined. Let us find $\Pr(X\le 5)$. This is the probability that $6$ comes after $1$. By symmetry this is $\frac{1}{2}$. So $\Pr(X=6)=\Pr(X\le 6)-\Pr(X\le 5)=\frac{1}{2}$.

To find $\Pr(X=5)$, we calculate $\Pr(X\le 5)-\Pr(X\le 4)$. The probability that $X$ is $\le 4$ is the probability $1$ comes before $5$ and $6$, which is $\frac{1}{3}$. So $\Pr(X=5)=\frac{1}{6}$.

To find $\Pr(X= 4)$, we find $\Pr(X\le 4)-\Pr(X\le 3)$. The probability that $X$ is $\le 3$ is the probability that $1$ comes before $4$, $5$, and $6$. This is $\frac{1}{4}$, so $\Pr(X=4)=\frac{1}{12}$.

Continue, it's almost over.

The idea works smoothly for balls numbered $1$ to $n$.

Remarks: $1.$ The "fast" method can be adapted to sampling with replacement. We calculate, as a sample, the probability that $X$ is $\le 4$. This can happen in various ways: First is $6$, first is between $2$ and $4$ and the second is a $1$, first $2$ are between $2$ and $4$ and the third is a $1$, and so on. The probability is given by $$\Pr(X\le 4)=\frac{1}{6}\left(1+\frac{3}{6}+\frac{3^2}{6^2}+\cdots \right).$$ Thus $\Pr(X\le 4)=\frac{1}{3}$. Similarly, we can calculate $\Pr(X\le 3)$, and then by subtraction $\Pr(X=4)$. If we compare with the numbers obtained in the no replacement case, we will notice something interesting.

$2.$ There is a fancier, but ultimately faster way of finding $E(X)$, the method of indicator random variables. This can be done without finding the distribution of $X$. But since we were asked to find that distribution, we might as well use it.