Random walk – A Point of View.

In a previous post we considered a random walk problem on a graph. For a graph $G$ we start a walk from any vertex $v_1.$ Every time we get to a vertex $v$ , we exit it along an edge incident with $v$ with equal probability. Denote by $L(v_1,v_2)$ the event that the last new vertex is $v_2,$ that is, when we visit $v_2$ all the other vertices of $G$ are already visited and we visit $v_2$ for the first time. We proved that in case $G$ is a cycle with $n$ vertices $P(L(v_1,v_2))=\frac{1}{n-1}$ for any two distinct vertices $v_1,v_2.$ In this blog post we discuss a reverse result of Laszlo Lovasz and Peter Winkler [1] that there are no other non-trivial graphs with the same property. Further, I closely follow the paper [2].

Theorem. (Lovasz-Winkler, 1993, [1]). Let $G$ be a simple connected graph with set vertices $V.$ Denote by $L(u,v), u,v\in V$ the event that a random walk starting at $u$ ends at $v$ as the last new covered vertex. Suppose

$\displaystyle P(L(u,v_1))=P(L(u,v_2))\qquad (1)$

holds for any vertices $u,v_1,v_2\in V$ . Then $G$ is either a cycle or a complete graph.

Suppose the graph $G$ satisfies $(1)$ . It means $P(L(u,v_1))=1/(|V|-1)$ for any $u,v_1\in V, u\neq v_1.$ We should rule out all possibilities except $G$ being a cycle or a complete graph. This filtering is based on two observations. The first one is a trivial, the other is also intuitive.

Observation. 1. The graph $G$ must be $2$ -connected, i.e. removing any vertex of $G$ leaves $G$ still connected.

Indeed, suppose it’s false and removing a vertex $v$ makes $G$ fall apart into two components, say $G_1,G_2.$ Take any vertices $v_1\in G_1, v_2\in G_2.$ Then $P(L(v_1,v))=0$ since it’s impossible to start from $v_1,$ visit all the other vertices of $G$ and end up in $v$ as the last visited new vertex – in order to visit $v_2$ we should pass through $v$ first.

Observation 2. Let $v_1,v_2$ be two vertices of $G$ that are not adjacent. Then there exists a neighboring vertex $u$ of $v_1$ such that

$\displaystyle P(L(u,v_2))\le P(L(v_1,v_2))\qquad (2).$

Moreover, if after deleting $v_1$ and $v_2,$ the resulting graph is still connected, then this inequality can be made strict.

Sketch of a proof. Maybe, at first look it looks complicated, but it’s not. Let’s see what happens if we assume $(2)$ fails for all $u$ adjacent to $v_1,$ that is, $P(L(u,v_2))> P(L(v_1,v_2))$ holds for all $u\in N(v_1)$ where $N(v_1)$ denotes the set of neighbors of $v_1.$ So, we start our random journey from $v_1$ and there is $P(L(v_1,v_2))$ probability that we end up at $v_2$ as the last new vertex.

But, after the first move, we are somewhere in $N(v_1)$ and after that there is a greater probability that we land at $v_2,$ moreover, we are not obliged any more to hit $v_1.$ This is impossible. Hence, either there is $u\in N(v_1)$ for which the inequality $(2)$ is strict, or

$\displaystyle P(L(u,v_2))= P(L(v_1,v_2))\qquad (3)$

for all $u\in N(v_1).$ Suppose now, $G$ remains connected after removing $v_1$ and $v_2.$ It means there is a path that starts from any $u\in N(v_1),$ visits all the other vertices, except $v_1$ and $v_2$ and finally lands at $v_2.$ This path has a certain non-zero probability to happen, which means that being in $N(v_1)$ there is a greater probability to land at $v_2$ than starting from $v_1.$ Of course this is not possible. $\square$

These observations are enough to narrow down the possible graphs that satisfy $(1)$ . Suppose $G$ is a graph like that. It means

1) $G$ is $2$ -connected (removing any vertex leaves the graph still connected).
2) Removing any two non-adjacent vertices of $G$ makes it disconnected.

