Assume we have a game with two dice pools. Each dice pool consists of k n-sided dices (all dices are fair, i.e. each side has the same probability to show up).
The first dice pool is rolled once and the player rolls the second dice pool r times.
A success is when a throw of the second dice pool results in each dice being greater or equal than the dice of the first dice pool at the specific index (all dice pools are kept unsorted, but the order is important). So the 1st dice of the 1st dice pool needs to be greater or equal than the 1st dice of the 2nd dice pool, and the 2nd dice of the 1st dice pool needs to be greater or equal than the 2nd dice of the 2nd dice pool, and so on on for each dice index.
How can we calculate the probability of a success dependant on r (throws of the second dice pool)?
Below are two ways to calculate the probabilities. The first is unfortunately not usable in my case as k is in the range of 32 and n is in the range of 256.
EDIT: r is evaluated in the range of $2^0$ to $2^{80}$.
The second approach seem to result in overestimated probabilities, while I am uncertain why this is the case.
EDIT2: As the parameters I have in my example are challenging to compute any estimation to approximate the probabilites are helpful as well.
Explicit Calculation
- k = 3 (# dices in each pool);
- n = 2 (# sides of each dice);
- r = 4 (# throws of second pool)
In total there are 8 possible outcomes. The probability $p_j$ to roll each slot higher for each j outcome is:
| 1st dice | 2nd dice | 3rd dice | $p_j$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1/2 | 1/2 |
| 1 | 1/2 | 1 | 1/2 |
| 1 | 1/2 | 1/2 | 1/4 |
| 1/2 | 1 | 1 | 1/2 |
| 1/2 | 1 | 1/2 | 1/4 |
| 1/2 | 1/2 | 1 | 1/4 |
| 1/2 | 1/2 | 1/2 | 1/8 |
The probability depending on the number of r throws for each outcome can be calculated with:
$$1 – (1 – p)^{r}$$
We can sum up the probabilities and divide by the number of outcomes, which gives the overall probability for this case.:
$$ P(success) = \frac{1}{n^k} \sum_{j=1}^{n^k}{1 – ( 1 – p_j)^r}$$
$$ P(success) \approx 0.785 $$
The explicit calculation does also match with an experiment simulation. Unfortunately, this is limited as it is infeasible to calculate for high number of dices and sides of each dice.
Approach to calculate the probability without explicit calculation
The idea is to split each dice into an independent event of each other. The probability that one dice rolls higher than a given dice can be written as:
$$ P_{dice} = \frac{n+1}{2n} $$
The assumption is that each dice of the dice pool is independent. Thus, we can accumulate the probabilities over the k dices in each pool:
$$ P_{dicepool} = {\left(\frac{n+1}{2n}\right)}^k $$
To calculate the probability depending on the throws $r$, we can use the formulae in the first calculation, which results to:
$$ P(success) = 1 – {\left( 1 – {\left(\frac{n+1}{2n}\right)}^k \right)}^r $$
$$ P(success) \approx 0.888 $$
This approach seems to overestimate $ P(success) $.
Best Answer
For each $i\in \{1,\dots,r\}$, let $F_i$ be the event that the second pool fails to beat the first pool on the $i^\text{th}$ attempt. The error in your second method is that the events $F_1,\dots,F_r$ are not independent of each other, so you cannot just multiply their probabilities to get the probability of their intersection. This is because we are reusing the same rolls for the first die pool every time. If the both the first pool and second pools were rerolled each time, then you would see the $88.8\%$ figure in simulations.
In light of the crytographic context provided, I will refer to the first die pool as Alice, and the second as Eve. The following is an upper bound for the probability that Eve succeeds: $$ \boxed{P(\text{Eve wins})\le r\cdot \exp\left(-k\left(1- \frac{\ln n}{2n}\right)+5\sqrt k\right) +2^{-18}} $$ Let $Q$ be the probability that Eve beats Alice with a single attempt; my $Q$ is your $p_j$. This $Q$ is a random variable depending on Alice's initial roll. If $Q$ is fixed, then the probability Eve beats Alice in $r$ attempts is $$\mathrm P(\text{Even wins})=1-(1-Q)^r\le rQ.$$
For each $i\in \{1,\dots,n\}$, let $A_i$ be the number of numbers in $\{1,\dots,n\}$ which are greater than or equal to Alice's $i^{th}$ roll. Note $A_i$ is uniformly distributed between $1$ and $n$. For Eve to win in a single round, all of her dice need to be at least that of Alice's, so $$ Q=(A_1/n)\cdot (A_2/n)\cdots (A_k/n), $$ Taking logs, $$\ln Q =\sum_{i=1}^k \ln (A_i/n)$$ Our strategy is to find the mean and variance of each $\ln A_i$, which tells us the mean and variance for $\ln Q$. Since $\ln Q$ is a sum of independent random variables, we can approximate $\ln Q$ by a normal distribution, and use that to get good bounds on $Q$. Note $$ E[\,\ln (A_i/n)\,]=\frac1n\sum_{i=1}^n\log \frac{i}n=\frac1n \log\frac{n!}{n^n}\approx -1+\frac{\ln n}{2n} $$ The $\approx$ follows from Stirling's approximation, $n!\sim (n/e)^n\sqrt{2\pi n}$. To upper bound the variance, we use the fact that in general, $\text{Var} X\le E[(X-a)^2]$, for any $a\in \mathbb R$. Taking $a=-1$, $$ \text{Var}[\ln (A_i/n)]\le E[(\ln (A_i/n)+1)^2]=\frac1n\sum_{i=1}^n (\ln \tfrac in+1)^2\approx \int_0^1 (\ln x+1)^2\,dx=1 $$ Therefore, we have that $\ln Q$ is approximately normal with mean $k(1-\ln n/2n)$, and standard deviation $\sqrt k$. In particular, we can say $$ \ln Q\le -k\left(1-\frac{\ln n}{2n}\right)+5\sqrt{k}\qquad \text{with probability at least }1-2^{-18} $$ This gives the estimate advertised at beginning.
Note that my formula above will never give an estimate better than $2^{-18}$, since this is the probability $\ln Q$ is more than five standard deviations over its mean, and we get no guarantee on $Q$ when that happens. If $2^{-18}$ is not strong enough, then you can instead pick any positive number $t$, and write $$ P(\text{Eve wins})\le r\cdot \exp\left(-k\left(1- \frac{\ln n}{2n}\right)+t\sqrt k\right)+\frac1{t\sqrt{2\pi}}\exp(-t^2/2) $$