Random walks on graphs

In order to better understand the random walk based algorithm of [cite 1] for $k$-gossip, I will be exploring the concept of random walks on both static and dynamic graphs.

Section 1: Markov Chains

A Markov chain can be thought of as a directed graph where edge $(u,v)$ has a probability label $P_{uv}$ denoting the probability that we move from node/state $u$ to node/state $v$. We can encode this directed graph in an adjacency matrix $P$. Where $P_{ij}$ is the probability label of the edge $(i,j)$ in the graph.

Equivalently, we can define Markov chains to be a set of random variables $\{X_t\}_{t\geq 0}$, where $X_t$ is the state of the Markov chain at time $t$. Then we can say that $P_{ij}=\mathbb{P}[X_t=j | X_{t-1}=i]$.

The defining characteristic of a Markov chain is that it is "memoryless", i.e. the value of our chain at time $t$ can be entirely dependent on the value of the chain at time $t-1$. So the history of state transitions before time $t-1$ is already captured by $X_{t-1}$. This is formally written as

$$\mathbb{P}[X_t=a_t | X_{t-1}=a_{t-1}, X_{t-2}=a_{t-2}, ..., X_0=a_0] = \mathbb{P}[X_t=a_t | X_{t-1}=a_{t-1}]$$

To get any one step transition probability ($P_{ij}$) we can just read from the matrix $P$, but what about a larger step transition probability? We want to compute $\mathbb{P}[X_t=j | X_0=i]$. We can write this as

$$\mathbb{P}[X_t=j | X_0=i] = \sum_{k}{\mathbb{P}[X_1=k | X_0=i] \cdot \mathbb{P}[X_t=j | X_1=k]} = \sum_{k}{P_{ik}\cdot \mathbb{P}[X_t=j | X_1=k]}$$

Therefore, we can inductively prove that $$\mathbb{P}[X_t=j | X_0=i] = P_{ij}^{t}$$

Now suppose that the probabilities of being in each state at time $t$ are given as a row vector $p(t)$. We can extend our result above to show that 

$$p(t)=p(t-1)\cdot P=p(0)\cdot P^t$$

It is natural to ask if $p(t)$ converges to some invariant/stationary distribution, which indicates that the Markov chain reaches some sort of equilibrium. Indeed we can compute this invariant distribution $\pi$ using the following

$$\pi=\pi P$$

The following theorem gives the necessary conditions for a Markov chain on $n$ states to converge to a unique invariant distribution.

Thm 1: Any finite, strongly connected and aperiodic Markov chain has the following properties:

1. the chain has a unique invariant distribution $\pi=(\pi_0,\pi_1, ..., \pi_n)$
2. for all $i$ and $j$, in the limit $\lim_{t\to\inf}{P^{t}_{j,i}}$ exists and it is independent of $j$
3. $\pi_i=\lim_{t\to\inf}{P^{t}_{j,i}}=1/h_{i,i}$, where $h_{i,j}$ is the expected time for the Markov chain to go from state $i$ to $j$.

We need the Markov chain to be strongly connected because if we have a Markov chain with two strongly connected components, the chain will have two invariant distributions: one for each connected components. A Markov chain is aperiodic if the $\gcd$ of all path lengths to get from one state back to it is equal to $1$, i.e there is no period which dictates when we can be in a state. If the Markov chain is periodic, then it will not converge to $\pi$ because the distribution will flip flop its value based on the periodicity of the chain.

The theorem implies that the probability of being in state $i$ is the limiting probability of being in state $i$ infinitely far in the future and that this is independent of the start state $j$. So running the chain long enough, it says that the start state does not impact the long term behavior of the chain. Intuitively, if we expect to take $h_{i,i}$ steps on average to go from state $i$ to $i$, then we expect to be in state $i$ $1/h_{i,i}$ of the time.

Section 2: Random walks on undirected static graphs

A random walk on an undirected static graph $G$ is a sequence of moves of a particle between the vertices of $G$. If the particle is at vertex $u$, then it has a $1/\text{deg}(u)$ probability of moving to any of its neighbors. We can see that this is a Markov chain where $X_t$ is a random variable denoting the node which the particle is at at time $t$.

