Draw numbers from 1 to n until increasing, find conditional expectation 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'.
 A: 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!
A: 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$
