2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The question is absolutely clear (although, indeed, not of the cutting edge level) - it is about understanding the basics of the theory of Markov chains - which, apparently, the people who closed it are sadly lacking. $\endgroup$
    – R W
    Nov 6 '13 at 13:03
  • $\begingroup$ @RW: I think at least the question needs an edit. Anyway, let's give the OP the benefit of doubt -- I'm casting the final vote to reopen. $\endgroup$
    – Stefan Kohl
    Nov 6 '13 at 17:24
  • $\begingroup$ why would bipartite graphs be a problem ? You can do random walks on any graphs, so why not bipartite ? $\endgroup$
    – Denis
    Nov 6 '13 at 18:43
  • $\begingroup$ @ Stefan Kohl - I agree that the formulation is pretty confused - thanks! $\endgroup$
    – R W
    Nov 6 '13 at 22:38
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks Ben for your contribution, you said "the random walk on a bipartite graph is periodic" Is this mean all nodes in different classes will be visited. or only a particular nodes from each class will be visited? $\endgroup$
    – maz
    Nov 7 '13 at 7:50
  • $\begingroup$ "Periodic" just means that you can tell which class the random walk will be in at time $t$ if you know where it started. If the graph is connected then you still expect the random walk to visit every vertex. $\endgroup$
    – Ben Barber
    Nov 7 '13 at 8:55
2
$\begingroup$

$\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$.**

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks R W for your contribution, I was thinking of that: V(G)=L Union R where L and R are disjoint and we have an edge (x,y) iff x is in L and y is in R or vice versa. 1. Let's say the walk starts at a node on L, at time t=0. Let time be discrete, i.e., t=0,1,2,... 2. The walk will always be in L whenever t=0 (mod 2) and it will always be in R whenever t=1 (mod 2). Thus, there is no stationary distribution. I said mod2 since we have two group of node in bipartite graph. Is this Correct ? $\endgroup$
    – maz
    Nov 7 '13 at 7:27
  • $\begingroup$ @maz This is incorrect. There is a stationary distribution just not one that you will converge to. For example the random walk on $\{a,b\}$ with a $\mathbb{P}[a\rightarrow b]=1/2$ and $\mathbb{P}[b\rightarrow a]=1/2$ does not converge but clearly has a stationary distribution $\pi(a)=\pi(b)=1/2$. See my answer below for more. $\endgroup$ Nov 7 '13 at 9:56

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.