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?

  • 1
    $\begingroup$ The $k$ in your expression should be $m$, right? $\endgroup$ – Math1000 Jun 18 '15 at 19:36
  • 2
    $\begingroup$ 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$ $\endgroup$ – 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!}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.