Re: Funky random number choosing

In article
<1193154890.814743.172740@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
, thomasjack <thomasjack@xxxxxxxxx> wrote:
Let {r_n} be a sequence of reals in (0,1] generated by a uniform
random number generator, with n=0,1,2... Let x be the smallest r_n for
which r_(n+1) > r_n. What's the expected value of x?

For example, if the sequence of random numbers came up "0.06, 0.21,
0.95, 0.93...", then x would be 0.95.

I think you mean the first r_n for which r_{n+1} < r_n.

After a few million trials I believe the expected value is around
0.718 (could it be e-2?), but I am having trouble deriving the exact
value.

m uniformly distributed values can be ordered in m! ways.
The number of permuations where r1 < r2 < ...< r_{m-1} > r_m is m-1.
The probability is (m-1)/m!.
The expected gap for m uniformly distributed values is 1/(m+1).
The expected value of r_{m-1} is

sum_{2 <= m}(1 - 1/(m+1)).(m-1)/m!
= sum_{2 <= m}[m/m! - 1/m! - (1/(m+1).(m+1 - 2)/m!]
= sum_{2 <= m}[m/m! - 1/m! - 1/m! + 2/(m+1)!]
= (e-1) - 2(e-2) + 2(e - 2 - 1/2)
= e - 1 - 1
= e - 2.

--
Michael Press
.

Relevant Pages

  • Re: Funky random number choosing
    ... thomasjack writes: ... random number generator, with n=0,1,2... ... For example, if the sequence of random numbers came up "0.06, 0.21, ... The solution of this differential equation with initial value u= 1 is ...
    (sci.math)
  • Re: Funky random number choosing
    ... thomasjack wrote: ... random number generator, with n=0,1,2... ... And in the full sequence, there are bound to be many values of r_n smaller than 0.06 for which r_>r_n, and the probability that a "smallest" exists is infinitesimal. ... --Mike Amling ...
    (sci.math)