Draw numbers from 1 to n until increasing, find conditional expectation

Question

Let's say we have a box with peaces of papers (or balls to make it easier) numbered from $1$ to $n$ - each number appears only once.

We draw balls until their numbers give an increasing sequence.

exapmle: we draw $2, 6, 12, 11$ and so we stop since $11<12$.

So, let

$X$ - number of first ball we have taken out of the box

$Y$ - amount of balls we have finally drawn

(So, in example $X=2$ and $Y=4$)

I want to find $E(Y|X)$

Does anyone have an idea how to solve it? I get lost every time I try to do it with 'brute force'.

Answer 1

Interesting question! Here is my suggestion. It is almost a complete argument, but there are some details for you to fill in.

First, let me change the question slightly. Define $T$ to be the longest initial increasing sequence. This is $Y-1$ in your notation, except when all the balls are chosen in which case $T = n = Y$.

---

Consider the following memoryless-type property.

Suppose that you are able to calculate the unconditional expectation. Let's somehow relate the conditional to this. Suppose we have $n = 100$ balls, and the first that we draw is $X = 10$. From now on, if any ball in $\{1, ..., X-1 = 9\}$ is chosen, then we 'lose'. While this is not the case, the balls are being drawn uniformly from the remainder.

That is, on the event that only balls not from $\{1, ..., 9\}$ are drawn until there is a decrease in value, the game is exactly the same as if we were just working with $n-X-1 = 90$ balls initially. (Of course, we need to increment $Y$ by $1$, since we have done a single step.)

---

Along lines suggested by @awkward, let $\sigma = (\sigma_1, ..., \sigma_n)$ be the chosen order. Also consider $\eta = (\eta_0, \eta_1, ..., \eta_n) \in \{0,1\}^{n+1}$. Consider the following slightly generalised problem.

Define $T_0(\sigma)$ to be the length of the longest initial increasing sequence in $(\sigma_1, \sigma_2, ...)$ -- so $T = Y - 1$ in your notation. Define $T_1(\eta) := \min\{ r \in \mathbb N_0 \mid \eta_r = 0 \}$. Set $T(\sigma, \eta) := T_0(\sigma) \wedge T_1(\eta)$. In words, this says "choose $T$ to be the length of the initial increasing sequence, but stop early if any of the $\eta_r$-s are $0$". (This includes terminating immediately, setting $T = 0$, if $\eta_0 = 0$.)

Now consider the case where $\sigma \sim \textrm{Uniform}(S_n)$ is a uniform permutation and $\eta \sim \textrm{Bernoulli}(p)^{\otimes n}$, ie is an iid sequence of $\textrm{Bernoulli}(p)$-s. (Here $\textrm{Bernoulli}(p) = 1$ with probability $p$ and $0$ with probability $1 - p$. The case $p = 1$ reduces to your original question.) Write $T$ for the random variable in this case.

Let's look at $\Pr(T > r)$ for some $r \in \{0, 1, ..., n-1\}$. This requires the first $r+1$ balls to be ordered in increasing order and also $\eta_0 = \eta_1 = \cdots = \eta_r = 1$. These events are independent, and have probability $1/(r+1)!$ and $p^{r+1}$, respectively. Hence $$ \textstyle \Pr_{n,p}( T > r ) = p^{r+1} / (r+1)!. $$ (Note that $\Pr_{n,p}(T > n) = 0$.) The subscript-$p$ indicates that the parameters $p \in [0,1]$ and $n \in \mathbb N$.

Using the fact that $\textrm{Ex}_{n,p}(T) = \sum_{r=0}^\infty \Pr_{n,p}(T > r)$, we obtain $$ \textstyle \textrm{Ex}_{n,p}(T) = \sum_{r=0}^{n-1} p^{r+1} / (r+1)! = \sum_{r=1}^n p^r / r! = \sum_{r=0}^n p^r / r! - 1. $$ If $n$ is large (or $p$ is very small), then this is roughly $e^p - 1$.

---

Now let's relate this to the original question. Suppose that $X = \sigma_1 = N$. Then, as described above, it is (almost) the case that $$ \textrm{Ex}_{n,1}(T \mid \sigma_1 = N) = \textrm{Ex}_{n-1, (n-N)/(n-1)}(T) + 1. $$ This is because when we select a ball we there are $N-1$ out of the $n-1$ balls which are 'bad', ie less than the first. (This is not quite true: for selecting the second ball, ie $\sigma_2$, this is the case; but for $\sigma_3$ it is now $N-1$ out of $n-2$; for $\sigma_3$, it is $N-1$ out of $n-3$; etc. However, since the expectation of $T$ is always at most $e$, only an order-1 number are chosen so this variation should be irrelevant in the limit.)

But we have an expression for this expectation. Assuming that $n$ is large (so that this approximation is probably valid), we deduce that $$ \mathrm{Ex}_{n,1}(T \mid \sigma_1 = N) \approx \exp(1 - N/n). $$

---

I hope this is helpful for you!

Answer 2

Let's call $E_{a,b}$ the expected number of future throws when you have not stopped and face $b$ remaining balls of which $a$ are higher than your current position. Your question is asking for an expression for $E_{n,n}$

You can say that $E_{a,b}=0$ if $b=0$ or $a>b$, and that $E_{a,b}=1$ if $a=0$ and $b>0$. In more interesting cases you have the recursion $$E_{a,b} =1 +\sum\limits_{i=1}^a \frac1b E_{a-i,b-1}$$ which can be simplified to $$E_{a,b} =E_{a-1,b}+\frac1b E_{a-1,b-1}$$ and that can be shown by induction to be $$E_{a,b} =\sum_{j=0}^a {a \choose j}\frac{(b-j)!}{b!}$$

You actually asked for $E_{n,n}$ which, for $n>0$, can be shown to be

$$E_{n,n} =\sum_{j=0}^n {n \choose j}\frac{(n-j)!}{n!}=\sum_{k=0}^{n-1} \frac{1}{k!}= \frac{\lfloor n!\,e - 1\rfloor}{n!}-1$$ slightly less than $e-\frac{1}{n!}$ for large $n$ and approaching $e$ as $n$ increases. For small $n$ you get $E_{1,1} = 1$, $E_{2,2} = 2$, $E_{3,3} = 2.5$, $E_{4,4} \approx 2.66667$, $E_{5,5} \approx 2.70833$, $E_{6,6} \approx 2.71667$, $E_{7,7} \approx 2.71806$, $E_{8,8} \approx 2.71825$