3 ms·
It's unintuitive, but I believe the probability ends up being 1-ln(2) if you think of n as being uniformly random.
by throwaway080383 8y ago
It's unintuitive, but I believe the probability ends up being 1-ln(2) if you think of n as being uniformly random.
- bmm6o 8y agon uniformly random from what distribution? Or are you taking a limit somewhere?
- jgtrosh 8y agoFor any power of two m, then for any range size n (with m/2 < n <= m), the probability of rejection is (m-n)/m. If any n is equally probable, then the average rejection is equal to the rejection of the average n (= 3*m/4): (m/4)/m = 1/4. This is true for any power of two m. I stand my case!
- throwaway080383 8y agoHm, yeah not sure what I was thinking. Maybe expected number of attempts?