If r is a uniformly distributed random number between 0 and 1, what is the probability that floor(log2(1/r)) is odd?
f(r)=floor(log2(1/r))
From 1/2 to 1 the function is 0: even
From 1/4 to 1/2 the function is 1: odd
From 1/8 to 1/4 the function is 2: even
From 1/16 to 1/8 the function is 3: odd
etc
Each even interval has a corresponding odd interval which is half as wide, so overall the P(even)=2*P(odd)
P(even) = 2/3
P(odd) = 1/3
This can also be seen as an alternating geometric series
1/2-1/4+1/8-1/16+1/32-1/64 ... = 1/3
In general for base b logarithm
P(odd) = 1/(b+1)
The above formula works for any positive real base (except 1)
|
|
Posted by Jer
on 2018-02-04 13:19:07 |
Solution with generalization
