Pregunta

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.

No hay solución correcta

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top