Since we want to avoid periodic Markov chains, we want to make sure that our graph we perform the random walk on does not prevent us from reaching a node if the number of time steps to do so is not a multiple of some constant.

Bipartite graphs are therefore no good, since if we are one side of the nodes, we cannot get to any nodes on the same side within an even number of time steps. This means that the random walk will be periodic and thus will not converge to the invariant distribution. This motivates the following theorem.

Thm 1: A random walk on an undirected graph $G$ is aperiodic if and only if $G$ is not bipartite.

proof. The forward direction was proven by the above paragraph, since we concluded that a bipartite graph is periodic. We now need to show that only bipartite graphs cause our random walks to be periodic. Suppose $G$ is not bipartite, then we can have cycles of odd length. Note that every node has a cycle of length $2$ (to a neighbor and back). This means that the Markov chain is aperiodic.

So if we work with a bipartite graph $G$, we know that a random walk on $G$ will converge to the invariant distribution. What is this invariant distribution? Well by looking at $\pi=\pi P$ and utilising the fact that $P_{ij}=1/\text{deg}(i)$, we get that $\pi_i=\text{deg}(i)/2m$. Intuitively, this makes sense, since the more edges a node has connected to it, the more ways the random walk can end up at the node.

(As an aside, this gave me the idea of studying the mixing time of random walks against an adaptive adversary. The adversary will make the graph bipartite in each round because this means the random walk will be periodic and so will not converge to the invariant distribution. But if we introduce smoothing, we can probably make it non-bipartite with high probability.)

We now introduce some interesting values of random walks which we want to study.

The hitting time, $h_{u,v}$ was introduced previously in terms of Markov chains. In the context of random walks, it is the expected time for the random walk to go from node $u$ to node $v$. The commute time is given by $h_{u,v} + h_{v,u}$.

The cover time is maximum over all starting vertices of the expected time for the random walk to visit all vertices.

Lemma 1: If $(u,v)\in E$ then $h_{u,v}+h_{v,u}\leq 2m$

We can justify this intuitively using the fact that if we have stationary distribution $\pi_i=\deg(i)/2m$, then this means for this fraction of the time we expect to be in state $i$. Therefore, on average the time between being in $u$ is $2m/\deg(i)$.

Lemma 2: The cover time is $\leq 2mn$

Since our graph is connected, there must exist a spanning tree $T$. We can cover every vertex by visiting the nodes in order of depth first search along $T$. Suppose this yields the cycle $u, w_1, w_2, ..., w_r, u$ of length $2(n-1)$. Then we have

$$\mathbb{E}[\text{steps to visit all vertices}]\leq \mathbb{E}[\text{steps }u\to w_1 \text{ and steps }w_1\to w_2\text{ and ... and steps }w_r\to u]$$

which by linearity of expectation and lemma $1$ is $\leq 2mn$.

We are now interested in another property of Markov chains, the mixing time. This tells us how quickly a Markov chain converges to the invariant distribution which is useful when sampling nodes in a graph for example. We will cover this in the next post.

$k$-gossip with smoothing

We have so far analysed gossip on connected dynamic graphs, however, we have not yet looked at this problem under smoothing. We use the analysis conducted by [cite1] and [cite2] as a blackbox to derive a $s$-smoothed upper bound for $k$-gossip.

Here we assume that each node in our dynamic graph is given as part of the input $n$ and $k$, we also assume there is some agreed upon ordering of the tokens. This leads to a very simple $O(nk)$ algorithm without smoothing.

Algorithm for each node:

• $i=1$
• For $i$ from $1$ to $k$ do
• For $n-1$ rounds broadcast the $i^{\text{th}}$ smallest token the node knows.

This works because of the connectivity of the dynamic graph ensuring that each round a node must learn a token. Because this protocol breaks up $k$-gossip into $k$ phases of flooding a single token, we can use results from smoothed flooding for $k$-gossip.

