Expectation value of number of drawings of increasing sequences of labelled balls from an urn.

Question

An urn contains $n$ balls, labelled from $1$ to $n$. A sequence of drawings with re-insertion is made, until the drawn ball is labelled with a number which is less than or equal to the number of the previous drawing. a. Given a positive integer $k$, find the probability that the number of drawings is greater than $k$; b. Find the expectation value of the number of drawings.

Here is what I've done. For $k = 0$ and $k = 1$, the probability is $1$: after the first drawing is done, at least another drawing has to be done, to determine whether the sequence terminates. For $k \ge n$ probability is $0$: if one has drawn the sequence $1,\dotsc,n$ then she will surely draw a ball labelled with a number less than or equal to $n$. Thus, the interesting events are ones with $1 \le k \le n-1$.

First part

Sketching the situation and naming $X$ the number of drawings, I've conjectured that $$ \mathbb{P}(X \ge k) = \frac{\sum_{j=k+1}^{n-1} \binom{n}{j}}{n^n} $$

Why is it wrong? Simply because I've totally forgot about the terminating drawing. If a sequence of $k$ drawings is obtained, what we have is:

1. A sequence of $k-1$ increasing drawings, which can be counted like order-less drawings sequences of length $k-1$, i.e $\binom{n}{k-1}$ choices;
2. A last drawing, which results in a number $k'$ such that $k' \le \max{(d_1,\dotsc,d_{k-1})}$ where $d_i$ is the $i$-th drawing label.

How can I incorporate that second point in my formula?

Second part

Then, I'm stuck on the computation of the expectation value.

1. Is my reasoning broken from beginning? How can I justify my conjecture? 2. Which is the correct way of computing expectation value? I've tried with $$\mathbb{E}(X) = \sum_{k=0}^\infty \mathbb{P}(X \ge k), $$ is that right?

Answer 1

For the first part, the number of drawings is greater than $k$ if and only if the first $k$ balls drawn were all increasing. You don't have to consider the final drawing, precisely because we're considering the cases where the final drawing is not among the first $k$.

The probability that the first $k$ drawings form an increasing sequence is $$\frac{\binom{n}{k}}{n^k}$$ as there are $\binom{n}{k}$ different increasing sequences, out of the $n^k$ possible drawings of the first $k$ balls. (Note: if it bothers you that we may stop before $k$ balls, we can assume a setting where we keep drawing even after the "bad" draw, and consider in that setting the probability that the "bad" draw did not happen among the first $k$ draws, which you can convince yourself is the same probability that we want.)

For the second part, for a random variable $X$ that takes nonnegative integer values, it is true that $$E[X] = \sum_{k \ge 1} \Pr(X \ge k) = \sum_{k \ge 0} \Pr(X > k)$$ (can you prove this?), and you have already calculated $\Pr(X > k)$ in the first part. To evaluate $E[X]$ as a closed form, use the fact that $\sum_{k \ge 0} \binom{n}{k} x^k = (1 + x)^n$ (the binomial theorem), with $x = \frac1n$, to get $$E[X] = \left(1 + \frac{1}{n}\right)^n$$ (which, incidentally, approaches $e \approx 2.718...$ as $n \to \infty$).

Answer 2

I think $P(X\geq k) = P(X>k-1)= \frac{n}{n}\frac{n-1}{n}...\frac{n-(k-1)}{n}$ whenever $1\leq k\leq n$, then use your formula.