Monday 31 August 2026

The decomposition that unlocks everything

Write $T=X_0+X_1+\cdots +X_{n-1}$, where $X_i$ is the number of ticks needed to go from $i$ distinct symbols to $i+1$ distinct symbols. Once you already hold $i$ symbols, each new tick is a new symbol with probability

$$p_i=\frac{n-i}{n},$$

and a repeat otherwise, independently of the past (the ticks are i.i.d. and only the count $i$ matters, not which symbols). Hence $X_i$ is geometric on $\{1,2,\dots \}$ with success probability $p_i$.

The point a candidate can miss: the segments $X_0,\dots ,X_{n-1}$ are mutually independent. After each success the process restarts as a fresh sequence of i.i.d. Bernoulli$(p_{i+1})$ trials whose length is unaffected by how long the previous segment took (memorylessness of the geometric plus i.i.d. draws). This independence is what makes the variance a plain sum.

Part 1: the mean

A geometric$(p)$ variable has mean $1/p$, so

$$𝔼[T]=\sum _{i=0}^{n-1}\frac{1}{p_i}=\sum _{i=0}^{n-1}\frac{n}{n-i}.$$

Substituting $j=n-i$ (so $j$ runs $1$ to $n$),

$$𝔼[T]=n\sum _{j=1}^n\frac{1}{j}=n{H}_n.$$

For $n=6$: $H_6=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=2.45$, so $𝔼[T]=6·2.45=14.7$.

Part 2: the variance

By independence, $\mathrm{V}\mathrm{a}\mathrm{r}(T)={\sum }_{i=0}^{n-1}\mathrm{V}\mathrm{a}\mathrm{r}(X_i)$. A geometric$(p)$ variable has variance $(1-p)/p^2$. With $p_i=(n-i)/n$ we have $1-p_i=i/n$ and $p_i^2=(n-i{)}^2/n^2$, so

$$\mathrm{V}\mathrm{a}\mathrm{r}(X_i)=\frac{i/n}{(n-i{)}^2/n^2}=\frac{ni}{(n-i{)}^2}.$$

Summing and substituting $j=n-i$ again,

$$\mathrm{V}\mathrm{a}\mathrm{r}(T)=\sum _{i=0}^{n-1}\frac{ni}{(n-i{)}^2}=\sum _{j=1}^n\frac{n(n-j)}{j^2}=n^2\sum _{j=1}^n\frac{1}{j^2}-n\sum _{j=1}^n\frac{1}{j}.$$

Thus the closed form is

$$\mathrm{V}\mathrm{a}\mathrm{r}(T)=n^2\sum _{j=1}^n\frac{1}{j^2}-n{H}_n.$$

Since ${\sum }_{j\ge 1}{j}^{-2}={\pi }^2/6$ and $H_n=\ln n+O(1)$, the leading term is

$$\mathrm{V}\mathrm{a}\mathrm{r}(T)~\frac{{\pi }^2}{6}{n}^2(n\to \infty ).$$

So the standard deviation is $~\frac{\pi }{\sqrt{6}}n$, of order $n$, while the mean is of order $n\ln n$. The ratio $\mathrm{s}\mathrm{d}/𝔼~\frac{\pi }{\sqrt{6}\ln n}\to 0$: $T$ concentrates around $n\ln n$, and the tail beyond the mean is dominated by the long wait for the single last symbol (that segment alone contributes variance $n(n-1)\approx n^2$).

For $n=6$: ${\sum }_{j=1}^6{j}^{-2}=1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\frac{1}{25}+\frac{1}{36}=1.49139$, so

$$\mathrm{V}\mathrm{a}\mathrm{r}(T)=36·1.49139-14.7=53.690-14.7=38.99,\mathrm{s}\mathrm{d}(T)\approx 6.24.$$

Part 3: the remaining stretch

Given that exactly $k$ symbols have been seen, the future is again a fresh collector problem: the remaining waits are the independent geometrics $X_k,X_{k+1},\dots ,X_{n-1}$ with success probabilities $p_j=(n-j)/n$. Hence