We know that flooding a token on a connected dynamic graph under $s$-smoothing against an oblivious adversary terminates within $O(n^{2/3}\log{n}/s^{1/3})$ with probability $1-\frac{1}{n}$. So instead of iterating $n-1$ times we can iterate $O(n^{2/3}\log{n}/s^{1/3})$ times.

Letting $F_i$ be the event that in phase $i$, flooding does not terminate in $O(n^{2/3}\log{n}/s^{1/3})$ round. Then $\mathbb{P}[F_i]=\frac{1}{n}$. The probability that any $F_i$ occurs for $1\leq i \leq k$ is then union bounded

$$\mathbb{P}[\bigcup_{i=1}^{k}{F_i}]\leq \sum_{i=1}^{k}{F_i}=\frac{k}{n}$$

Therefore, the probability that none of the phases fail is at least $1-\frac{k}{n}$. This is not with high probability since $k\leq n$. Thus we need to increase the upper bound for flooding so that the probability of success is at least $1-\frac{1}{n^2}$.

In flooding, we needed an edge between two sets, each of size $\geq r$, where $r$ is the number of rounds in one of the algorithm's phases. This happens with probability at least $c_1sr^2/n^2$ for constant $c_1$ and under $s$-smoothing. Over $r$ rounds, the probability of this not happening in any of the rounds is at most $(1-c_1sr^2/n^2)^r$. We can use the Chernoff bound for random Bernoulli variables to get the following upper bound $(1-c_1sr^2/n^2)^r \leq e^{-c_1r^3s/n^2}$.

We are union bounding twice: once over the $n$ vertices and once over the $k\leq n$ tokens. Therefore, we need flooding to fail with probability at most $1/n^3$. Therefore we need to pick a value for $r$ s.t.

$$e^{-c_1r^3s/n^2}\leq 1/n^3$$

solving this for $r$ yields that

$$r\geq n^{2/3}(3\ln{n})^{1/3}/(c_1s)^{1/3}$$

Result Oblivious: $k$-gossip terminates within $O(kn^{2/3}(\log{n}/s)^{1/3})$ rounds with probability at least $1-1/n$ against an oblivious adversary under $s$-smoothing.

We can extend this result to the case of an adaptive adversary. Here flooding requires $O(n\sqrt{\log{n}/s})$ rounds to terminate. In a previous blog post, I went over the reason why the probability of a helpful edge being added is at least $c_1sr/n^2$, which is required to occur at some point within $r$ rounds for an arbitrary node $v$ to receive the flooded message. Thus the probability that flooding fails is at most $(1-c_1sr/n^2)^{r}$. Using a Chernoff bound we can deduce that

$$(1-c_1sr/n^2)^{r}\leq e^{-c_1r^2s/n^2}$$

We want $e^{-c_1r^2s/n^2} \leq 1/n^3$ and so solving for $r$ we get

$$r\geq n\sqrt{3\ln{n}/c_1s}$$

Result Adaptive: $k$-gossip terminates within $O(kn\sqrt{\log{n}/s})$ rounds with probability at least $1-1/n$ against an oblivious adversary under $s$-smoothing.

Note that the adaptive result improves the $O(nk)$ upper bound, when $\sqrt{\log{n}/s}\leq 1$, which happens when $n\leq e^s$

Flooding requires $\Omega(n\log{k}/k)$ rounds in a $k$-smoothed adversarial dynamic graph

We have presented the $O(n\sqrt{\log{n}/k})$ upper bound for flooding to complete in a previous blog post. We now complete the adversarial $k$-smoothed analysis of flooding by presenting the corresponding lower bound for flooding against an adaptive adversary which was given by [cite].

We adapt the spooling graph used by the oblivious adversary, to construct the adaptive spooling graph. The idea is the same as in the oblivious case: all informed nodes will be in the left star, and all uniformed in the right star. Since the adversary is adaptive, he can keep this property even with smoothing.

Def 1: We define the dynamic adversarial spooling graph $\mathcal{G}=(V,\mathcal{E})$ as follows.

For every round $r$, let the set of informed nodes be $I_r$, and $v_r$ the minimum uninformed vertex. Then $G_r=(V,\mathcal{E}(r))$ where

