A random walk on the $n$-hypercube

1.5k Views Asked by At

The stationary distribution for a simple random walk on a nonweighted graph gives

$$\pi _{v}=\frac{deg(v)}{\sum_{z}^{}deg(z)} = \frac{deg(v)}{2e},$$

where $e$ denotes the number of edges of the graph.

We can show this is stationary by proving that $\boldsymbol{\pi }=\boldsymbol{\pi }\boldsymbol{P}$.

$$(\pi P)_{v}=\sum_{w}\pi _{w}P_{wv}= \sum_{w\sim v}\frac{deg(w)}{2e}\frac{1}{deg(w)}=\frac{1}{2e}\sum_{w\sim v}1=\frac{deg(v)}{2e}=\pi _{v}.$$

To make use of this, we can look at the hypercube.

The $n$-hypercube graph has $2^{n}$ vertices. The sum of the degrees of the vertices is $n2^{n}$. So,

$$\pi _{v}=\frac{n}{n2^{n}}=\frac{1}{2^{n}}.$$

The distribution is uniform. This is because all of the vertex degrees are the same.

How does this concept change when the graph is weighted?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider a general graph on $n$ nodes. Let the weights be $w_{ij}\geq 0$, and assume $w_{ij} = w_{ji}$, so the graph is still undirected. For all $i \in \{1, ..., n\}$ define $w_i$ as the sum of all weights out of node $i$:
$$ w_i = \sum_{k=1}^n w_{ik} $$ Assume $w_i>0$ for all $i \in \{1, ..., n\}$. Assume transition probabilities satisfy: $$ P_{ij} = \frac{w_{ij}}{w_i} \quad \forall i, j \in \{1, ..., n\} $$ Note that we allow self-transitions if we have weights $w_{ii}>0$.

Claim:

The following probabilities $(\pi_i)_{i=1}^n$ satisfy the global balance equations (stationary equations): $$ \pi_i = A w_i \quad, \forall i \in \{1, ..., n\}$$ where $A = \frac{1}{\sum_{j=1}^n w_j}$.

Proof: We can show these probabilities satisfy the detail equations: $$\pi_i P_{ij} = \pi_j P_{ji} \quad \forall i, j \in \{1, ..., n\}$$ and the detail equations imply that the same probabilities satisfy the global balance equations. $\Box$

If the resulting weighted graph is connected then the Markov chain is irreducible and this probability distribution is in fact the unique solution to the global balance equations. For completeness, note that the global balance equations are: $$ \pi_j = \sum_{i=1}^n \pi_i P_{ij} \quad , \forall j \in \{1, ..., n\}$$ and a 2-line calculation shows that the detail equations imply the global balance equations.