$$𝔼[\text{additional ticks}]=\sum _{j=k}^{n-1}\frac{n}{n-j}=n\sum _{i=1}^{n-k}\frac{1}{i}=n{H}_{n-k}.$$

It depends only on how many symbols remain, $n-k$, not on their identities: by symmetry every unseen symbol is drawn with the same probability $1/n$ per tick, so relabelling the missing symbols changes nothing. For $n=6,k=4$ (two symbols missing):

$$n{H}_{n-k}=6H_2=6(1+\frac{1}{2})=9.$$

Answers

1. $𝔼[T]=n{H}_n$; for $n=6$, $𝔼[T]=14.7$.
2. $\mathrm{V}\mathrm{a}\mathrm{r}(T)=n^2{\sum }_{j=1}^n{j}^{-2}-n{H}_n~\frac{{\pi }^2}{6}{n}^2$; for $n=6$, $\mathrm{V}\mathrm{a}\mathrm{r}(T)\approx 38.99$ and $\mathrm{s}\mathrm{d}(T)\approx 6.24$. The relative spread $\mathrm{s}\mathrm{d}/𝔼\to 0$.
3. Expected additional ticks $=n{H}_{n-k}$; for $n=6,k=4$ this equals $9$.

Closing note. The tempting error is to treat the $X_i$ as merely uncorrelated, or worse to try computing $𝔼[T^2]$ directly — the whole simplification rests on the independence of the segments, which is genuinely true here. As a cross-check on Part 1, one can also use $𝔼[T]={\sum }_{m\ge 0}\mathbb{P}(T>m)$ together with the inclusion–exclusion occupancy formula $\mathbb{P}(T>m)={\sum }_{k=1}^n(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{n}{k}\left)\right(1-\frac{k}{n}{)}^m$; summing the geometric series in $m$ collapses back to $n{H}_n$.

1. The exact target law

For $t\in [0,n]$, using $F(x)=x/\theta$ on $[0,\theta ]$ and independence, $$P(T_n>t)=P(M_n<\theta (1-t/n))=\left(F\right(\theta (1-t/n)){)}^n={(1-\frac{t}{n})}^n.$$ This $\to e^{-t}$ for every fixed $t\ge 0$, so $T_n\stackrel{d}{\to }\mathrm{E}\mathrm{x}\mathrm{p}(1)$. The limit is continuous: $P(T=0)=0$. Keep that fact; it is what the bootstrap will violate.

2. Why the full-sample bootstrap fails

Conditionally on the data, each $X_i^{\backslash }*$ equals the maximizing observation with probability $1/n$. The bootstrap maximum equals $M_n$ iff that observation is drawn at least once, so $$P^{\backslash }*(M_n^{\backslash }*=M_n)=1-{(1-\frac{1}{n})}^n⟶1-e^{-1}\approx 0.632.$$ Whenever $M_n^{\backslash }*=M_n$ we have $T_n^{\backslash }*=0$. Hence the bootstrap law of $T_n^{\backslash }*$ carries a point mass at $0$ whose size tends to $1-e^{-1}$.

This is the decisive observation. The Kolmogorov distance between the bootstrap CDF $G_n^{\backslash }*$ and the target $G(t)=1-e^{-t}$ satisfies $${sup}_t|G_n^{\backslash }*(t)-G(t)|\ge G_n^{\backslash }*(0)-G(0)=P^{\backslash }*(T_n^{\backslash }*=0)\to 1-e^{-1}>0,$$ because $G$ is continuous with $G(0)=0$. So the bootstrap is inconsistent: no matter the realization of the data, its law stays a fixed distance from $\mathrm{E}\mathrm{x}\mathrm{p}(1)$.

