They study this problem in the context of dynamic graphs $\mathcal{G}$ which are:
- connected (otherwise the random walk will never converge to the invariant distribution),
- $d$-regular (ensures invariant distribution remains the same for each $G_t\in \mathcal{G}$, it will remain the uniform distribution),
- non-bipartite (ensures the random walk is aperiodic and therefore converges to the invariant distribution)
Additionally, they analyse the problem in the CONGEST$(\log^2{n})$ communication model. This is done to simplify the analysis of their algorithm. However, we aim to generalise their results to the CONGEST$(\log{n})$ model.
The main idea of their algorithm is to perform many shorter walks of length $\lambda$ (to be specified later) in parallel and later stitch them together to form the walk of the desired length.
More specifically, each node $v$ begins by initiating $d=\deg(v)$ random walks of length $\lambda$ by forwarding $d$ "walker" tokens uniformly at random. Once all $nd$ random walks have completed, we have constructed many short random walks which are not linked, they are independent. In the next phase, we want to stitch them together.
To stitch, we first make the source node $s$ uniformly sample one of the $d$ random walks of length $\lambda$ that it created in the first phase.
We can flood the endpoints of each random walk across the graph in dynamic diameter time. Now each node knows the endpoints of each of its $d$ random walks of length $\lambda$. It uniformly picks one of them, $v$, deletes it from its list and tells $v$ to do the same as it just has. In this way, we construct random walks of length $\lambda, 2\lambda, 3\lambda,...$. This is great! Since we want a random walk of length $\tau$ (dynamic mixing time), we can repeat this process $\tau/\lambda$ times.
This seems like it works, but with a good-old pessimistic mindset, we can always find something that breaks. Imagine that some node $u$ is the endpoint of $>d$ short random walks. Then, we can have a situation where $u$ has depleted its collection of random walk endpoints it constructed in phase 1. It would therefore be helpful for us to say that a node $u$ is unlikely to be visited as a connector more than some fraction of $d$ times, which means that $u$'s endpoint supply will, in all likelihood, not be depleted. We will return to this point later, but for now, we ignore it and assume this problem will be fixed later.
Is the algorithm correct? For correctness, we need to show that the stitched random walk of length $\tau$ is a true random walk. Clearly each short random walk (before stitching) is a true random walk over the graphs $G_1, G_2, ..., G_{\lambda'}$ for some decent upper bound $\lambda'$ on $\lambda$. However, for phase 1 to complete in $\lambda'$ rounds we need to make sure that congestion through each edge is not too bad. We want to show that in any round of phase 1, we have at worst $\log{n}$ congestion with high probability (since we operate in CONGEST$(\log^2{n})$ model).
Fix an arbitrary directed edge $(u,v)$. We let $X_{i}$ be the event that "walker" token $1\leq i\leq d$ is forwarded by $u$ along edge $(u,v)$. Then the expected congestion along directed edge $(u,v)$ is
$$\mathbb{E}\left[\sum_{i=1}^{d}{X_i}\right] = d\cdot 1/d = 1$$
Now considering the other symmetric case $(v,u)$, we can conclude that each edge is expected to have $2$ messages in congestion. Using a Chernoff bound we get that
$$\mathbb{P}\left[\sum_{i=1}^{d}{X_i} \geq 4\log{n}\right] \leq 2^{-4\log{n}} = n^{-4}$$
Hence with high probability there will be no congestion and each short random walk will be able to extend its length by one step each round of the first phase.
Now to argue that the stitched random walk is indeed a random walk, we note that each short random walk is independent from every other since the stitching is done by uniformly sampling a short random walk at each chosen endpoint. Additionally, the stitching rounds do not affect the distribution of the chosen vertex since the stitching does not advance the random walk, i.e. only communications are performed, no random walk steps.
So the algorithm is correct (ignoring the flaw we pointed out above). Next post we will try to patch this hole by claiming that with high probability in a random walk of length $l$, we visit each endpoint of the random walk (stitching vertex) at most $O(d\sqrt{l}/\lambda)$ times.
No comments:
Post a Comment