Stationary distribution for bipartite graph

Question

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but we have two different islands in bipartite graph and connections occur between nodes from different groups.

Answer 1

There is a distribution such that, if you start a random walk in that distribution, then it will remain there for all time: the usual formula, $\pi(v) = d(v)/2e(G)$, still works. What is no longer true is that the random walk will converge to the stationary distribution as time tends to infinity independent of the start vertex, as there is an unsurmountable parity problem: if you start in one class, then you will always be in that class after an even number of steps, so the probability of being at a particular vertex is zero at every other time step. In the language of Markov chains, the random walk on a bipartite graph is periodic.

Answer 2

There is no problem with dealing with random walks and stationary distributions on bipartite graphs. Actually, integer lattices $\mathbb Z^d$ or finite cyclic groups of even order $Z_{2p}$ all give rise to bipartite graphs with respect to natural generating sets. The simple random walk on a finite connected graph always has a unique stationary distribution given by the usual formula (without any exceptions for bipartite graphs). On the other hand, the property of being bipartite can indeed be expressed in terms of random walks: a graph is bipartite if and only if the simple random walk on it has precisely two periodic classes.

Answer 3

$\newcommand{\Raw}{\Rightarrow}\newcommand{\raw}{\rightarrow}\newcommand{\N}{\mathbb{N}}$ I just want to echo a few of the other answers and add one point to RW's: I understand that the graph is bipartite if and only if $-1$ is an eigenvalue of the stochastic operator. There is a bit more info than the OP asked for but I had it handy so said I would add it.

A central question is for a given random walk whether or not the $\xi_k$ display limiting behaviour as $k\raw\infty$? If `$\xi_\infty$' exists, what is its distribution? Here $\xi_k$ is the position of the walk after $k$ steps.

One possible debarring of the existence of a limit is periodicity. Consider a Markov chain $\xi$ on a set $X=X_0\cup X_1$ with $X_0\cap X_1=\emptyset$ and neither of the $X_i=\emptyset$ for $i=1,2$. Suppose $\xi$ has the property that $\xi_{2k+i}\in X_i$, for $k\in\N_0$, $i=0,1$. Then `$\xi_\infty$' cannot exist in the obvious way. In a certain sense $\xi$ must be aperiodic for limiting behaviour to exist. This is of course the case for bipartite graphs.

Suppose $\xi$ is a Markov chain and the limit $\nu P^n\raw \theta$ exists. Loosely speaking, after a long time $N$, $\xi_N$ has distribution $\mu(\xi_N)\sim \theta$: $$\begin{align} \nu P^N\sim \theta \\\Raw \nu P^{N}P\sim\theta P \\\Raw \nu P^{N+1}\sim \theta P \end{align}$$ But $\nu P^{N+1}\sim \theta$ also and hence $\theta P\sim \theta$. So if '$\xi_\infty$' exists then its distribution $\theta$ may have the property $\theta P=\theta$. Such a distribution is said to be a stationary distribution for $P$.

Relaxing the supposition on `$\xi_\infty$' existing, do stationary distributions exist? Clearly they are left eigenvectors of eigenvalue 1 that have positive entries summing to 1.

If $k(x)\in F(X)$ is any constant function then $Pk=k$ so $k$ is a right eigenfunction of eigenvalue 1. Let $u$ be a left eigenvector of eigenvalue 1. By the triangle inequality, $|u(x)|=|\sum_yu(y)p(y,x)|\leq\sum_y|u(y)|p(y,x)$. Now $$\sum_{z\in X}|u(z)|\leq \sum_{z\in X}\left(\sum_{y\in X}|u(y)|p(y,z)\right)=\sum_{y\in X}|u(y)|\underbrace{\left(\sum_{z\in X}p(y,z)\right)}_{=1}=\sum_{y\in X}|u(y)|$$ Hence the inequality is an equality so $\sum_z\left(\sum_y|u(y)|p(y,z)-|u(z)|\right)=0$ is a sum of non-negative terms. Hence $|u|P=|u|$, and by a scaling, $\pi(x):=|u(x)|/\sum_y |u(y)|$, is a stationary distribution.

Therefore a left eigenvector of eigenvalue 1 exists and if it is positive and of weight 1 it is a stationary distribution.

How many stationary distributions exist? Consider Markov Chains $\xi$ and $\zeta$ on disjoint finite sets $X$ and $Y$, with stochastic operators $P$ and $Q$. The block matrix $$ R=\left(\begin{array}{cc}P & 0\\0 & Q\end{array}\right)$$ is a stochastic operator on $X\cup Y$. If $\pi$ and $\theta$ are stationary distributions for $P$ and $Q$ then $$\phi_c=(c\pi,(1-c)\theta)\,,\,\,\,\,c\in[0,1]$$ is an infinite family of stationary distributions for $R$. The dynamics of this walk are that if the particle is in $X$ it stays in $X$, and vice versa for $Y$ (the graph of $R$ has two disconnected components). This example shows that, in general, the stationary distribution need not be unique. Rosenthal shows that a sufficient condition for uniqueness is that the Markov chain $\xi$ has the property that every point is accessible from any other point; i.e. for all $\,x,y\in X$, there exists $r(x,y)\in\N$ such that $p^{(r(x,y))}(x,y)>0$. A Markov chain satisfying this property is said to be irreducible.

So for the existence of a unique, stationary distribution it may be sufficient that the Markov chain is both aperiodic and irreducible. Call a stochastic operator $P$ ergodic if there exists $n_0\in \N$ such that $$p^{(n_0)}(x,y)>0\,,\,\,\forall x,y\in X$$ In fact, ergodicity is equivalent to aperiodic and irreducible, and the following theorem asserts that it is both a necessary and sufficient condition for the existence of a strict distribution for '$\xi_\infty$'. These precluding remarks suggest the distribution of `$\xi_\infty$' is in fact stationary and unique, and indeed this will be seen to be the case. A nice, non-standard proof of this well-known theorem is to be found in F. Ceccherini-Silberstein, T. Scarabotti and F. Tolli. Harmonic Analysis on Finite Groups. Cambridge University Press, New York, 2008, which also discusses bipartite graphs specifically.

Markov Ergodic Theorem

A stochastic operator $P$ is ergodic if and only if there exists a strict $\pi\in M_p(X)$ such that $$\lim_{n\raw\infty} p^{(n)}(x,y)=\pi (y)\,,\,\,\forall x,\,y\in X$$ In this case $\pi$ is the unique stationary distribution for $P$.**