The deeper reason (worth seeing). Compute the whole conditional survival function. With $K_n(t):=\#\{i:X_i>M_n(1-t/n)\}$, $$P^{\backslash }*(T_n^{\backslash }*>t)=P^{\backslash }*(M_n^{\backslash }*<M_n(1-t/n))={(1-\frac{K_n(t)}{n})}^n.$$ The window $(M_n(1-t/n),M_n]$ has width $\Theta (1/n)$, so it contains only a bounded number of order statistics; in fact $n(\theta -X_{(n-j)})/\theta$ converge jointly to the arrival times of a rate-$1$ Poisson process, and $K_n(t)\stackrel{d}{\to }N(t)$, the count of that process on $(0,t]$ (with $N(t)\ge 1$ once the max is inside). Therefore $$P^{\backslash }*(T_n^{\backslash }*>t)\stackrel{d}{\to }{e}^{-N(t)},$$ a random limiting survival function. Consistency (Bickel–Freedman) requires the conditional law to converge to the fixed $\mathrm{E}\mathrm{x}\mathrm{p}(1)$; here it converges to a random measure. The atom $e^{-N(0^{+})}·$-mass $=1-e^{-1}$ is just the visible symptom. The general lesson: the bootstrap fails exactly when the statistic depends on the extreme tail of the empirical measure, where resampling cannot manufacture the missing continuum.

3. Why $m$-out-of-$n$ repairs it

Repeat the atom computation with $m$ draws: $$P^{\backslash }*(M_m^{\backslash }*=M_n)=1-{(1-\frac{1}{n})}^m=1-\exp (m\log (1-1/n))\approx 1-e^{-m/n}⟶0,$$ since $m/n\to 0$. The atom vanishes.

For the full law, $T_m^{\backslash }*>t$ iff all $m$ resampled points fall in $[0,M_n(1-t/m)]$. Now the window $(M_n(1-t/m),M_n]$ has width $\approx \theta t/m$, which is large compared with the $1/n$ spacing since $m/n\to 0$. So the empirical measure of the window is accurate: by Glivenko–Cantelli and $M_n\to \theta$, $$P^{\backslash }*(M_m^{\backslash }*<M_n(1-t/m))=\left(F_n\right(M_n(1-t/m)){)}^m,F_n(M_n(1-t/m))\stackrel{P}{\to }1-\frac{t}{m}\text{(to leading order)}.$$ Hence $$P^{\backslash }*(T_m^{\backslash }*>t)\approx {(1-\frac{t}{m})}^m\stackrel{P}{\to }{e}^{-t}.$$ The subsampling ratio $m/n\to 0$ is exactly the condition that (i) kills the atom and (ii) makes the relevant window wide enough for the empirical CDF to be trustworthy. With $m=o(n)$ and $m\to \infty$ the $m$-out-of-$n$ bootstrap is consistent.

Answer

1. $T_n\stackrel{d}{\to }\mathrm{E}\mathrm{x}\mathrm{p}(1)$, a continuous law.
2. $P^{\backslash }*(M_n^{\backslash }*=M_n)=1-(1-1/n{)}^n\to 1-e^{-1}\approx 0.632$; the bootstrap law of $T_n^{\backslash }*$ has an atom of this mass at $0$ and its conditional survival function converges to the random limit $e^{-N(t)}$ (rate-$1$ Poisson $N$), so it cannot converge to the continuous $\mathrm{E}\mathrm{x}\mathrm{p}(1)$ — the ordinary bootstrap is inconsistent for the maximum.
3. Taking $m\to \infty ,m/n\to 0$ sends the atom to $0$ and yields $P^{\backslash }*(T_m^{\backslash }*>t)\stackrel{P}{\to }{e}^{-t}$, restoring consistency.

Tempting wrong answer: concluding the bootstrap works because $M_n^{\backslash }*\to \theta$ and $M_n\to \theta$. Consistency of the point estimate says nothing about consistency of the distribution of the normalized error; the $O(1/n)$-scale behavior at the boundary is where everything happens, and that scale is precisely what a full-sample resample cannot reproduce.