Problem 13.14 Easy Free 2 variations

Waiting to Beat the First Value

Let $U \sim \mathrm{Unif}(0,1)$ and let $X_1, X_2, \dots$ be i.i.d. $\mathrm{Unif}(0,1)$ random variables, independent of $U$ . Let $N = \min\{n \in \mathbb{N} : X_n > U\}$ . Is $\mathbb{E}[N]$ finite? If so, find it.

Work it out, then compare with the answer.

SolutionShow the worked solution

Key idea. Condition on the threshold $U$ .

Given $U=u$ , the trials $X_1,X_2,\dots$ are independent. Each one succeeds ( $X_n>u$ ) with probability $1-u$ . So $N\mid U=u \sim \mathrm{Geom}(1-u)$ on $\{1,2,\dots\}$ , and

\mathbb{E}[N\mid U]=\frac{1}{1-U}.

By the tower property,

\mathbb{E}[N]=\mathbb{E}\!\left[\frac{1}{1-U}\right]=\int_0^1\frac{du}{1-u}=\Bigl[-\ln(1-u)\Bigr]_0^{1^-}=\infty .

Hence $N$ is finite almost surely, but its mean is not finite. The divergence comes from thresholds $U$ close to $1$ , which make the wait very long.

Alternative. The event $\{N>n\}$ says that $X_1,\dots,X_n\le U$ . In other words, $U$ is the largest of the $n+1$ i.i.d. continuous variables $U,X_1,\dots,X_n$ . By symmetry this has probability $\frac{1}{n+1}$ . Therefore

\mathbb{E}[N]=\sum_{n\ge 0}\mathbb{P}(N>n)=\sum_{n\ge0}\frac{1}{n+1}=\infty,

because the harmonic series diverges.

\boxed{\mathbb{E}[N]=\infty}

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 13.14a

Let $T, X_1, X_2, \dots$ be i.i.d. $\mathrm{Beta}(12,8)$ random variables. Let $N = \min\{n \in \mathbb{N} : X_n > T\}$ . Is $\mathbb{E}[N]$ finite? If so, find it.

Work it out, then compare with the answer.

Solution

The symmetry argument uses only the fact that $T,X_1,X_2,\dots$ are i.i.d. and continuous, so ties have probability zero.

The event $\{N>n\}$ says that $T$ is the largest of the $n+1$ variables $T,X_1,\dots,X_n$ . By exchangeability this has probability $\frac{1}{n+1}$ .

The same conclusion follows from the probability integral transform. Let $F$ be the $\mathrm{Beta}(12,8)$ distribution function, which is strictly increasing on $(0,1)$ . Then $F(T),F(X_1),\dots$ are i.i.d. $\mathrm{Unif}(0,1)$ , and $X_n>T \iff F(X_n)>F(T)$ . This is exactly the main problem.

Either way,

\mathbb{E}[N]=\sum_{n\ge0}\frac{1}{n+1}=\infty.

\boxed{\mathbb{E}[N]=\infty}

Variation 13.14b

You roll a fair six-sided die and record the result. You then keep rolling the same die until you obtain a value at least as large as your first roll (a tie counts as a success). Let $N$ be the number of rolls you make after the first. Find $\mathbb{E}[N]$ .

Work it out, then compare with the answer.

Solution

Let $X$ be the first roll. Given $X=i$ , exactly $7-i$ faces are at least $i$ . Each later roll therefore succeeds with probability $\frac{7-i}{6}$ , so $N\mid X=i\sim\mathrm{Geom}\!\left(\frac{7-i}{6}\right)$ and

\mathbb{E}[N\mid X=i]=\frac{6}{7-i}.

The success probability never falls below $\frac16$ , so the mean is now finite:

\mathbb{E}[N]=\sum_{i=1}^6\frac16\cdot\frac{6}{7-i}=\sum_{k=1}^6\frac1k=H_6=\frac{49}{20}=2.45 .

\boxed{\mathbb{E}[N]=\frac{49}{20}}

Spotted an error? Email us