Now, it boils down to prove that any graph that satisfies 1) and 2) is either a cycle or a complete graph. The proof of this claim is not present in [2] and I don’t know how it was done in the original paper [1] of Lovasz and Winkler, I haven’t seen it. Here is a possible approach.
Let’s take a spanning tree $T$ of $G$ using depth- first-search algorithm starting from a root $v_0.$ This algorithm guarantees $T$ has not cross edges, i.e. all the edges of $G$ that are not edges in $T$ connect comparable vertices in $T.$ If $T$ has more than $1$ leaf then those leaves are not connected (in $G$ ) and removing two of them results in still connected graph. Hence, $T$ contains only one leaf, that is, $T$ is a path starting from $v_0$ and ending at $v_{n-1}.$ Note that $v_0$ and $v_{n-1}$ should be connected (in $G$ ) because otherwise we can remove them both and the graph would be connected. Thus, there exists a cycle $C=v_0v_1\dots v_{n-1}v_0$ that passes through all the vertices of $G.$ If there are no other edges, $G$ is a cycle. Suppose it has a chord that connects $v_i$ and $v_j$

Now, if there exists a pair of red and blue vertex that are not connected (see fig. 2), we can remove them and the graph would be still connected. Thus, any red point is connected to any blue one. Further, if there exist two vertices $v_k,v_{\ell}$ that are not connected we can remove them, again contradicting the condition 2). Hence, $G$ is a complete graph. That is it.

References.
[1] L. Lovasz and P. Winkler (1993), A Note on the Last New Vertex visited by a Random Walk, Journal of Graph Theory 17, 593–596.
[2] Tim Dwyer, Uniform distribution of last new vertex in random walk on a graph determines (almost) the graph.
[3] AoPS thread.
[4] A Random Walk on a Graph. Part 1.

The problem that follows was told to me by a friend, and shocked me at first, because the claim is counter-intuitive! It was about a random walk. A few sentences about what a random walk is. Assume, a tourist travels around a country, which consists of cities, some of them connected with roads. Every time, he arrives at a city $X$ , he chooses the next city between those connected to $X$ (including the city he came from) with equal probability. The journey ends at the moment all cities are visited, that is when all the cities (nodes) are covered.
So, the problem was about a random walk on a circle with $n+1$ nodes $x_0, x_1,x_2,\dots,x_n.$ We start our journey from $x_0$ – see Fig. 1.

We are interested what is the probability that the walk finishes at the node $x_i,$ that is, the last new covered vertex would be $x_i, i=1,2,\dots,n.$ The strange fact is that this probability does not depend on the final vertex. The question that arises is: do there exist other graphs with this property? Laszlo Lovasz and Peter Winkler proved that the only graphs for which this property holds are the cycle and the complete graph. The intent of this blog post is 1) to prove the cycle has the mentioned property, and 2) to sketch the proof of the Lovasz-Winkler result. Perhaps, the second goal will be the topic of my next blog post.
Definition. Let $G(V,E)$ be a graph. We denote by $L(x,y)$ the event that a random walk starting from a vertex $x\in V,$ ends at a vertex $y\in V$ and $y$ is the last new covered vertex visited, that is, when we arrive at $y$ all the other vertices are already visited and we visit $y$ for the first time.
Note that with this definition, the probability of the event $L(x,x)$ is $0$ since starting from $x$ it is already visited at the very beginning.

1. Random Walk on a Circle.

Claim. Let the graph $G$ be a cycle with $n$ vertices $x_1,x_2,\dots,x_n.$ Then $P(L(x_i,x_j))=\frac{1}{n-1},i,j=1,\dots,n,i\neq j.$

I made the following wording of this claim, just for fun, and posted it on AoPS forum (see [2]). In this version the final point $T$ (the dark tower) is fixed, and we prove that all $P(L(x,T)), x\in V$ are equal (to $1/n$ ). By symmetry it is true for any two other distinct vertices $x,y\in V.$

Problem 1. Sauron, the king of Mordor, decided to go on a vacation and locked his Dark Tower with $n$ keys, $n\in\mathbf{N}, n\ge 2$ . He distributed the keys into $n$ houses, one key per house. The houses and the Dark Tower are disposed on a circular road. Frodo wants to break into the Dark Tower, so he must collect all the keys first. He starts his journey from some of the houses. Every time he visits a house, he picks up the key (if it wasn’t already taken) and tosses a fair coin to decide which of the two neighboring places to visit next. If Frodo arrives at the Dark Tower before collecting all the keys, he wouldn’t enter and will be eaten by Grendel, a monster that lurks around the Tower. Prove that the chance of Frodo not being eaten does not depend on which house he starts from.

