Reducing random numbers
Pick a uniformly distributed random number between 0 and 1. Continue picking until you pick one that is larger than the previous one that you picked. What is the expected number of numbers you pick (including the one that ended the sequence)?
NB Expected means average.
NB Expected means average.
Labels: Probability
posted by Chris at
6:10 PM
16 Comments:
In my model, the average number of picks is about 31. This did not seem correct on first thought. You pick a random number then pick again till you find one larger. Most of the time you will pick something like 0.5 then you would have a 50% chance on the next pick to beat the initial pick. But I had not thought much about getting 0.98 for the first pick. Then it might be 100 or a thousand picks to beat that. The average for about 20 million initial picks yielded and average of 30.5 "re-picks".
Hi Ragknot,
Chris may need to confirm this, but I think you may have misread the question.
I think the question is asking "How long before you pick a number larger than the one preceding it", rather than "how long before you pick a number larger than the first one you picked".
I think that may alter your answer as you seem to be describing the latter interpretation in your modelling.
DA has the correct interpretation. A valid sequence would be 0.7, 0.3, 0.2, 0.4 - you'd stop there with having picked 4 numbers, the 0.4 having ended the sequence.
This problem should be suitable for confirmation by computer simulation.
Ok, then I get an average of 1.718 picks.
Hi Ragknot. You've not included the failing number in the count. i.e. you should get 2.718
I've written a proggy that confirms the result. But I'm still hoping for a mathematical result.
Sub RunTrials()
Dim nNumberOfNumbers As Long
Dim nTotalNumberOfNumbers As Long
Dim nAverageNumberOfNumbers As Double
Dim nThisPick As Double
Dim nLastPick As Double
Dim nTrials As Long
Randomize
For nTrials = 1 To 1000000
nLastPick = 1
nNumberOfNumbers = 0
Do
nThisPick = Rnd()
nNumberOfNumbers = nNumberOfNumbers + 1
If nThisPick > nLastPick Then Exit Do
nLastPick = nThisPick
Loop
nTotalNumberOfNumbers = nTotalNumberOfNumbers + nNumberOfNumbers
Next nTrials
nAverageNumberOfNumbers = nTotalNumberOfNumbers / nTrials
Debug.Print vbCr + vbCr + "Average number of numbers ="; nAverageNumberOfNumbers
Debug.Print "Deviation from e = " + Format((nAverageNumberOfNumbers - Exp(1)) / Exp(1), "0.#####%")
End Sub
-- output
Average number of numbers = 2.71850628149372
Deviation from e = 0.00826%
It says to continue picking until you pick one larger... so I think that includes the fatal pick that stops the continue.
If I remove the fatal pick then average is one less not one more.
To get 2.71, I would have to add one pick not subtract one.
Maybe I missed something.
Sub rantest2()
Randomize
Again:
N = N + 1
t = 0
pick1 = Rnd()
Cont:
t = t + 1
pick2 = Rnd()
If pick2 < pick1 Then pick1 = pick2: GoTo Cont
tot = tot + t
If N = 1000000 Then
Debug.Print "Avg"; tot / N: Stop
End If
GoTo Again
End Sub
I had t=0 at the initial pick
it should have been t=1 at initial pick, then I get 2.71...
Sub rantest2()
Randomize
Again:
N = N + 1
t = 1
pick1 = Rnd()
Cont:
t = t + 1
pick2 = Rnd()
If pick2 < pick1 Then pick1 = pick2: GoTo Cont
tot = tot + t
If N = 1000000 Then
Debug.Print "Avg"; tot / N: Stop
End If
GoTo Again
End Sub
NB To add a physical space, use "& n b s p ;", without the spaces - No Break SPace. It's infuriating that leading spaces aren't honoured and that the PRE tag isn't allowed.
I have no proof of this, but is the exact value e by any chance?
The exact answer is e.
This is interesting, but my first model was more interesting and a lot of fun to watch.
Lots of 1,2 and 3 in the results but a few whoppers. Once the initial number was 0.999999 and it took around 168,000 times to beat it. That drives the average to 31+. I didn't count the initial pick as #1. The second pick is the first to compare to the initial pick.
I've published some enhanced code Reducing random numbers that also finds the average value of the last failing and non-failing numbers. Theoretically that is 2-e/2 and 3-e.
Perhaps this one was I bit tougher than I had supposed. There
are quite a few way of doing it. I think the following is the most
straightforward one. Let E(x) be the expected number of picks to
go after having picked x. We actually want E(1). Let y be the next
number we pick. If y > x then the process ends. If y < x, then
there would be a further E(y) picks on average to go. So the
average number of picks to go is
E(x) = 1 + Integral(over y from 0 to x of E(y)).
Now differentiate with respect to x => E(x) = A*e^x, where A is
a constant. But E(0) = 1 (i.e. if you've picked 0, then you must
pick a higher number on you next throw), so A = 1. Therefore our
required E(1) = e ≈ 2.7183 picks (including the killing pick).
I do like the recursive methods. The only problem with them is,
that it's not always straightforward to get a closed form
expression from them.
NB The derivative, with respect to x, of the integral of f(y)
over y from a to x, = f(x), where f(x) is an arbitrary function.
I missed a step in my 8:08 PM solution. I got to
E(x) = 1 + integral(over y = 0 to x, E(y)). On differentiating
with respect to x you get, dE(x)/dx = E(x). That gives E(x) = A*e^x.
A non-calculus solution: If you pick n numbers at random, then
there are n! equally likely ways of arranging them. Of those,
precisely (n-1) are in the correct sequence to give exactly n picks
in total - that's e.g. for n = 4, where a > b > c > d; bcda, acdb, abdc
NB simply taking a,b,c and making it be the last number. So the
probability of stopping on the nth pick is (n-1)/n!. So the
expected number of picks is (r is the rth term):
E = 1*0 + 2(2-1)/2! + 3(3-1)/3! + 4(4-1)/4! + ... + r(r-1)/r! + ...
E = 0 +1/1! + 2/2! + 3/3! + ... + (r-1)/(r-1)! + ...
E = 1 + 1 + 1/2! + 1/3! + ... + 1/(r-2)! + ... = e (as before).
Post a Comment
Links to this post:
Create a Link
<< Home