4
$\begingroup$

Let $S_n$ be the symmetric group on $n$ elements. Now, we pick a random transpositions to generate random walks on $S_n$ (also assume the probability of picking each transposition is equal of course). There are $n(n-1)/2$ transpositions. How many does is need on average (expectation) to get back to the identity $(1)$? Namely, what is the expectation step of a random walk on $S_n$ first hit the identity?

I could compute the case for 2,3, and 4. The expectations are simply 2, 6, 24. So I guess it is $n!$.

$\endgroup$
4
$\begingroup$

In general, for an irreducible, aperiodic Markov process on a finite state space, the expected return time to a state $x$ is always the reciprocal of the unique steady state probability for $x$. To see this, let $T_0,T_1,T_2,\dots$ be the return times to $x$ when the Markov process starts at $x$, where we define $T_0=0$. Note that $${T_n\over n}=\frac1n\left[(T_1-T_0)+(T_2-T_1)+\dots+(T_n-T_{n-1})\right]$$ By the strong law of large numbers, $T_n/n\to E[T_1]$, the expected return time to $x$. On the other hand, $n/T_n$ is the proportion of visits to $x$ among the first $T_n$ steps of the process, since there were exactly $n$ visits. Since we assumed the process converges to a unique steady state vector, we must also have $n/T_n\to p_{\infty}(x)$.

Your random walk on $S_n$ is irreducible and aperiodic. Since symmetry implies the steady state probability for all group elements is equal, it must be $1/n!$ for each, so the expected return time for all elements is $n!$.

$\endgroup$
1
  • $\begingroup$ Thank you very much. Do you have some reference for this or in general Markov process as I am not very familiar with it. $\endgroup$
    – CO2
    Nov 27 '21 at 18:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.