Proof. We have $n$ points $1,2,\dots,n$ on a circle plus one extra point $T$ (the Tower). We start a random walk, starting from some point $i, 1\le i\le n.$ Let $P_n(i)$ be the probability that when we hit $T$ for the first time, we have already visited all the other points $1,2,\dots,n.$ We prove $P_n(i)=1/n, i=1,2,\dots,n.$ Let’s try to find some relation between $P_n(i).$ Consider first the case when $2\le i\le n-1.$ Starting from $i$ there is equal probability to jump at $i-1$ or at $i+1.$ Despite that $i$ is already visited, in both cases we should revisit it again in order $T$ be the last point hit. Hence,

$\displaystyle P_n(i)=\frac{1}{2}\big( P_n(i-1)+P_n(i+1)\big)\,,\,\forall i, 2\le i\le n-1\qquad(1)$

The more interesting cases are $i=1$ and $i=n.$ They are symmetrical, so it is enough to consider the former one.

There is $1/2$ probability that starting from the node $1$ we jump to $2.$ In this hypothesis, the probability to arrive at $T$ without revisiting $1,$ or revisiting the node $1$ after all the keys are picked up, is exactly $P_{n-1}(1).$ Indeed, we could think of this situation as if the node $1$ is deleted, and we start at the first node to the left of $T,$ that is, from $2.$ Moreover, the probability of revisiting $1$ before we visit $T$ and before we got all the keys is exactly $1-P_{n-1}(1).$ Assume this happens, we are again at $1$ and there are some of keys missing. It means we haven’t visited the $n$ -th house. Then, the probability of visiting $T$ , after all the other nodes are visited, is again $P_n(1),$ since the already visited vertices do not matter, we must revisit them again, because we have to visit the node $n$ . This argument can be written down as follows:

$\displaystyle P_n(1)=\frac{1}{2}\Big(P_{n-1}(1) +\big(1-P_{n-1}(1)\big)P_n(1) \Big)\qquad (2)$

You see, $(2)$ is a recurrent relation that connects $P_n(1)$ with $P_{n-1}(1)$ . Thus, knowing $P_1(1)$ (which is $1$ ) we can calculate all $P_n(1),n=2,3,\dots.$ An easy induction yields $P_n(1)=1/n.$ Hence,

$\displaystyle P_n(1)=P_n(n)=\frac{1}{n}, n=1,2,\dots\qquad (3)$

Now, $(3)$ combined with $(1)$ gives as a system of linear equations with respect to $P_n(i),i=1,2,\dots,n$ which is easily solvable and we obtain $\displaystyle P_n(i)=\frac{1}{n}$ for all $i=1,2,\dots,n$ , which means that the probability of Frodo not being eaten does not depend on the house he starts from. (unfortunately thsi probability is small) $\blacksquare$

There is another approach possible, which is based on the equation $(1)$ but does not use $(2)$ . We do no need to calculate explicitly $P_n(1)$ and $P_n(n)$ . What really matters is they are equal by the mere symmetry. Assume, $P_n(i),i=1,2,\dots,n-1$ are not all equal. Then among $P_n(i),i=2,3,\dots,n-1$ there is one that’s either greater than $P_n(1)=P_n(n)$ or less than it. Suppose, the former holds. Let $P_n(k), 2\le k\le n-1$ be the maximal among $P_n(i),i=2,\dots,n-1$ such that at least one of its neighbors is less that it. But, this contradicts $(1)$ applied to $i=k.$ The other case is similar. One can see this approach in more details in [3].

2. Random Walk on a Graph – Lovasz-Winkler Result.

Theorem (Lovasz-Winkler, 1993, [1]). Let $G$ be a simple connected graph with set vertices $V.$ Denote by $L(u,v), u,v\in V$ the event that a random walk starting at $u$ ends at $v$ as the last new covered vertex. Suppose $P(L(u,v_1))=P(L(u,v_2))$ holds for any vertices $u,v_1,v_2\in V$ . Then $G$ is either a cycle or a complete graph.

I’ll discuss this result in more detail in the next blog post, but the idea is simple. Let $v_1,v_2$ be two vertices of $G$ that are not adjacent. Then there exists a neighboring vertex $u$ of $v_1$ such that $P(L(u,v_2))\le P(L(v_1,v_2)).$ Moreover, if after deleting $v_1$ and $v_2,$ the resulting graph is still connected, then this inequality can be made strict.

To the next part >>

Refferences.
[1] L. Lovasz and P. Winkler (1993), A Note on the Last New Vertex visited by a Random Walk, Journal of Graph Theory 17, 593–596.
[2] AoPS thread.
[3] Aditya Guha Roy’s blog post.
[4] A Random Walk on a Graph. Part 2.