Modeling Pseudorandom Number Generator Without Replacement

Question

I vaguely recall a definition of a pseudorandom generator from cryptography. My rephrasing here:

No adversary can (with non negligible probability) predict the next bit of a uniformly (pseudo)random sequence of bits with accuracy substantially greater than 50%

I define two number generators as follows:

A: I generate 100 bits by flipping a fair coin 100 times

B: I generate 100 bits by writing 50 0's and 50 1's on the back of 100 cards, then I shuffle the cards together perfectly, and report the numbers on the back of each card.

Certainly it is easy for an adversary to guess the 100th bit of the B so long as it can see the previous 99 bits. But what if the adversary must predict all 100 bits simultaneously?

If the adversary must guess 100 bits at a time, what is the probability they correctly guess 60 or more of the bits?

For A: I believe this can be determined by the binomial distribution. For B: How do I determine this? Is this the hypergeometric distribution?

---

(I'm trying to determine a proper null distribution for a classifier that predicts X% of a class balanced test set if the input data is completely irrelevant to the classification)

---

Clarification, for my exact use case, the adversary is unconstrained in their guesses, they may guess all 0's or all 1's if they so choose.

I believe they must also make all of their 100 guesses individually and independently, which may reduce their predictive ability back to case A, but I'm curious if they can somehow do better on B.

Answer 1

A) Binomial. 40 or fewer errors out of 100 can be computed exactly in R as follows:

pbinom(40, 100, .5)
[1] 0.02844397

B) Then one approach is to say that I have a random permutation of fifty $0$'s and fifty $1$'s. And, independently, so do you. What is the probability that we have at least 60 matches in sequence? By simulation, the answer is about $0.0358\pm 0.0004.$ (Better than binomial.)

set.seed(2020)
deck=rep(0:1,each=50)
match = replicate(10^6, sum(sample(deck)==sample(deck)))
mean(match>=60)
[1] 0.035784
2*sd(match >= 60)/1000
[1] 0.0003715026

However, the rules have to be carefully stated.

• If it is agreed that you will always have exactly 50 $0$s and exactly 50 $1$s and I can make unconstrained guesses, then I could predict all one hundred to be $0$'s and be right exactly half the time.
• By contrast if I must have exactly fifty of each and you can sample each bit independently 50-50 at random, then the probability of $60$ or more matches is about $0.0285.$ (Binomial again.)

.

set.seed(717)
deck=rep(0:1,each=50)
match = replicate(10^6, sum(sample(deck)==sample(0:1,100,rep=T)))
mean(match>=60)
[1] 0.028491

Answer 2

In option A, as BruceET says, any strategy by the guesser will lead to the same binomial distribution. In particular the expected number of correct bit guesses will be $50$, and the probability of $60$ or more correct guesses will be $\sum\limits_{n=60}^{100} {100 \choose n}/2^{100} \approx 0.028444$

In option B, where the guesser knows that there are $50$ zeros and $50$ ones in some random permutation, the probabilities of various possible number of correct guesses is affected by the strategy. If all the bits have to be guessed in advance, the expected number of correct answer will again be $50$ with any strategy by linearity of expectation but you can also say

• guessing each bit independently with zero and one each having a probability of $\frac12$ will again lead to a binomial distribution and give a probability of $60$ or more correct guesses of $\sum\limits_{n=60}^{100} {100 \choose n}/2^{100} \approx 0.028444$
• the guesser also producing a random permutation of $50$ zeros and $50$ ones will lead to what is essentially a hypergeometric distribution,and a probability of $60$ or more correct guesses of $\sum\limits_{w=30}^{50} {{50 \choose w}{50 \choose 50-w}}/{100 \choose 50} \approx 0.035671$ (BruceET's simulation is consistent with this)

You might think this is improvement comes from the guesser adopting the same strategic option as the original question. That is not really the dominant effect; much more important is that the second strategy is guaranteed to produce an even number of correct answers, and your critical region of "$60$ or more" starts with an even number.

Suppose you instead had a critical region of "$59$ or more":

• guessing each bit independently would give a probability of $59$ or more correct guesses of $\sum\limits_{n=59}^{100} {100 \choose n}/2^{100} \approx 0.044313$
• the guesser producing a random permutation of $50$ zeros and $50$ ones will again lead to a probability of $\sum\limits_{z=30}^{50} {{50 \choose z}{50 \choose 50-z}}/{100 \choose 50} \approx 0.035671$ of $59$ or more correct guesses, since exactly $59$ is impossible
• the guesser producing a random permutation of $51$ zeros and $49$ ones (or $49$ zeros and $51$ ones) will lead to a probability of of $\sum\limits_{z=30}^{50} {{50 \choose z}{50 \choose 50-z}}/{100 \choose 51} \approx 0.054542$ of $59$ or more correct guesses, and always gets an odd number correct

so this parity based strategy would perform better than either of the other two.