| Well, it may be easy, but this solution isn't very elegant.....
Define a series of functions Pn(x) as
Pn(x) = the probability that the next n random numbers are in ascending
order and greater than x.
From the definition of Pn, the following recurrence can be seen:
1
Pn(x) = S Pn-1(y) dy (sorry for the crummy integral sign)
x
(i.e. "iff the next random number is > x and the next n-1 are greater than that
one and ascending, then all n random numbers are > x and ascending")
and (assuming the distribution of random numbers is uniform between 0 and 1),
P1(x) = 1-x n
(1-x)
You can now show by induction that Pn(x) = -------
n!
The expected value of the number of ascending random numbers greater than X is:
E(X) = 1*(P1(X)-P2(X)) + 2*(P2(X)-P3(X)) + 3*(P3(X)-P4(X)) + ...
1-X
= P1(X) + P2(X) + P3(X) + ... = e - 1
and the number you seek is E(0).
Now, what's the elegant solution?
|
| Elegant? Well, that wasn't promised - just that it was easy. Anyway,
here's my approach:
1) The probability that a sequence of random numbers as described in
the base note is exactly of length n is
n / (n+1)!
because there are exactly n ways in which n+1 numbers can be ordered
so that the first n are ascending and the n+1st is less than the
nth; out of the total possible orderings of n+1 numbers.
2) The expectation of the infinite series is
1*p(n=1) + 2*p(n=2) + 3*p(n=3) + ... + m*p(n=m) + ...
m 2
= Lim Sigma n /(n+1)!
m->00 n=1
m
= Lim Sigma [(n-1)*(n+1)+1]/(n+1)!
m->00 n=1
m m
= Lim Sigma (n-1)*(n+1)/(n+1)! + Lim Sigma 1/(n+1)!
m->00 n=1 m->00 n=1
m m
= Lim Sigma (n-1)/n! + Lim Sigma 1/(n+1)!
m->00 n=1 m->00 n=1
m m m
= Lim Sigma n/n! - Lim Sigma 1/n! + Lim Sigma 1/(n+1)!
m->00 n=1 m->00 n=1 m->00 n=1
m m m
= Lim Sigma 1/(n-1)! - Lim Sigma 1/n! + Lim Sigma 1/(n+1)!
m->00 n=1 m->00 n=1 m->00 n=1
= e - (e-1) + (e-2)
= e-1
|