0
$\begingroup$

I have an infinite stream of good random numbers available to me that range 0 - 255. I draw them in pairs. In how many pairs will both numbers be equal?

I think that this is a form of Birthday Problem, but I can't do the math. Empirically, it's about 3% for me. It would be useful to know the exact theoretical amount as a percentage.

$\endgroup$
2
$\begingroup$

There's no birthday-paradox effect here. In the birthday paradox, the somewhat unintuitive solution comes from the fact that you have several people and the possible ways of choosing two increase quadratically with the total number of people in the room. In your problem, you just draw two random numbers from the range $[0,255]$ repeatedly (you could map that onto rolling a $256^2$-sided die). As you haven't mentioned it: I assume a i.i.d. uniform distribution.

Regarding the solution: choose one fixed number $i$. The probability to draw two times $i$ is $p_i = \frac 1 {256^2}$. And as you have $256$ numbers, the probability for a pair is

$$p = \frac{1}{256}$$

(The die analog again: just as for two six-sided dice the probability for a pair is $\frac{1}{6}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.