$n$ bugs moving in a line

Question

I have a line of $n$ bugs, where no $2$ bugs have the same size. They all move in the same direction. If a bigger bug is behind a smaller bug, it will eat the smaller bug. What is the expectation of the number of bugs left after a long enough time?

I am not sure how to approach this. From $n=1, 2, 3, 4$ I guess the answer might be $$ 2- \frac{1}{n!} $$ but I am not sure if this is correct and how to derive this.

For example, when $n=3$, if my bugs are $a,b,c$, where $a>b>c$, assuming they are moving from left to right, then I have the following $6$ situations.

• $a,b,c$ — 1 left
• $a,c,b$ — 1 left
• $b,c,a$ — 2 left
• $b,a,c$ — 2 left
• $c,a,b$ — 2 left
• $c,b,a$ — 3 left

then the expectation is 1*2/6+ 2*3/6 + 3*1/6 = 11/6 = 2-1/3!

Answer 1

Fun question!

Your calculation for the first three expectations is correct, but your guessed formula is not. Here is one possible approach. It will point you to some cool online resources along the way.

Let me call the expected number you are after $e(n)$. Let $B$ be the big fat guy who will eat everybody in front of him. Then the probability that $B$ is in any given place in the sequence is $1/n$, and if he is in place $i$, then the number of survivors is himself plus whatever happens behind him, which is just a question about permutations of the remaining $i-1$ bugs. Thus, you get the recursive formula $$ e(n) = \frac{1}{n}\sum_{i=0}^{n-1}(1+e(i)) = 1+ \frac{1}{n}\sum_{i=1}^{n-1}e(i). $$

Edit: See lulu's and Christian Blatter's answers for the solution to this recursion! You can easily prove that that's the solution using the series identity between harmonic numbers $$ \sum_{k=1}^n H_k = (n+1)(H_{n+1}-1). $$

Here is MAGMA code, which you can paste in the online calculator to compute this sequence:

function prob(n)
if n lt 2 then return n; end if;
return 1/n*&+[1+prob(i): i in [0..n-1]];
end function;

Now you can say

[prob(i): i in [1..10]];

and get the sequence

$$ 1, 3/2, 11/6, 25/12, 137/60, 49/20, 363/140, 761/280, 7129/2520, 7381/2520,... $$ If you multiply this by $n!$, you get an integer sequence:

$$ 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, 10628640,... $$ The encyclopedia of integer sequences recognises this as sequence A000254, and gives several interpretations for it. For example it is the total number of cycles in all permutations of $\{1,\ldots,n\}$, and you can easily prove (exercise!) that that's what it should be for your puzzle.

Answer 2

To use Linearity:

(assume no two ants have the same size)

Let $X_i$ be the indicator variable for the $i^{th}$ ant. Thus $X_i=1$ if the $i^{th}$ ant survives this process, and $X_i=0$ otherwise.

Since the largest of the first $i$ ants is equally likely to be in any of those $i$ slots we see that $$E[X_i]=\frac 1i$$

It follows that the answer is $$E=E\left[ \sum X_i\right]=\sum E[X_i]=\sum_{i=1}^n\frac 1{i}$$

Thus the answer is just the $n^{th}$ Harmonic Number.

Answer 3

Denote by $E(n)$ the expected number of surviving ants. If the smallest ant is the last in the line it will survive. If not it will certainly be eaten and have no effect on the number of surviving ants. It follows that $$E(n)={1\over n}\bigl(1+E(n-1)\bigr)+{n-1\over n}E(n-1)={1\over n}+E(n-1)\ .$$ This leads to $$E(n)=H(n):=\sum_{k=1}^n{1\over k}\ .$$

Answer 4

Here's another way to see that the answer is the Harmonic number $H_n=1+{1\over2}+{1\over3}+\cdots+{1\over n}$.

Construct the lineup of bugs starting with the biggest and ending with the smallest by wedging each bug somewhere into the existing lineup. Each new bug survives if and only if it enters at the back of the line. So the $k$th bug survives with probability $1/k$, there being $k$ positions to place it. (Note, the total number of lineups is $1\times2\times3\times\cdots\times n=n!$.)