1
$\begingroup$

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.

$\endgroup$

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.