Expressing the expected value in a simpler form

We randomly set numbers $(1, 2,\ldots, n)$ in the sequence $(a_1,\dots,a_n)$. Let $N$ be the largest number such that for $2 \le k \le N$ we have $a_k>a_{k-1}$. Find $\mathbb{E}N.$

Lets start from computing $Pr(N=m)$:

$$\Pr(N=m)=\Pr(N \ge m)-\Pr(N \ge m+1)=\frac{{n \choose m} (n-m)!}{n!}-\frac{{n \choose m+1}(n-m-1)!}{n!}$$

So $$\mathbb{E}N=\sum_{m=1}^n m \left(\frac{{n \choose m}(n-m)!}{n!}-\frac{{n \choose m+1}(n-m-1)!}{n!}\right).$$

I have a problem with expressing $\mathbb{E}N$ in a simpler form. Could you help?

• The $k$ in your expression should be $m$, right? – Math1000 Jun 18 '15 at 19:36
• I'm pretty sure you have the expression for Pr($N=k)$ wrong. Try it for $n=10$ and $k=2$; your expression gets $\frac{1}{10!} (10-45) < 0$ – Mark Fischler Jun 18 '15 at 19:37

Start from the correct expression for $$\Pr(N\geq m) = \frac{1}{n!} \binom{n}{m} (n-m)!$$ because having chosen the first $m$ numbers -- which can be ordered in only one way -- the other $n-m$ numbers can be placed in any order.

Also, we must define, for sequences with $a_0 > a_1$, that for such a sequence $N = 1$ since for $N = 1$ there are no $k$ values with $2 \leq k \leq N$ and your condition is true vacuously.

Then you have $$\Bbb{E}(N) = \sum_{m=1}^{n-1} m\left[ \binom{n}{m} \frac{(n-m)!}{n!} - \binom{n}{m+1} \frac{(n-m-1)!}{n!} \right] + \frac{n}{n!}$$ where I have separated out the end case of $N=n$ because that one has no subtraction term.

W notice considerable simplifications; and later we will be working with sums of $\frac{m^2}{m+1)!}$ which can be broken up using $$m^2 = m(m+1) -(m+1) +1$$

In the end, you get the answer $$\Bbb{E}(N) = \sum_{m=1}^n\frac{1}{m!}$$

No further simplification is available, except to notice that for large $n$ this rapidly approaches $e-1$.

It is simplest not to have to simplify. If a random variable $N$ only takes on non-negative integer values, then by a standard result, $$E(N)=\sum_{i=1}^\infty \Pr(N\ge i).$$ In our problem, it is convenient to let $N=1$ if $a_1\gt a_2$. Whatever set happens to be chosen as the first $i$ elements, the probability these are in order is $\frac{1}{i!}$. So for all $i$ with $1\le i\le n$, we have $\Pr(N\ge i)=\frac{1}{i!}$. It follows that $$E(N)=\frac{1}{1!}+\frac{1}{2!} +\frac{1}{3!}+\frac{1}{4!}+\cdots+\frac{1}{n!}.$$

Another way: For $i=1$ to $n$, define random variable $X_i$ by $X_1=1$, and for $2\le i\le n$, by $X_i=1$ if $a_1\lt a_2\lt \cdot \lt a_i$, and by $X_i=0$ otherwise. Then $N=X_1+X_2+X_3+\cdots+X_n$.

By the linearity of expectation we have $E(N)=E(X_1)+E(X_2)+E(X_3)+\cdots+E(X_n)$. We have $E(X_i)=\Pr(X_i=1)=\frac{1}{i!}$. Summing, we obtain the answer.

Remark: One could define $N$ to be $0$ if $a_1\gt a_2$. Then minor modification needs to be made, and the expectation turns out to be $\frac{1}{2!}+\frac{1}{2!}+\frac{1}{3!}+\cdots +\frac{1}{n!}$.