An adversary Craig tries to log-in as Alice on a system that will only accept the right password, leaks (only) if an attempt succeeds, and allows many attempts.

Alice's password choice is modeled as a random pick in a finite set of $m$ possible passwords $P\_i$ each with probability $p\_i$, with $0\le i<j<m\implies p\_i\ge p\_j>0$ , and $1=\displaystyle\sum\_{0\le i<k}p\_i$ .

Assume Craig has a perfect model of Alice's password choice and tries up to $n$ passwords $P\_i$ by increasing $i$ (with $0\le n\le m$), stopping if he logs-in. That success for Craig has probability $q\_n=\displaystyle\sum\_{0\le i<n}p\_i$ .

We know $n$, $m$, and the password distribution's [Shannon entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)#Definition) $H=\displaystyle-\sum\_{0\le i<m}p\_i\cdot\log\_2(p\_i)$ . For a uniform distribution of the $p\_i$, we'd have $q\_n=n/m=n/2^H$ . But we do not know said distribution.

**How can we rigorously, and tightly, bound Craig's success probability** $q\_n$ ?

Clarification: it is asked upper and lower bounds of $q\_n$ as a function of $(n,m,H)$.

What if we additionally have the [min entropy](https://en.wikipedia.org/wiki/Min_entropy) $H\_\text{min}=-\log\_2(p\_0)$ or some other interesting metric of the probability distribution?

---

Now there are $u$ users Alice, Bob.. that (we assume) have chosen their password independently of each others, but per the same distribution. Craig knows user logins, and tries $P\_i$ for each user before moving to $P\_{i+1}$. He stops when he logs into the account of any user, or has made $n$ tries, with $0\le n\le (m-1)\cdot u+1$ .

What does the bounds become?

---

Suggested numerical illustration: for $n=1000$ out of $m=2^{48}$, $H=20$-bit entropy, what bound can we get for $q\_n$? If we additionally assume $H\_\text{min}=12$? Or with $u=2^{10}$?

---

Does some property that actual distributions of password choice tend to have let us tighten the bounds?