Quadratic upper-bound conjecture for random card shuffling

About 4 years old · traced to

Let DD be a deck with nn cards of each type, and let λD\lambda_D denote the expected number of steps to absorption for the random card-shuffling process started from DD. As n→∞n\to\infty, quadratic upper-bound conjecture. There is an absolute constant C≤2C\leq 2 such that

max⁡{λD ⁣:D any deck}≤Cn2+o(n2).\max\{\lambda_D\colon D\text{ any deck}\}\leq Cn^2+o(n^2).

The conjecture is motivated by experimental data for decks with n=26n=26 and asserts that the worst-case expected absorption time is asymptotically at most quadratic in nn, with leading constant no greater than 22; its status is not established in the supplied source.

References

Primary source

Joel Brewster Lewis and Mehr Rai, “A Random Card Shuffling Process”, arXiv:2206.04614 (2022).

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.