3
$\begingroup$

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2).

To paraphrase, we are supposed to use paths and an encoding scheme in order to bound the mixing time of a Markov Chain composed of state space $\Omega$ where a given state consists of a permutation of cards labeled {1,...,$n$}. Further, a valid path $\gamma_{x,y}$ between two states $x,y \in \Omega$ can be formed using no more than $n$ transitions (i.e. we can go from state $x$ to state $y$ in $n$ transitions) as follows: for each $k$ in 1 thru $n$, move card $x_k$ (i.e. the card labeled $k$) from its current position to its final position (the one occupied by the card in state $y$). So in effect, each transition step (which I will label $z_i$) in the aforementioned path is also in the form of a valid permutation, where at most two cards have swapped their positions from the previous step $z_{i-1}$.

Furthermore, to the best of my knowledge, the "flow encoding technique" and "appropriate injection" that the question mentions have to do with showing that there exists no significant "bottleneck" or "congestion" in any path between any two states $x,y$, and this in turn proves that the Markov Chain has a rapid mixing time.

So the primary difficulty I'm having is how to devise an encoding scheme $e_i$ for each stage of the transition so as to prove that, given some step of the transition $z_{i-1} \rightarrow z_i$, there exists an injection between the pair of states $x,y$ and the encoded data $e_i$. If my understanding is correct, $e_i$ itself has to be in the form of a valid permutation on {1,...,$n$} (and so $e_i \in \Omega$), and it must be possible to get back $x$ and $y$ (i.e. derive the permutations of $x$ and $y$) if all you're given is the encoding along with the transition step $z_{i-1} \rightarrow z_i$.

My understanding of the problem of course could be incorrect in some way as I'm just learning this material, in which case I'd appreciate a correction. Regardless, how might I go about devising an appropriate encoding scheme? Thanks a lot.

$\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.