Erasing numbers from the front of the row Numbers $1,2,\ldots,k$ are written in this order in a row. For $i=1,\ldots,k$, in the $i$th step, a random variable $V_i$ is drawn uniformly from the interval $[0,2i]$. If $V_i$ is greater than the first remaining number, that number is erased. What is the expected number of numbers that will be erased?
For example, if $k=1$, then we have the number $1$ and $V_1$ drawn from $[0,2]$, so $1/2$ numbers will be erased in expectation.
If $k=2$, then with probability $1/2$ we have $V_1>1$ and it is 50-50 whether the second number is erased. Otherwise $V_1<1$ and with probability $3/4$ the first number is erased. So the answer is $(1/2)(3/2)+(1/2)(3/4)=9/8$.
For $k=3$, a similar case analysis shows that the answer is $85/48$ (if I calculated correctly.) It could be that no closed form can be found in general. If so, upper/lower bounds would still be interesting.
 A: Let $E_{b,k}(a)$ be the expected number of erased numbers when you have already erased $a$ numbers and you are at the $b$th shot, out of $k$ shots.
Those can be defined for $1 \le a,b \le k+1$ by induction :
When you don't have any shot left, $E_{k+1,k}(a) = a$.
When you do you have $E_{b,k}(a) = \frac 1 {2b}((a+1) E_{b+1,k}(a) + (2b-a-1) E_{b+1,k}(a+1))$.
It turns out that every $E_{b,k}$ is an affine function :
Suppose $E_{b+1,k}(a) = pa + q$ for some $p,q \in \Bbb R$.
Then $E_{b,k}(a) = \frac 1{2b} ((a+1)(pa + q)+(2b-a-1)(p(a+1)+q))
= (1-\frac 1 {2b})pa + (q+(1-\frac 1 {2b})p)$.
So, focusing on those coefficients, we have $p_{b,k} = (1-\frac 1 {2b}) p_{b+1,k}$ and $q_{b,k} = q_{b+1,k} + p_{b,k}$
Since $p_{k,k}=1$ and $q_{k,k}=0$ we have :
$p_{b,k} = \prod_{j=b}^k (1-\frac 1 {2j})$ and
$q_{b,k} = \sum_{j=b}^k p_{j,k}$.
From there it's easy to find that when we fix $b$, the sequences $(q_{b,l})_{k \ge b-1}$ satisfy the recurrence relation $q_{b,k+1} = (1-\frac 1 {2k+2})(1 + q_{b,k})$.
Since we are interested in $E_{1,k}(0)=q_{1,k}$, we get the sequence (I'll rename it $(a_k)$) that starts with
$a_0 = 0$
$a_1 = \frac 12$
$a_2 = (\frac 12 + 1)\frac 34 = \frac 98$
$a_3 = (\frac 98 + 1)\frac 56 = \frac {85}{48}$ and so on.

Let $f_k(x) = (x+1)(1-\frac 1{2k+2})$.
We can check that $f_k(\frac {2k-1}3) = \frac {2(k+1)-1}3$ and $f_k(\frac 23 k) < \frac 23 (k+1)$.
Since the $f_k$ are increasing, this implies by induction that forall $k$, $\frac {2k-1}3 < a_k \le \frac 23k$.
Letting $b_k$ be the error term $a_k - \frac {2k-1}3$, we have $b_{k+1} = (1-\frac 1 {2k+2})b_k = \frac {2k+1}{2k+2}b_k$. Then for $k \ge 1$, $b_k = \frac {(2k-1)!!}{(2k)!!}b_0 = \frac{(2k-1)!}{2^{2k-1}(k-1)!k!}b_0 = 2^{1-2k}\binom{k-1}{2k-1}b_0$
Since $b_0 = \frac 13$, we get the closed form $a_k = \frac13 ((2k-1)+2^{1-2k}\binom{k}{2k-1})$

As for the asymptotics of $(a_k)$, one can use Stirling's formula to see that it has a development in $1/\sqrt k$ at any order.
$a_k = \frac 13 (2k -1 + \frac 1 {\sqrt{k \pi}} - \frac 1 {8\sqrt{k\pi}k} + \frac 1 {128\sqrt{k\pi}k^2} + \ldots + o(k^{n- \frac 12}))$.
