I am mainly confused about my reasoning/solution
Problem: I have a bag of numbers ranging from $1,2… n$. I randomly choose a number and then I throw out all numbers less than that. Then I keep choosing numbers until I've found the largest one. What's the expected number of things I have chosen?
My Argument: I expect on average to have chosen a number of $n/2$ on each pick. Hence, everytime I choose a number, I expect to discard half of them. Hence, the $E(X) = \log_2(n)$
Note that I devised this problem as an equivalent one while trying to solve the "cluster of cars on one long road" question. If this is not equivalent, please let me know but I am confident that it is. As a result of this equivalency, I know my solution is incorrect. However, I cannot pinpoint where the issue arises.
Best Answer
Here is the result of work in the comments by lulu, Henry, and me.
The expected number of balls is $E[n]=\sum_{i=1}^n\frac 1i=H_n\approx \log n + \gamma + \frac 1{2n}$, the $n^{th}$ harmonic number.
The recursion is $E[n]=1+\frac 1n\sum_{i=0}^{n-1}E[i]$ because you can imagine putting ball $n$ randomly into an arrangement of $n-1$ balls. $i$ represents the number of balls before ball $n$. You will then throw away $E[i]$ balls plus ball $n$. We define $E[0]=0$ to make this come out properly when ball $n$ is put first in line.
We have $E[1]=1$ as the base case for strong induction. Then if $E[j]=H_j$ for all $j$ from $1$ to $k$, $$\begin {align}E[k+1]&=1+\frac 1{k+1}\sum_{i=0}^{k}H_i\\ &=1+\frac 1{k+1}\left(1+(1+\frac 12)+(1+\frac 12+\frac 13)+\ldots H_{k}\right)\\ &=1+\frac 1{k+1}\left(k+\frac{k-2}2+\frac{k-3}3+\ldots\frac{k-(k-1)}{k}\right)\\ &=1+H_k-\frac k{k+1}\\&=H_{k+1}\end {align}$$ To go from the second line to the third we count the number of terms $\frac 1m$ and note that it is $n-m$