Expected People Passed Before Seeing Someone Taller
You are walking down a busy street, passing people one at a time. Everyone (including you) has a distinct height, and the order in which you encounter people is uniformly random. Your own height is ranked uniformly at random among all $n+1$ people (yourself plus $n$ others).
You keep walking until you encounter someone taller than you, at which point you stop.
What is the expected number of people you pass before stopping? If you are the tallest person, you never stop -- condition on the cases where you do stop, or give the unconditional answer (where "never stopping" contributes $\infty$ or is handled by taking $n$ large).
Express your answer in terms of $n$, and give the large-$n$ asymptotic form.
Hints
- Think about what determines how quickly you find someone taller -- it depends on how many people are taller than you, which depends on your rank.
- If your rank is $k$ out of $n+1$, the waiting time to see someone taller is geometric with success probability $(n+1-k)/n$. Average over your rank.
- The sum $\sum_{j=1}^{n} 1/j$ is the harmonic number $H_n \approx \ln n + 0.577$. This gives the logarithmic growth of the answer.
Worked Solution
How to Think About It: Picture yourself on a crowded sidewalk. You have some height rank among everyone, and you walk past the others *in a fixed random order* -- nobody is encountered twice. That last point is the crux: the people you meet form a random permutation, so you are sampling *without* replacement. If you are short, almost everyone ahead is taller and you stop almost immediately; if you are tall, you wait a long time. So the question is: conditioned on your rank, where in a random permutation does the first taller person sit? Averaging that over your (uniform) rank produces a harmonic sum, and harmonic sums grow logarithmically.
The single most important fact: in a uniformly random arrangement of $n$ people, $m$ of whom are "taller," the expected *position* of the first taller person is $\frac{n+1}{m+1}$, not $\frac{n}{m}$. The $m$ taller people split the line into $m+1$ gaps of equal expected size $\frac{n-m+1}{m+1}$; the first taller person sits just after the first gap, at expected position $\frac{n-m+1}{m+1}+1=\frac{n+1}{m+1}$. (Treating each encounter as an independent coin flip -- a geometric waiting time with success probability $m/n$ -- would give $n/m$ and is the classic *with-replacement* mistake; it overcounts because in a permutation the taller people cannot "re-hide" behind you.)
Quick Estimate: Take $n=100$ others. If your rank is the median, about $m=50$ are taller, so you expect the first taller person at position $\frac{101}{51}\approx 2.0$. If you are near the top with only $m=10$ taller, you expect $\frac{101}{11}\approx 9.2$. Averaging $\frac{101}{m+1}$ over $m=1,\dots,100$ gives $\frac{101}{100}(H_{101}-1)\approx 4.24$ -- so, counting the taller person you stop at, you pass only about $4$ people on average among
Approach: Condition on your height rank $k$. That fixes $m=n+1-k$, the number of the $n$ others who are taller. Use the random-permutation result $E[\text{first-taller position}\mid m]=\frac{n+1}{m+1}$ for the number of people passed (counting the taller person you stop at). Then average over the uniform rank, restricting to the cases where you actually stop ($m\ge 1$).
Formal Solution:
Label everyone by height rank
*Position of the first taller person.* Drop $m$ "taller" markers uniformly at random into a line of $n$ positions. By symmetry the $m$ markers create $m+1$ gaps (before the first, between consecutive, after the last) whose expected lengths are all equal to $\frac{n-m}{m+1}$. The first taller person occupies the position right after the first gap, so the number of people you pass *up to and including* that taller person is $E[T\mid m]=\frac{n-m}{m+1}+1=\frac{n+1}{m+1}.$ (Equivalently: each of the $n-m$ shorter others is equally likely, by symmetry, to fall in any of the $m+1$ gaps, so the expected number of shorter people *before* the first taller one is $\frac{n-m}{m+1}$; add
*Average over rank.* You stop iff someone taller exists, i.e. $m\ge 1$, equivalently $k\le n$ (rank $n+1$ = tallest = never stops, probability $\frac{1}{n+1}$). Conditioning on stopping, $m$ is uniform on $\{1,\dots,n\}$, so $E[T\mid \text{stop}]=\frac1n\sum_{m=1}^{n}\frac{n+1}{m+1} =\frac{n+1}{n}\sum_{m=1}^{n}\frac{1}{m+1} =\frac{n+1}{n}\Big(H_{n+1}-1\Big),$ since $\sum_{m=1}^{n}\frac{1}{m+1}=\frac12+\frac13+\cdots+\frac1{n+1}=H_{n+1}-1$ and $H_{n+1}=1+\frac12+\cdots+\frac1{n+1}$.
*Asymptotics.* Using $H_{n+1}=\ln(n+1)+\gamma+o(1)$ with $\gamma\approx 0.5772$, and $\frac{n+1}{n}\to 1$, $E[T\mid\text{stop}]=\frac{n+1}{n}\big(H_{n+1}-1\big)=\ln n+\gamma-1+o(1).$
*Two harmless conventions.* If instead you count only the people passed strictly *before* the taller one (not counting the person you stop at), subtract
Answer: Counting the taller person you stop at, the expected number passed is $\boxed{E[T\mid\text{stop}]=\frac{n+1}{n}\big(H_{n+1}-1\big)\;\sim\;\ln n+\gamma-1\ \text{(large }n).}$ Excluding that person subtracts
Intuition
This problem is a clean example of why harmonic numbers show up everywhere in probability. Whenever you average a geometric waiting time over a uniformly distributed "success rate," you get a harmonic sum, and harmonic sums grow logarithmically. The same structure appears in coupon collector problems, record-counting in random permutations, and the expected depth of a randomly built binary search tree. The deep reason is always the same: you are summing
In practice, this logarithmic scaling is surprisingly useful intuition. If someone asks "how many random draws until you see something extreme?" the answer is almost always logarithmic in the population size, not linear. A trader who understands this will correctly calibrate how long unusual market conditions take to appear -- and won't be surprised that extreme events are rarer than linear intuition suggests, but not as rare as exponential intuition would imply.