Universality conjecture for normalized collision times

Let TT be the total time considered above, with expectation and variance denoted by E[T]\mathbb E[T] and Var(T)\operatorname{Var}(T), and let NN and MM be the parameters satisfying NMN \gg M. Let μ\mu be a distribution in the stated wide class. Universality conjecture. The normalized variable has distribution function

P(TE[T]Var(T)t)=1et1.\mathbb P \left( \frac{ T - \mathbb E[T]}{ \sqrt{\operatorname{Var}(T)}} \leq t \right) = 1 - e^{-t-1}.

This predicts a universal limiting law for the relevant stopping time when NN dominates MM; the source does not provide a proof or a resolution, and the intended range of distributions μ\mu should be checked.

Sources & referencesView supporting material

Primary source

Percy Deift, Stephen D. Miller and Thomas Trogdon, “Stopping time signatures for some algorithms in cryptography”, arXiv:1905.08408 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.