# Calculating binomial distribution probability for dependent trials

Context:

I am a software developer and recently we've had a bug report saying that one of our login systems are potentially insecure to a brute-force attack. I need to come up with a formula to calculate the success rate given X attempts, and vice versa, to accurately determine the current risk of our login system.

The problem:

Imagine that there is a website which requires you to specify a 6-digit number to log in. In total, there are 20 valid numbers, each of which will grant you access. Every 30 seconds, a new valid 6 digit number is created, and the oldest 6 digit number is no loger valid. Assuming you can make 100 guesses/second, how many seconds would it take to have a 50% chance of guessing at least 1 number?

Ideally, the answer would be a function which takes as parameters:

• Total number of codes (10^6 = 1,000,000)
• Number of valid codes (20)
• Code renewal speed (30s)
• Guess rate (100 guesses/second)
• Desired success chance (50%) or number of attempts(10,000)

and outputs either the required number of attempts if given a desired success chance, or the resulting success chance if given the number of attempts.

My wrong solution

I tried coming up with a solution by using a normal binomial distribution calculator such as https://stattrek.com/online-calculator/binomial with:

• success chance per trial: 20/1 000 000
• Number of trials: 10 000
• Number of successes: 1

But then I realized that the problem with that is that it doesn't take into account that the trials are dependent. After every trial, we know that in the next trial, the number we tried before is not correct, so for every next trial, we don't need to guess 20/ 1 000 000 numbers, but rather 20 / 999 999 and so on, until 30s pass and 1 out of the 20 valid numbers changes.

A good approximation can be had by ignoring the code renewal process. The number of attempted queries follows a negative hypergeometric distribution with this simpler model. Comparing the approximation with results from a simulation in R:

First, a function to simulate the process described.

fsim <- function(x) {
ncodes <- 1e6
n1 <- ncodes - 1
nvalid <- 20
renew.speed <- 30
guess.rate <- 100
qr <- renew.speed*guess.rate
N <- 1e3 # replications
nqueries <- numeric(N)
for (i in 1:N) {
inext <- ncodes
codes <- sample(0:n1, nvalid)
from <- 1
to <- qr
repeat {
if (from > to) {
hit <- codes >= from
if (any(hit)) {
nqueries[i] <- nqueries[i] + min(codes[hit]) - from + 1
break
}
hit <- codes <= to
if (any(hit)) {
nqueries[i] <- nqueries[i] + min(codes[hit]) + ncodes - from
break
}
} else {
hit <- codes >= from & codes <= to
if (any(hit)) {
nqueries[i] <- nqueries[i] + min(codes[hit]) - from + 1
break
}
}
nqueries[i] <- nqueries[i] + qr
from <- (from + qr)%%ncodes
to <- (to + qr)%%ncodes
inext <- if (inext == ncodes) 1 else inext + 1
codes[inext] <- sample((0:n1)[-codes - 1], 1)
}
}
nqueries
}


Run the simulation in parallel (on 15 nodes):

library(parallel)
cl <- makeCluster(detectCores() - 1L)
nqueries <- unlist(parLapply(cl, 1:length(cl), fsim))
stopCluster(cl)
length(nqueries)
#> [1] 15000


Compare the two approximations.

median(nqueries)/100 # estimate from simulation (in seconds)
#> [1] 335.585
extraDistr::qnhyper(0.5, 1e6 - 20, 20, 1)/100 # estimate from negative hypergeometric distribution
#> [1] 340.64

• Thanks for the answer! I studied a bit about negative hypergeometric distribution and saw that it is used for sampling without replacement. This is fine for a guess rate of 100 guesses/second, since it amounts to ~340 seconds needed for a 50% chance. But what about for a slower guess rate, lets say 10 guesses/second, I think that would be better modeled by using sampling with replacement. Is there a thing such as negative hypergeometric distribution but with sampling with replacement? Commented Apr 3 at 11:30
• Take a look at the negative binomial distribution. The geometric distribution would apply here. It is a special case of the negative binomial distribution where $r=1$. Commented Apr 3 at 11:40
• Cool, thanks! Would give you an upvote but I don't have enough rep :( Commented Apr 5 at 13:39