Re: math problem from an interview

Pascal Bourguignon said:

"Digital Puer" <digital_puer@xxxxxxxxxxx> writes:

Suppose you have a function that returns random 64-bit integers
without checking if a particular integer has already been used. How
many integers would be returned before the probability that an integer
has been repeated is above 0.5?

Depends on how 'random' it is.

If the function is _equiprobable_ on the whole range 0 2^64-1, then
you'll have to fetch 2^63 integers before the probability of getting a
repeat be above 0.5.

You reckon?

If you have n items, and choose m of them at random (equiprobably, as you
suggest), then the probability of two of them *not* being the same is:

n! / (n - m)!
-------------
m
n

For 1 bit, if you fetch two numbers, the probability of a clash is 0.5. If
you fetch a third, the probability is 1.

For 2 bits, you have to fetch three numbers to exceed 0.5.

Bits Number reqd Number of bits
to exceed in result
0.5 collision
probability
1 3 2
2 3 2
3 4 2
4 5 3
5 7 3
6 10 4
7 14 4
8 20 5
9 27 5
10 38 6
11 54 6
12 76 7
13 106 7
14 151 8
15 214 8
16 302 9
32 77163 17

As you can see, the number of bits required to represent the number you have
to fetch is approximately half the number of bits in the range, and this
approximation appears to hold good as the numbers get bigger.

So I'd expect the solution to be in the range 2^32 - 2^34 (ish), which is a
far cry from 2^63.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
.

Relevant Pages

  • Re: some interview questions
    ... A very rough approximation can be made by saying that if I choose N ... I need about 2^63 pairs to get a probability of 1/2 (I did say very ... one needs about sqrttries to get a repeat, ...
    (sci.math)
  • Re: some interview questions
    ... A very rough approximation can be made by saying that if I choose N ... I need about 2^63 pairs to get a probability of 1/2 (I did say very ... one needs about sqrttries to get a repeat, ...
    (sci.math)
  • Re: math problem from an interview
    ... many integers would be returned before the probability that an integer ... For 1 bit, if you fetch two numbers, the probability of a clash is 0.5. ... approximation appears to hold good as the numbers get bigger. ... The expected number of random number before the first collision is ...
    (comp.programming)
  • Re: A Gambling Math Question
    ... Let p be the probability of success and q = 1-p = probability of failure. ... The standard deviation is approximately sqrt. ... But the approximation comes in replacing the binomial ... distribution with a normal distribution having the same mean and standard ...
    (sci.math)
  • Re: Whew! Let me break that down.
    ... You go on to list those "repeat runs of n happen 1 in m times" ... of 3 more are the same as the chances of 3 in a row AT ANY TIME. ... the probability of each decision is exactly 1/2. ... rather illiterate snake-oil salesman. ...
    (rec.gambling.craps)
Loading