Score:2

Probability of getting same result from /dev/{u}random

ru flag

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

AAllgood avatar
ru flag
Is it `1 in 10000^n` where `n` is the length of bytes (or bits) pulled?
Maarten Bodewes avatar
in flag
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.
us flag
"getting the same result" --> same as what?
AAllgood avatar
ru flag
@Mikero the same twice in a row.
Score:3
ng flag

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).

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.