Bayer and Diaconis famously proved that a deck of fifty-two cards will be mixed after only seven dovetail shuffles. Numberphile has a nice series of videos of Diaconis explaining the proof.

I suspect that there's some interactive proofs to show the above.

Given a group $G$ having order $O(\exp n)$ and representation $\langle S \vert R\rangle$, consider the Cayley graph $\Gamma=\Gamma(G,S)$ on the $O(\exp n)$ vertices.

Suppose Merlin tells me that, starting from the identity and choosing generators $g\in S$, a random walk on $\Gamma$ will converge to the stationary distribution $\pi$ rapidly, in time $t=O(n)$. But I am suspicious, and I need to be convinced.

Can I challenge Merlin to find a word of length less than or equal to $t$ in the group $G$ that equals a particular element of $G$ of my choosing, such that the word hashes on to a string of my choosing?

Here I have specialized to groups and Cayley graphs, which may be a red herring; any large, well-defined graph with a configuration space having nice enough properties may also be interesting. Also, I haven't formalized mixing time, but I think most reasonable definitions are polynomially related.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.