2
$\begingroup$

What is the likelihood of getting the same result from /dev/random?

$\endgroup$
4
  • $\begingroup$ Is it 1 in 10000^n where n is the length of bytes (or bits) pulled? $\endgroup$
    – AAllgood
    Apr 5 at 16:30
  • $\begingroup$ Bits have 2 options per bit, so you would expect 1 in $2^n$ if the output is well distributed (to match any specific n-bit value per extraction, previously generated or not). Generally you'd expect it to be well distributed, but in the end that's an implementation question. $\endgroup$
    – Maarten Bodewes
    Apr 5 at 16:42
  • 2
    $\begingroup$ "getting the same result" --> same as what? $\endgroup$
    – Mikero
    Apr 5 at 16:49
  • 1
    $\begingroup$ @Mikero the same twice in a row. $\endgroup$
    – AAllgood
    Apr 5 at 16:57

1 Answer 1

3
$\begingroup$

I'll read the question as: we draw two bitstrings $S$ and $S'$ each of $b$ bit(s) from /dev/{u}random, assumed an ideal random generator (which is it's aim). What's the probability that $S$ and $S'$ are identical, noted $\Pr(S=S')$ ?

Note: if $b$ is a multiple of $8$, $S$ and $S'$ can be thought as bytestrings each of $b/8$ bytes.

A simple way to solve this is to consider that $S'$ was chosen after $S$, and uniformly at random, independently of $S$, among the values $S'$ can get. Since $S'$ is $b$-bit, there are $2^b$ such values, and each has probability $p=1/2^b=2^{-b}$ to be chosen (since the sum of all probabilities must be $1$, and each of the $2^b$ values has the same probability). Since $S$ is $b$-bit, $S$ is one of these $2^b$ values. Therefore $$\Pr(S=S')\,=\,1/2^b\,=\,2^{-b}$$

Note: at first I considered the question so simple that it's best answered by who asked the question, and closed it. Perhaps that was a mistake. I realized there is pedagogical interest in a precise argumentation with standard notation for that elementary question (and, as an aside, that I had made a sign mistake in an initial comment, now deleted).

$\endgroup$
0

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.