$$\mathcal{E}(r)=(I_r\setminus \{1\}) \times \{1\} \cup (\overline{I_r}\setminus v_r) \times \{v_r\} \cup \{\{1,v_r\}\}$$

We want to use this adaptive version of the spooling graph to argue that flooding must use some number of rounds $R$ to complete with probability at least $1/2$. Our strategy will be to bound the expected number of newly informed nodes per round and then use Markov's inequality to finish the proof.

Goal: To upper bound the value of $\mathbb{E}[I_r]$.

We know that at least one node, namely, $v_r$ will learn the flooded message in round $r$. However, the smoothed edges between informed nodes in the left star and uninformed nodes in the right star will cause more nodes to become informed.

We introduce the indicator variable $X_{u,r}$ where:

• $X_{u,r}=1$ if there is an edge between $u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}$ and a vertex in the right star.
• $X_{u,r}=0$ if there is no edge between $u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}$ and a vertex in the right star.

Then we have $\mathbb{E}[I_r] \leq |I_{r-1}| + \mathbb{E}[\sum_{u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}}{X_{u,r}}]+1$ since we may have two distinct edges between the left and right spools pointing to the same node in the right spool. By linearity of expectation 

$$\mathbb{E}[I_r] \leq  |I_{r-1}|+\sum_{u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}}{\mathbb{E}[X_{u,r}]}+1$$

$$\leq |I_{r-1}| + c_2k(|\overline{I_{r-1}}|-1)|I_{r-1}|/n^2+1$$

$$\leq |I_{r-1}|\cdot(1+c_2k/n) + 1$$

