\documentclass{article}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}




\begin{document}
\centerline{\bf \noindent Homework 2} 
\noindent {\bf Due: Wednesday, October 13, 2021 before the start of class at 11am. }
\\
Type your solutions using Latex and turn-in via Gradescope.   \\
Let me know if you're having difficulties and I'll give you help/hints.  \\
Zoom office hours are Tuesdays/Thursdays at 9pm.

\vspace{.2in}

{\bf \noindent Problem 1:}

Consider the following Markov chain for shuffling a deck of $n$ cards.
Let $\Omega$ denote the set of all $n!$ permutations of $\{1,2,\dots,n\}$.
We will choose a random position $i$ and a random card $c$, then 
we will swap card $c$ with the card in position $i$. Formally it is the following. 

{\em Notation:} For a state $X\in\Omega$, let $X=(x_1,\dots,x_n)$ denote the permutation where 
$x_i$ is the card in the $i$-th position and let $X^{-1}(c)$ denote the position of 
card $c\in\{1,\dots,n\}$.  For example, for $X=(3,4,2,1,5)$ then card $3$ is in the first position
and $X^{-1}(2) = 3$ as card 2 is in position 3.

{\em Markov chain:}.   
From $X_t\in\Omega$,
\begin{enumerate}
\item Choose a position $i$ u.a.r. from $\{1,\dots,n\}$ and a card $c$ u.a.r. from $\{1,\dots,n\}$.
\item Let $j=X^{-1}_t(c)$ denote the position of card $c$ in the current permutation $X_t$.
\item Swap the cards in positions $i$ and $j$, i.e., let 
\[ X_{t+1}(i) = X_t(j), X_{t+1}(j) = X_t(i), \mbox{ and for all }k\neq i,j, X_{t+1}(k)=X_t(k).
\]
\end{enumerate}

{\bf \noindent Part (a):} Show that this chain is ergodic with uniform stationary distribution.

{\bf \noindent Part (b):} Give a coupling argument to prove that the mixing time is $O(n^2)$.

Hint: you should end up with a coupon collector type argument at the end of your analysis but
the probabilities of collecting the coupons will be on the order of $1/n^2$ (instead of $1/n$).

Note: It is OK to use path coupling, however it is a bit subtle to do so correctly.  In particular,
be careful with the set $S\subset\Omega\times\Omega$ that you use as ``neighboring'' pairs
and with the definition of the distance metric, make sure it's a path metric (i.e., for 
every pair $(X,Y)\in\Omega\times\Omega$ the shortest path in $(\Omega,S)$ between
$X$ and $Y$ is  of length equal to the distance between $(X,Y)$).



\end{document}
