1
$\begingroup$

I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn).

We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/degree(vi). This is assuming the edges have no weights and there are no self-loops.

Also, the stationary distribution pi exists such that pi*P=pi.

For the complete graph, pi can be defined as a 1xn vector where each element equals 1/(n-1). I got this from defining each element to be deg(vi)/sum(deg(N(vi))) - the degree of node i divided by the sum of the degrees of its neighbors.

What would be the mixing time? I'm not sure how to go about finding it.

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? Do you understand the definition of mixing time? If not, you should ask about your specific confusion with that, rather than asking how to compute it in some specific case. If yes, what specifically leaves you confused in this problem? We want to help you understand concepts, not solve an exercise for you, but you haven't given us a lot to work with. If you can articulate what approaches you've tried or what specifically you are unsure about, it might be easier to help with specific answers. There's lots written about mixing time in textbooks. $\endgroup$ – D.W. Apr 9 '16 at 22:10
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – D.W. Apr 9 '16 at 22:10
  • $\begingroup$ @D.W.: So what I have stated above is exactly what I have tried. I defined the probability matrix P for Kn and then also found its stationary distribution pi such that pi*P=pi. Where I'm stuck is how to find the mixing time (not just for this example but for any graph) - honestly, I don't understand the definition of it and I couldn't find concrete examples to work off of. $\endgroup$ – TheVarunShah Apr 10 '16 at 2:33
  • $\begingroup$ The definition of mixing time is one thing, and how to find it is another. Which are you asking? It's hard to tell. If you want to know what the definition is, it'd be better to say so explicitly -- and that's independent of any specific example (but I'm sure the mixing time is defined in many textbooks, so asking about material that's available in standard textbooks probably isn't a good fit here). If you want to know what techniques there are to find it, that's a different question. This will work better if you pick one. $\endgroup$ – D.W. Apr 10 '16 at 2:55
  • $\begingroup$ @D.W.: could you define the mixing time independently? $\endgroup$ – TheVarunShah Apr 10 '16 at 5:45
2
$\begingroup$

Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the transition matrix of $M$. The variation distance between $\pi$ and $p_x^t$, which is a measure of the similarity between the distributions, is given by the formula $$ \|\pi - p_x^t\| = \frac{1}{2} \sum_{\sigma \in M} |\pi(\sigma) - p_x^t(\sigma)|. $$ The sum goes over all states in $M$. The mixing time of a Markov chain $M$ is the smallest $t$ such that for every state $x$, $\|\pi - p_x^t\| \leq 1/(2e)$ (your account may use a different constant).

Given a graph $G$ without disconnected nodes, we can define a Markov chain as follows. The state space is the vertex set of $G$. When at state $x$, the next state is chosen uniformly at random from the neighbors of $x$.

In the particular case of the complete graph $K_n$, the random walk simply chooses a random vertex different from the current vertex. As you mention, $\pi$ is the uniform distribution. Let us compute some variation distances, for some vertex $x$ (the results are the same for all vertices): $$ \begin{align*} &\|\pi - p_x^0\| = \frac{1}{2} \left[|\tfrac{1}{n} - 1| + (n-1) |\tfrac{1}{n}-0|\right] = 1 - \frac{1}{n}. \\ &\|\pi - p_x^1\| = \frac{1}{2} \left[|\tfrac{1}{n} - 0| + (n-1)|\tfrac{1}{n} - \tfrac{1}{n-1}|\right] = \frac{1}{2} \left[\frac{1}{n} + \frac{n-1}{n(n-1)}\right] = \frac{1}{n}. \end{align*} $$ In both cases we have split the sum into two parts: $\sigma = x$ and $\sigma \neq x$. For all $n$ we have $\|\pi - p_x^0\| > 1/(2e)$. For $n > 2e$ (i.e., $n \geq 6$), we see that $\|\pi - p_x^1\| < 1/(2e)$. Therefore for $n \geq 6$, the mixing time is $1$.


With some effort, we can compute explicitly the variation distances for larger $t$. The transition matrix of the Markov chain is $(J-I)/(n-1)$ (where $J$ is the all ones matrix and $I$ is the identity matrix). Denoting by $e_x$ the basis vector corresponding to $x$, we have $p_x^t = (J-I)^t/(n-1)^t e_x$. Next, notice that $(J-I)/(n-1) \cdot \mathbf{1} = \mathbf{1}$ (where $\mathbf{1}$ is the constant 1 vector), and all other eigenvectors have the eigenvalue $-1/(n-1)$ (the corresponding eigenspaces being all vectors with zero sum). In particular, we can write $e_x = \frac{1}{n} \mathbf{1} + (e_x - \frac{1}{n} \mathbf{1})$, and so $$ p_x^t = \left(\frac{J-I}{n-1}\right)^t e_x = \frac{1}{n} \mathbf{1} + \left(-\frac{1}{n-1}\right)^t (e_x - \tfrac{1}{n} \mathbf{1}). $$ Explicitly, we have $$ p_x^t(y) = \begin{cases} \frac{1}{n} + \left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right) & \text{if } y = x, \\ \frac{1}{n} - \left(-\frac{1}{n-1}\right)^t \frac{1}{n} & \text{otherwise}. \end{cases} $$ Therefore $$ \begin{align*} \|p_x^t - \pi\| &= \frac{1}{2}\left|\left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right)\right| + \frac{1}{2} \left|\left(-\frac{1}{n-1}\right)^t \frac{1}{n}\right| \\ &= \frac{1}{2(n-1)^t} \left[1 - \frac{1}{n} + \frac{n-1}{n} \right] \\ &= \frac{1}{(n-1)^{t-1}n}. \end{align*} $$ Using this explicit formula, we find that the mixing time of $K_2$ is infinity (indeed, the chain is periodic), and the mixing time of all of $K_3,K_4,K_5$ is $2$. For $n \geq 6$, as commented above, the mixing time of $K_n$ is $1$.

$\endgroup$

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.