We achieve the last inequality using the fact that $|I_{r-1}|\leq n$. (Don't understand this next part), but using the linearity of this term, we can write

$$\mathbb{E}[I_{r}]\leq \mathbb{E}[I_{r-1}]\cdot(1+c_2k/n) + 1$$

Now we have a recurrence which we want to upper bound. We let $\mathbb{E}[I_{r}]=A_{r}$ to abstract away from the exact meaning of the recurrence. So we have

$$A_{r+1}\leq A_{r}\cdot(1+c_2k/n) +1$$

Observe that $A_{r+1}\geq A_{r}+1$ because of connectivity of our dynamic graph. We split the analysis of $A_r$ into two cases.

Case 1: $A_r\leq n/c_2k$. Then $A_r\leq 1$ which means the additive term dominates the $A_{r}c_2k/n$ multiplicative term. Hence we have $A_{r}+1\leq A_{r+1}\leq A_{r} + 2$. Because $A_1=1$, we have $\Theta(n/k)$ iterations where stage $1$ applies.

Case 2: $A_r\geq n/c_2k$. Then $A_{r}c_2k/n \geq 1$, so the multiplicative term is larger than the additive term. Therefore we have $A_{r+1}\leq A_r(1+2c_2k/n)$ for $r\geq r_0$. Hence we can write

$$A_{r_0+r_1}\leq A_{r_0}(1+2c_2k/n)^{r_1}$$

where  $r_0$ is the maximum $r$ such that $A_{r_0}\leq n/c_2k$. Using $A_{r_0}=\Theta(n/k)$ we have

$$A_{r_0+r_1}\leq \Theta(n/k)(1+2c_2k/n)^{r_1}$$

Letting $r_1=\alpha n\log{k}/k$, where $\alpha$ is small enough, we have a round $A_{r_0+r_1}\leq n/10$.

Then there exists a round, namely $r_0+r_1$, where the expectation is bounded by $n/10$, which means that flooding has not completed at this round in expectation. Now using Markov's inequality we get

$$\mathbb{P}[|I_{r_0+r_1}|\geq n] \leq \frac{\mathbb{E}[I_{r_0+r_1}]}{n}\leq 1/10$$

Hence $\mathbb{P}[|I_{r_0+r_1}|< n] \geq 9/10$, which implies a $k$-smoothed lower bound of $\Omega(n\log{k}/k)$ for flooding.

Theorem: Fix $0 < k \leq n/16$, not necessarily an integer. For any $k$-smoothed adaptive dynamic graph, for the flooding process to succeed with probability at least $1/2$ it must run for $\Omega(\min\{n, n\log{k}/k\})$ rounds.

Flooding in $O(n\sqrt{\log{n}/k})$ on a $k$-smoothed adaptive dynamic graph

We have previously shown an $O(n^{2/3}\log{n}/k^{1/3})$ upper bound for flooding on $k$-smoothed connected dynamic graphs. However, our adversary was constrained to select the dynamic graph sequence $G_1,G_2,...$ without knowing the outcomes of $k$-smoothing. In this post we present [MPS20]'s work which extends this analysis to an adaptive adversary, i.e. one who can construct $G_r$ based on the previous outcomes of $k$-smoothing on $G_1,...,G_{r-1}$.

The intuitive idea is similar to what we have seen before:

• In the first $r$ rounds of flooding we are guaranteed to have $r$ nodes learn the flooded message.
• We then show that it is likely for some node in a support sequence to receive the message in the next $r$ rounds.
• If a node in the support sequence has the flooded message, then it is likely that our target node $u$ will receive the message within the next $r$ rounds.

However, since our adversary is adaptive we don't have the last bullet point because the adversary can see which nodes have the flooded message and can make it hard for $u$ to receive the message. The adaptive adversary can't do anything about the first two bullet points though since these are a consequence of the connectivity of $\mathcal{G}$ only.

To solve the issue of the last bullet point no longer being a valid strategy, we ask how likely it is for a smoothed edge to appear in between the set of $r$ nodes who know the message after the first $r$ rounds and $u$, since the adversary can't control this.

So consider the set $I$ of informed nodes from the first $r$ rounds of flooding. We know that $|I|=r$ by the connectivity of $\mathcal{G}$. Before we looked at the potential edge set $I\times S_l$ for a support sequence set $S_l$, but now we look at the potential edge set $I\times \{u\}$ where $u$ is our target node.

The probability that at least one edge from $I\times \{u\}$ is in the smoothed version of $\mathcal{G}$ is at least $c_1k|I\times \{u\}|/n^2 = c_1kr/n^2$. Therefore, the probability of no edge from $I\times \{u\}$ being in the smoothed version of $\mathcal{G}$ across $r$ rounds is at most $(1-c_1kr/n^2)\leq e^{-c_1r^2k/(n^2)}$ which is upper bounded by $1/n^2$ for $r=2n\sqrt{\log{n}/(c_1k)}$.

Thus the probability that $u$ does not receive the flooded message after $2n\sqrt{\log{n}/(c_1k)}$ rounds is at most $1/n^2$, which implies that $u$ will receive the flooded message with high probability. A union bound over all vertices in $\mathcal{G}$ gives us that flooding will complete in $O(n\cdot\sqrt{\log{n}/k})$ rounds with high probability.

Theorem: Given a dynamic graph $\mathcal{G}=(V,\mathcal{E})$ constructed by an adaptive adversary, some $1\leq k \leq n/16$, flooding completes in $O(n\sqrt{\log{n}/k})$ rounds with high probability on the $k$-smoothed version of $\mathcal{G}$.

[MPS20] Uri Meir, Ami Paz, and Gregory Schwartzman. “Models of Smooth-

ing in Dynamic Networks”. In: CoRR abs/2009.13006 (2020).

arXiv: 2009.13006. url: https://arxiv.org/abs/2009.13006.

$O(n^{2/3}\log{n}/k^{1/3})$ $k$-smoothed algorithm for flooding.

[Din+15] present an algorithm which runs in $O(n^{2/3}\log{n}/k^{1/3})$ rounds with high probability on a $k$-smoothed dynamic graph.

At the core of their argument is the concept of a support sequence, i.e. a temporally connected subgraph across some number of rounds. The motivation being that if any node in the support sequence receives the flooded message, then it is likely to later be propagated to the target node in the support sequence. In essence a support sequence is just a "fat" target the flooded message needs to hit for $u$ to get the message within some bounded number of rounds dependent on the size of the support sequence. We use this to show that each node receives the flooded message with high probability.

Def 1: Fix integers $t$ and $l$ s.t. $1\leq l < t$, a dynamic graph $\mathcal{G}=(V, \mathcal{E})$, and a target node $u\in V$. A $(t,l)$-support sequence for $u$ in $\mathcal{G}$ is a sequence $S_0,S_1,...,S_l$ such that

• $S_0=\{u\}$,
• for every $i\in [0,l]$ we have $S_i \subseteq V$,
• for every $i\in [1,l]$ we have $S_{i-1}\subset S_i$ and $S_i\setminus S_{i-1}=\{v\}$ for some $v\in V$ such that $v$ is adjacent to at least one node of $S_{i-1}$ in $G_{t-i}$.

Since we are interested in connected dynamic graphs, it seems reasonable that any such dynamic graph has a $(t,l)$-support sequence.

Lemma 1: Given a connected dynamic graph $\mathcal{G}=(V,\mathcal{E})$, some node $u\in V$ and rounds $t$ and $l$ such that $1\leq l < t$, there exists a $(t,l)$-support sequence for $u$ in $\mathcal{G}$.

proof. We can construct such a support sequence inductively as follows. Let $S_0=\{u\}$. Now suppose we have validly constructed $S_0,...,S_i$. We define $S_{i+1}=S_i \cup \{v\}$, where $\{x,v\}\in \mathcal{E}(t-i)$ and $v\in V\setminus S_i$ and $x\in S_i$. Since $\mathcal{G}$ is connected, such a node $v$ must exist, otherwise $S_i$ would be disconnected from the rest of the graph.

Suppose we have a connected dynamic graph $\mathcal{G}$, from lemma 1, there exists a $(t,l)$-support sequence $S_0,...,S_l$ for a target node $u$ in $\mathcal{G}$. If some $v\in S_l$ receives the flooded message in round $t-l$, then we are certain that $u$ will receive the flooded message no later than round $t$. However, since $\mathcal{G}$ will be smoothed, it is possible for our support sequence to get "messed up". We want to show that this is unlikely. Take the following example support sequence.

Here we let $v_i=S_i\setminus S_{i-1}$ and let $v_0=u$. An edge between nodes $v_i$ and $v_j$ for $j<i$ indicates that $\{v_i, v_j\}\in\mathcal{E}(t-i)$. Suppose $v_7$ begins with the flooded message. Node $u$ will receive the message if a $\{v_7,u\}$-journey exists after $k$-smoothing. What is the probability of this in general? We will use a handy lemma that we showed in a previous blog post.

Handy Dandy Lemma: There exists constant $c_2 > 0$ such that the following holds. Consider any graph $G = (V, E)\in\text{allowed}(\mathcal{G}_{\text{conn}})$. Consider also any nonempty set $S \subseteq E$ of edges in the graph and smoothing value $k \leq n/16$. Then with probability at most $c_2k|S| /n^2$, the $k$-smoothed graph of $G$ removes an edge from $S$.

So let's say that $v_i$ has the message, and that $N(v_i)=\{v_j\text{ }|\text{ }\{v_i,v_j\}\in\mathcal{E}(t-i)\text{ and }j<i\}$ is the neighborhood of $v_i$ in $G_{t-i}$. For the message not to proceed in the support sequence, then all $|N(v_i)|$ edges need to be removed by smoothing. Using the handy dandy lemma we know that the probability that $v_i$ can't pass its message on to any $N(v_i)$ is at most $(c_2k/n^2)^{|N(v_i)|}\leq c_2k/n^2$. We can then take a union bound over the up to $l$ rounds needed for the message to reach the target node $u$. This gives us a probability of at most $c_2kl/n^2$ for $u$ not receiving the flooded message.

If we choose $l=n^{2/3}/k^{1/3}$, we get $c_2 k^{2/3}/n^{4/3}\leq 1/4$, which holds for sufficiently large $n$ and $k\leq n$. Thus the probability that $u$ receives the flooded message is at least $3/4$. This gives us the following lemma.

Lemma 2: Fix a connected dynamic graph $\mathcal{G}=(V,\mathcal{E})$ and any $(t,l)$-support sequence $S_0,...,S_l$ where $S_0=\{u\}$. If any $v\in S_l$ receives the flooded message by round $t-l$, then $u$ receives the flooded message with probability at least $3/4$. 

Lemma 2 assumes that a node in the support sequence set $S_l$ already has the flooded message by round $t-l$. However, we don't know that this is the case so let's bound the probability of that happening.

We know that in round $l=n^{2/3}/k^{1/3}$ at least $l$ nodes know the message because of the connectivity of $\mathcal{G}$. Thus we have $l|S_l|$ possible edges between nodes that know the message and nodes in $S_l$. The probability that any of these edges are present in a round $r\geq l$ is at least $c_1kl|S_l|/n^2$. If any of these edges are present from rounds $l$ to $t-l$, then $S_l$ receives the flooded message by round $t-l$. Thus we have a probability of at most $(1-c_1kl|S_l|/n^2)^{t-2l}$ that none of these edges are present in all rounds from $l$ to $l-t$.

Choosing $t=\alpha n^{2/3}/k^{1/3}$ for $\alpha \geq 3$, we have probability at most 

$$(1-c_1k^{1/3}|S_l|/n^{2/3})^{(\alpha-2)n^{2/3}k^{1/3}}\leq e^{-c_1(\alpha-2)}$$

which for a suitable choice of the constant $\alpha$ is at most $1/4$.

So if either the flooded message does not reach $S_l$ by round $t-l$ or the message does not reach its target in the support structure, $u$, then $u$ will not receive the message. So $u$ does not receive the message with probability at most $1/4 + 1/4 = 1/2$. This gives us the following key result.

Lemma 3: Fix a connected dynamic graph $\mathcal{G}=(V,\mathcal{E})$, any node $u\in V$, and a consecutive interval of $\alpha n^{2/3}/k^{1/3}$ rounds, where $\alpha\geq 3$ is a constant. For $k\leq n/16$, node $u$ receives the flooded message in the $k$-smoothed graph of $\mathcal{G}$ with probability at least $1/2$.

Now that we know each node has a constant probability of receiving the flooded message after $\alpha n^{2/3}/k^{1/3}$ rounds, we can give a high probability guarantee that every node receives the flooded message over a larger round interval.

If we repeat lemma 3 $\Theta(\log{n})$ times, we get that node $u$ does not receive the flooded message with probability at most $2^{-\log{n}}$, and thus it will receive the message with probability at least $1-\frac{1}{2^{\log{n}}}$, i.e. with high probability since $2^{\log{n}}=O(n)$. 

Theorem 1: For any connected dynamic graph $\mathcal{G}$ and smoothing value $k\leq n/16$, flooding completes in $O(n^{2/3}\log{n}/k^{1/3})$ rounds on the $k$-smoothed version of $\mathcal{G}$ with high probability.

[Din+15]    Michael Dinitz et al. “Smoothed Analysis of Dynamic Networks”.

In: Proceedings of the 29th International Symposium on Distributed

Computing - Volume 9363. DISC 2015. Tokyo, Japan: Springer-

Verlag, 2015, pp. 513–527. isbn: 9783662486528. doi: 10.1007/

978- 3- 662- 48653- 5_34. url: https://doi.org/10.1007/978-3-662-48653-5_34.

Self-reducibility

When studying the complexity of problems, we often focus on decision problems. For example, NP-complete problems must be decision problems since they must be in NP. What about problems which aren't answered by a simple yes or no? What about finding the minimum vertex cover, or finding an actual $3$-coloring?

Well it turns out that most of the time, if we have an oracle TM with access to the decider for $X$, we can solve the search/optimisation version of $X$. This means that the search version of $X$ cook reduces to the decision version of $X$.

We take the search problem of finding a $3$-coloring of a graph $G=(V,E)$ as an example. Suppose we have access to an oracle which decides if its input graph has a valid $3$-coloring. We want to use this oracle to actually construct a $3$-coloring on $G$ in polynomial time.

First, we should check if $G$ has a valid $3$-coloring to begin with. If it does not then we halt. Otherwise, we can start building the $3$-coloring.

Let's impose an ordering on the vertices, $v_1<v_2<...<v_n$. We will color these vertices one by one starting from $v_1$. Suppose we have colored all vertices $v_1,...,v_{i-1}$ in a way that can be extended to the entire graph $G$. Let $C_i$ be the set of valid colors for $v_i$, for each $c\in C_i$ we assign $c$ to $v_i$. Now we need a way to test if our new coloring can be extended to the entire graph $G$. 

Since our oracle takes as input a graph and that is all, we can't just call the oracle on our graph since it will just ignore the colors we have assigned to it. We need a way to encode the choices of colors into a new graph $G'$ which is $3$-colorable iff the partial coloring can be extended to the entire graph $G$.

We propose the following construction for $G'$: merge all vertices with the same color into one super-vertex whose neighborhood is the union of the neighborhoods of all the vertices being merged. Uncolored vertices are left as in $G$.

Claim: The partial coloring over $v_1,...,v_i$ is extendable to the entire graph $G$ iff $G'$ is $3$-colorable.

proof. Suppose $v_1,...,v_i$ is extendable to the entire graph $G$. Then uncolored vertices in $G$ have a valid assignment of colors. If we construct $G'$, then all uncolored vertices are still adjacent to the same set of colors, so the coloring is still valid, hence $G'$ is $3$-colorable. Suppose $G'$ is $3$-colorable. Then if we undo our construction, we can still color the uncolored vertices since they will be adjacent to the same colors as in $G'$.

Thus we can simply construct $G'$ and call the oracle on it. If the oracle returns yes, then we fix $c$ as the color assigned to $v_i$. Otherwise we move to the next valid color in $C_i$ and do the same. Note that for some color in $c\in C_i$, the assignment of $c$ to $v_i$ must be a valid assignment for a $3$-coloring over the entire graph $G$, since we know that the coloring over $v_1,...,v_{i-1}$ is extendable to the entire graph $G$ and we know that $G$ is $3$-colorable to begin with.

This informal walkthrough demonstrates an example of self-reducibility. In this case we call the oracle $O(n)$ times and the construction of $G'$ can be done in polynomial time. Pretty neat!

A huge sum

Problem E in the latest atCoder beginner round was quite interesting. The problem statement is quite simple, we are asked to compute

$$\sum_{i=1}^{N}{\lfloor \frac{N}{i} \rfloor}$$

for $1\leq N \leq 10^{12}$.

This problem would be easy if $N$ wasn't so huge. But since it is, we need a faster way to compute the sum than just doing it directly.

The first thing to notice is that all $\lfloor \frac{N}{2}\rfloor < i \leq N$ have $\lfloor \frac{N}{i}\rfloor =1$. More generally, $\lfloor \frac{N}{k+1}\rfloor < i \leq \lfloor \frac{N}{k}\rfloor$ have $\lfloor\frac{N}{i}\rfloor = k$. So our strategy becomes to group equal values together.

If we do this for say $X$ groups we will have 

$$N-((N-\lfloor \frac{N}{2}\rfloor)+(\lfloor \frac{N}{2}\rfloor - \lfloor \frac{N}{3}\rfloor) + ... + (\lfloor \frac{N}{X}\rfloor - \lfloor \frac{N}{X+1}\rfloor))=\lfloor \frac{N}{X+1}\rfloor$$

values of $i$ for which we have still not computed the value of $\lfloor \frac{N}{i}\rfloor$ for. If we choose $X=\lfloor\sqrt{N}\rfloor$, then we have $O(\sqrt{N})$ groups and $\lfloor \frac{N}{\sqrt{N}+1}\rfloor = O(\sqrt{N})$ indices $i$ for which we can directly compute their contribution.

Thus we compute the sum using the following.

$$\sum_{k=1}^{\lfloor\sqrt{N}\rfloor}{k\cdot\left(\lfloor \frac{N}{k}\rfloor - \lfloor \frac{N}{k+1}\rfloor\right)} + \sum_{i=1}^{\lfloor \frac{N}{\sqrt{N}+1}\rfloor}{\lfloor \frac{N}{i}\rfloor}$$

This is done in $O(\sqrt{N})$ which is fast enough for the given constraints.