AtCoder shananigans

Here is the problem, and below is the raw transcript of my thoughts.

Obs: It is always optimal to use all $K$ moves.

intuitive proof. While we have moves left, each move can be used to improve the permutation. Either we can shorten it if all are in increasing order.

Or we can improve it if we have say 1 4 2 by deleting the 4.

we want to prioritise getting 1 in first position

Suppose $1$ has $p[1]=1$. If we shift, we are worsening our permutation.

So shifts become useless. Once the 1, or the lowest value possible is

positioned at the head, we will only use deletes.

We have some options for _ ... _ 1 _ ... _ to be improved

1. Delete the prefix.

2. Shift $1$ to the head.

3. Delete part of the suffix and then shift $1$ to head.

If we are going to shift, we should delete from the suffix first.

Otherwise we waste moves shifting values that will be deleted.

We can simulate this by shifting first without deleting, then

anything in the suffix before the shift can be deleted for free.

As long as we take this into account, we can ignore $3$ and just do $2$.

Sub-Problem: Given a permutation how to optimally improve it with

only deletes. Just delete whenever there is a decrease so for example:

1 3 2 4 we would first delete the $3$, then the $4$. We can use a stack to push values to while they increase and as soon as we see a decrease, we pop until it goes back to increase.

Programming again

The problem is given here.

Def 1: A zig-zag path is a path starting from $(i,j)$ which moves according to the following rule $(i,j)\rightarrow ((i+1)\mod 2, j)\rightarrow ((i+1)\mod 2, j+1)$. This rule may be repeated as many times as we like.

Claim: Suppose we are at $(1,j)$ after making two consecutive right moves. Then we are forced to move $(1,j+1)\rightarrow ... \rightarrow (1,m)\rightarrow (2,m)\rightarrow ... \rightarrow (2,j-1)$. Call such a path a forced path.

Then the path that we must take will firstly consist of a zig-zag path starting from $(1,1)$ (possibly of length $0$) followed by a forced path (possibly of length $0$). 

Suppose for any cell $(i,j)$ we have pre-computed the time needed to complete the forced path in $f[i,j]$, and the time needed to zig-zag to this cell $z[i,j]$ from $(1,1)$. We define $t[i,j]$ to be the minimum time needed to visit each cell exactly once given that we have zig-zaged to $(i,j)$. Then

$$t[i,j]=z[i,j]+\min(t[(i+1) \mod 2, j+1], f[i,j+1])$$

The problem now reduces to computing $z[i,j]$ and $f[i,j]$ efficiently, i.e. in $O(m)$. The problem of computing $z[i,j]$ can be done in $O(m)$ by directly simulating the unique zig-zag path.

We now focus on the only remaining task of computing $f[i,j]$, i.e. the time to complete the forced path starting at $(i,j)$. This is where I got stuck in the contest. I am not sure how to efficiently compute $f[i,j]$ by dynamic programming, although I suspect this approach can be made to work. It feels like a hell of a lot of work though, so I am curious to see if there is a more straightforward approach. I strongly believe that most solutions should leverage the claim above.

It turns out that we need to notice that we need at least $k$ time to move through $k$ cells. Any additional time is spent waiting at some cells. Observe that it makes no difference where we wait, i.e. if we wait at a cell for 2 seconds and another for 4 seconds, then we can convert it to a path where we wait 6 seconds at the first cell and move directly through all cells with no waiting. So we compute the minimum waiting time for a path instead. 

For the $k$th cell in a path at $(x,y)$, the minimum waiting time $t$, is $t\geq a_{x,y}-k$. So we can take the maximum of the minimum waiting times over all cells in the forced path as our minimum waiting time for that path. If we know the minimum waiting time for a path from cells $[i,j]$, call it $t_{[i,j]}$, then we can compute the minimum waiting time $t_{[i,j+1]}=\max(t_{[i,j]}, a_{j}-(j+1-i))$. Also $t_{[i-1,j]}=\max(t_{[i,j]}+1, a_{i-1})$. This gives us everything we need to write an $O(m)$ solution.

More programming problems

I kinda failed today's round. But oh well.

Problem A:

This is very simple implementation.

Problem B:

We just keep track of the sum of the differences between increasing columns for all intervals $[0,i]$ in an array $d$. Then we can get the jump damage for any $[i,j]$ interval using $d[j]-d[i]$.

Problem C:

A bracket sequence is regular (RBS) if and only if:

1. number of '(' = number of ')',
2. for every prefix: number of '(' $\geq$ number of ')'.

Idea 1: Iterate from left to right through $s$, whenever we meet a '?' determine if it may be replaced by a '(' and a ')'.

Replacing '?' with '(' can never break condition (2), however to satisfy (1) we need to ensure that we do not replace so that number of '( > number of ')'.

Replacing '?' with ')' requires that the current nesting depth is $>0$. Furthermore, we must not use too many such that we number of '(' < number of ')'. Additionally, we need to ensure that this replacement does not violate (2) which can occur even if the nesting depth is $>0$. For example in '(?)?' the first question mark is at nesting depth $1$, however if we replace it with ')', the sub-segment $[1,3]$ has more ')' than '('. However, I am not sure how to make this work.

In the end I used a hint from the editorial. Apparently problem D was easier than C, I noticed this in contest but was too stubborn to switch.

Reviewing codeforces 808

Problem A:

We observe that for $a_1$ to be turned to $0$, we need $a_1$ to be a multiple of $a_0$. If this is not the case then the answer is no. Else we can make $a_1=a_0$, so we can inductively repeat the argument. Hence we only need to check that $a_i$ is a multiple of $a_0$ for $1\leq i<n$.

Problem B:

We observe that $\gcd(i, a_i)\in\{1,...,i\}$. Then we must have $\gcd(i,a_i)=i$. Suppose not, then $\gcd(i-1,a_{i-1})$ has $i-2$ possible values, $\gcd(i-2, a_{i-2})$ has $i-3$ possible values, ..., $\gcd(1,a_1)$ will have no possible values. This means that $a_i$ must be any multiple of $i$ in the range $[l,r]$, for $1\leq i\leq n$.

Problem C:

We observe that if we can take $x$ tests, then we can take $x-1$ tests. Therefore, we can do a binary search. How can we check if we can take $\geq x$ tests? We iterate through $a$ maintaining the current IQ $k$ and current tests taken $c$. If $k\geq a[i]$, then it definitely won't hurt to take test $i$. If $k<a[i]$, then we should only take the test $i$ if we have $n-i\leq x-curr$, i.e. the number of tests remaining is at most the number of tests needed to hit our minimum target of $x$ tests taken. The intuition is that taking such a test earlier decreases our IQ, so it may prevent us from taking a test we could otherwise have taken.

Problem D:

I did not get very far on this problem. I will update this section later once/if I solve it.

Wrapping my head around network sharding

It is well known that traditional blockchains have all nodes store and verify the entire state, as well as process all transactions. As a result, the transaction throughput is much lower (<15 tx/s) than for transactions on centralised networks (visa ~1500 tx/s). Sharding is a promising concept which aims to improve this transaction rate for blockchains while upholding decentralisation and security.

The basic question is: do we really need all nodes in the network to verify every single transaction? 

Ideally, we want to partition the network into $K$ sets of validator nodes, each able to verify and add transactions securely in parallel, thus increasing the transaction throughput by a factor of $K$.

This is called network sharding, where we form groups of validator nodes in order to process transactions in parallel. However, if the groups are formed naively, it is possible to overpower a shard with fewer resources because the number of validators in a shard are < the total number of validators. To overcome this we can sample the validors in each shard at random, which means that the attacker can not force himself into a single shard so easily. In practice, we can achieve this by randomly shuffle the list of validators and allocating the first set of validators in the shuffled list to shard $1$, the next set to shard $2$ and so on.

To illustrate this, we analyse the scenario of having $N$ validator nodes in total (all of equal weight/power in the consensus mechanism, PoW/PoS/etc...) and $K$ shards of $X=N/K$ validators each. Suppose there are $M$ malicious nodes and that the rest ($N-M$) are honest. Fix a shard $1\leq i\leq K$, we want to know how large $M$ needs to be in order to have $>X/2$ malicious nodes in shard $i$.

We have ${N \choose X}$ validator groups possible for shard $i$, each of which is equally likely and

$$S=\sum_{j=0}^{X/2}{{M \choose j}{N-M \choose X-j}}$$

ways to choose validator groups for shard $i$ with $\leq X/2$ malicious nodes. This means that the probability of having $\leq X/2$ malicious nodes in shard $i$ is $\frac{S}{{N \choose X}}$.

Say $N=100$ and $K=10$ so that $N/K=10$. If we assume that $M=30$, then we have a

$$\frac{\sum_{j=0}^{5}{{30 \choose j}{100-30 \choose 10-j}}}{{100 \choose 10}}=0.96$$

probability of shard $i$ having $\leq 50$ malicious nodes. This makes it almost infeasible to force ones way into a shard. Below is a graph showing the probability of malicious nodes overwhelming a shard as $M$ varies.

The next question is then: how do we allocate transactions to our validator groups/shards?

This question is decided by transaction sharding mechanisms, but I will end this post here.

Codeforces: The third problem

I couldn't take part in the round today because I was playing tennis =) . Anyway problem C had 2500 solves so I thought I would give it a go.

We are given a permutation of the numbers from $0$ to $n-1$ and are asked to find the number of permutations $b$, from $1$ to $n$ such that for every $1\leq l<r\leq n$, MEX$(a_l, ..., a_r)=$MEX$(b_l,...,b_r)$. Here the MEX of a sequence of numbers is the smallest non-negative number not in the sequence.

So we first observe that any sub-array which includes $0$ in $a$ must also include $0$ in $b$. Therefore, the position of $0$ in $b$ is the same as its position in $a$. Similarly, the position of $1$ is the same in both $a$ and $b$ since if it changes some sub-array whose MEX was $1$ will now be $>1$ or some sub-array whose MEX was $>1$ will now be $1$. This lead me to the following observation.

We want to make sure that all sub-arrays with MEX$=0,1,2,...,n-1$ keep their MEX unchanged. For MEX=0, this means the $0$ staying in the same position. For MEX$=1$, the same. Now for MEX$=2$, we observe that these sub-arrays must contain $0$ and $1$. Let pos$[i]$ be the position of $i$ in $a$. Then we have two cases.

Case 1: $\min(\text{pos}[0],\text{pos}[1])<\text{pos}[2]<\max(\text{pos}[0],\text{pos}[1])$.

Then the exact position of $2$, so long as it remains in this range, does not change MEX$=2$ intervals. This is because for a MEX of $2$, we need to include both $0$ and $1$ and so moving the $2$ around will not change the MEX of intervals which do not include either $0$ or $1$ in this case.

Case 2: $\min(\text{pos}[0],\text{pos}[1])>\text{pos}[2]$ or $\text{pos}[2]>\max(\text{pos}[0],\text{pos}[1])$.

Then $2$ cannot be moved at all in $b$.

In general for any $i$, we let $l=\min(\text{pos}[0],...,\text{pos}[i-1])$ and $r=\max(\text{pos}[0],...,\text{pos}[i-1])$. Then for case 1 we need $l<\text{pos}[i]<r$. 

So now we can easily find if an $i$ can be moved, and a rough range of positions it must stay within (namely $(l,r)$) . However, we need to figure out for each $i$, how many positions it can be moved to, i.e. how many elements it can swap with in $a$. Note that this will result in double counting, so we only consider for each $i$, the number of elements $>i$ that it can swap with.

If we have case 2 for some $i$, then the number of elements it can swap with is $0$. If we have case 1, then we have $r-l+1$ elements in the range $[l,r]$ of which $i$ of them are $<i$. The remaining $r-l-1-i$ elements are larger than $i$ and can be swapped with $i$ safely. Therefore, we can multiply our answer by $r-l+1-i$ every time we enter case 1.

This leads to an $O(n)$ solution basically using a two pointers method with $l$ and $r$ to maintain the range. Quite a nice problem! For me the hardest part was figuring out the correct approach to count the number of elements each $i$ can swap with.

Codeforces: Permutation Graph

We are given a permutation of $1,2,...,n$, $a_1, a_2, ..., a_n$. Construct the undirected graph with vertex set $1, 2, ..., n$ and $(i, j)$ an edge iff $\min_{k=i}\{a_k\}=a_i$ and $\max_{k=i}\{a_k\}=a_j$ or the reverse. Find the shortest path from vertex $1$ to $n$. Here $n\leq 2.5\times 10^5$.

The main idea:

Firstly, we observe that a $(1,n)$-path always exists since for any vertices $i$ and $i+1$ we have the edge $(i,i+1)$.

Consider the element with value $1$, say it is at position $i$. Similarly, the element with value $n$ at position, say $j$.

$$a_1, ..., a_i, ..., a_j, ..., a_n$$

We have the edge $(i, j)$. Additionally, there can be no edge $(x,y)$ with $x<i$ and $y>i$ or $x < j$ and $y>j$. Therefore, the shortest path must take the edge $(i,j)$, and we can apply a divide-and-conquer strategy on the sub-arrays $a_1, ..., a_{i-1}$ and $a_{j+1}, ..., a_n$. This can be implemented in linear time.

Happy days + learning cryptography

I'm pretty happy today since I managed to solve 3 problems in codeforces and had the idea for problem D (a binary search based solution) but could not figure out the implementation details in time.

I am trying to learn some cryptography so that I can better understand blockchain technology. I am following Prof. Shafi Goldwasser's (a legend in computer science) lectures to do this. I will use this post to record some notes on the first lecture.

First some important notation is introduced. We define an encryption scheme as a triple $(G,E,D)$ where

• $G(1^k)$ outputs a secret key of length $k$.
• $E(sk, m)$ takes a secret key and a message and outputs ciphertext.
• $D(sk, m')$ takes a secret key and a ciphertext and outputs plaintext.

We also assume a message space $M$ which defines a probability distribution over all possible messages, a key space $K$, and a ciphertext space $C$, which is just a probability distribution which is dependent on $M$ and $K$.

Note that $G$ must be probabilistic in the sense that its output must define a probability distribution. If not our adversary could easily decrypt any ciphertext since there exists only one secret key for each $k$. If we allow $E$ to be probabilistic then we could have many possible ciphertexts for the same message. Similarly, if $D$ is probabilistic, we allow for a ciphertext to have many possible plaintexts. For this to make sense, we demand that w.h.p the decryption is correct.

By correctness, we mean the following: $D(sk, E(sk, m))=m$. Additionally, we need security, i.e. it should be hard for our adversary to decrypt the ciphertext. Usually, this is done by reduction to some "hard" problem.

Shanon secrecy is demanding that $\mathbb{P}[M=m]=\mathbb{P}[M=m \mid C=c]$, where $c=E(sk, m)$. This basically says that the attacker does not learn anything new about the message by looking at the ciphertext.

The notion of perfect indistinguishability is the condition that $\mathbb{P}[C=c \mid M=m]=\mathbb{P}[C=c \mid M=m']$. This says that for any pair of messages, by looking at the ciphertext, we cannot learn/distinguish between which message, $m$ or $m'$, was sent.

It turns out that these two concepts are equivalent. The lecture concludes by giving an example encryption scheme which achieves Shanon secrecy. This scheme is called the one-time pad:

• $G(1^k)$ outputs a random string from $\{0,1\}^k$.
• $E(sk, m)$ outputs $m \oplus sk$.
• $D(sk, m')$ outputs $m' \oplus sk$.

This works because $(m \oplus sk) \oplus sk = m$. Additionally, it can be shown that one-time pads achieve Shanon secrecy, however, a one-time pad can only send one message with the same secret key, if it sends two we no longer have Shanon secrecy.

Some codeforces problem + a little puzzle

We are given some array $a$ of length $n$ which is initially populated with only $0$'s. We also have a pointer which starts pointed at the first element of $a$. Given the pointer is at position $i$, we can make the following moves:

• add $1$ to $a[i]$ and move the pointer one to the right, or
• subtract $1$ to $a[i]$ and move the pointer one to the left.

We are given some target array of length $n$. Can we transform $a$ into the target array such that the pointer also ends at the first element in $a$?

We first note that because the pointer must start and end in the first position of $a$, the target array sum must be $0$. Additionally, if we look at what a move is actually doing on the following example:

$a_1, a_2, a_3, a_4, a_5$

+     +     +     + 

       -     -     -     -

The overlapping + and - just cancel out and so the operation actually has the form +...+_____-

We observe that whenever we have a - we must also have at least one + preceding it by the move's anatomy. Thus the prefix sums must be non-negative. It turns out this condition is also sufficient.

Extra puzzle:

Imagine $n$ glasses upside-down on a table. In one move, we can flip any group of $n-1$ glasses. For which values of $n$ can we turn the glasses up? For these values of $n$ devise an algorithm for doing so in the minimum number of moves.

So first we note that when $n=1$ it is clear that it is impossible. For $n=2$ it is trivially possible. For $n\geq 3$, we need to think a little bit.

In order to flip every glass over, we need to flip each glass an odd number of times. Consider the following procedure.

• number the glasses from $1$ to $n$.
• for every $g=1$ to $n$, flip all glasses except for glass $g$.

Fix any glass $g$, it is flipped $n-1$ times by this procedure. Thus if $n$ is even, all glasses will be turned over. The remaining questions are:

1. What about $n>1$ odd? (Conjecture, it is not possible)
2. Is our algorithm for even $n$ optimal. (Conjecture, yes)

Note that we will never flip the same set of $n-1$ glasses twice. Since the second will undo the effects of the first. Thus if it is possible it is always possible in $\leq n$ moves.

Consider odd $n$. At any given moment there must exist at least one upside-down glass. After $1\leq i<n$ moves suppose WLOG we have excluded $1, 2, ..., i$. Each of these glasses will have been flipped $i-1$ times and all others will have been flipped $i$ times. Thus for all $i<n$ we have glasses which are flipped and unflipped. Thus we need at least $n$ moves and it is impossible for odd $n$.

Line Empire Codeforces

We are given $N$ cities on an integer number line at positions $0<x_1<x_2<...<x_N$, where our capital is initially at position 0. Initially only the capital is conquered. We can make the following moves:

1. Move the capital at $x_i$ to any conquered city at $x_j$ for a price of $a\cdot |x_i-x_j|$,
2. Conquer an unconquered city at position $x_j$ where our capital is at $x_i$ for a price of $b\cdot |x_i-x_j|$ so long as all cities on path between capital and unconquered city are conquered already.

We are looking for the minimum price to conquer all cities. First let's make some observations:

• We are forced to conquer the cities in the order $x_1, x_2, ..., x_N$ because of the condition that all cities on the path from the capital to the unconquered city must be already conquered.
• The first move must be to conquer $x_1$.
• We never want to move the capital left.

Let's play with a scenario.

0 -- X1 -- X2 -- X3 -- X4

Suppose the sequence of moves which minimises the price payed ends with the capital at $X3$. Then, we must pay price $a\cdot X3$ for capital movement. Since the price function is linear, the moments  when we move the capital do not affect the cost payed for capital movement, i.e. if we move the capital from $0$ to $X1$, then to $X3$, this costs the same as moving the capital straight to $X3$ from $0$.

However, since having the capital closer to the right reduces the cost payed for conquering, we always want to move the capital right as soon as we can. Pictorially this is because if we do the conquering first we pay prices as follows

0 -- X1 -- X2 -- X3 -- X4

-------->

-------------->

--------------------->

----------------------------->

********************

Here --> is the conquering cost between the neighboring cities and *** is the capital moving cost. However, if we move the capital as soon as we can, then we have

0 -- X1 -- X2 -- X3 -- X4

------->

******

            ----->

            ******

                     ------>

                     *******

                                ------>

So, as already established the capital moving cost is the same, however, the conquering cost is much less, since we do not repeat the costs as in the first picture. In general, if the capital ends up at $X_i$, the total price payed is therefore 

$$X_i\cdot (a+b) + b\cdot\sum_{j=i+1}^{N}{X_j-X_i}=X_i\cdot (a+b)+b\cdot(S_{N}-S_{i}-(n-i)\cdot X_i)$$

We can precompute prefix sums $S_{i}$ on $X$ in $O(N)$ so that this value is computable in $O(1)$ for any $i$.

We are missing a detail: how do we know where the capital ends up at the end of a sequence of moves which minimises the price? Well we can just try every possible $0\leq i\leq N$ and keep whichever achieves the minimum price.

String equality

Hi, today I will be presenting my thoughts on a recent codeforces problem. In this problem, we are given two strings $s$ and $t$ of length $n$. We want to make $s$ equal $t$ by performing any number of the following moves on $s$:

1. if we see 'ab' we can change it to 'ba',
2. if we see 'bc' we can change it to 'cb'.

We are asked to print YES if $s$ can be made equal to $t$, and NO otherwise. Note that $n\leq 10^5$, so we need $O(n\log{n})$ or better.

Firstly, we note that both moves leave the number of occurrences of each letter in $s$ and $t$ invariant. Thus, we count the number of occurrences of 'a', 'b', and 'c' in $s$ and $t$ and check they are equal.

Obs 1: Move $1$ moves 'b' to the left, and move $2$ moves 'b' to the right.

So moves essentially shift around the 'b' 's.

Obs 2: Let $\text{pos_s}_i$ be the position of the $i$th 'b' from the left of $s$, and let $\text{pos_t}_i$ be the position of the $i$th 'b' from the left of $t$. If $s$ is made equal to $t$, then $\text{pos_s}_i=\text{pos_t}_{i}$ for all $1\leq i\leq \text{cnt}_b$. 

Since $\text{pos_s}_i<\text{pos_s}_{i+1}$, the observation follows.

Once all 'b' 's are correctly positioned (if possible), i.e. $\text{pos_s}_{i}=\text{pos_t}_i$, then we cannot perform any more moves without moving a 'b' to the wrong position. Therefore, it only remains to check that the strings are equal, if so then we return YES, else we return NO.

This can be implemented in $O(n)$.

Kickstart: Ants on a stick

This is a twist of the well known ant problem, whereby we can view ants as walking through each other when they meet. In this case, we do not seek the latest time for an ant to fall off the stick, instead we want the order by which they fall off.

The first thing I noticed was that one of the leftmost or rightmost ants, $l$ and $r$ respectively, will fall off first. This is because they will either walk straight off, or they will walk into some ant and then walk towards the end of the stick. Now we just need to decide which of the two falls off first. 

Since, we can view the ants as walking past each other when meeting, we know that the $n$ ants fall off the stick at times $t(1),t(2),...,t(n)$, where $t(i)$ is the time that the $i$th ant falls off the stick when it is alone on the stick. Then the first ant will fall off at time $\min_{i}\{t(i)\}$. Let $x$ be the ant which has this minimum value of $t(x)$. If $x$ and $l$ are facing each other, then $l$ will fall off first since $x$ and $l$ will meet at some time, forcing $l$ to fall off the stick first. There are other cases to examine, but we have now made the main observations.

Binary string

 The problem link is here: https://codeforces.com/contest/1680/problem/C.

My approach and thoughts:

Let b start with $x$ zeros. We simplify the problem to only have deletions from the left side.

Let $s[i]$ denote the number of $1'$s in positions $[0,i)$. We want to delete prefix $[0,i)$ which minimises $\max\{x-(i-s[i]), s[i]\}$.

Say prefix $[0,i)$ meets these conditions, then we delete it. Let $b'$ be the remaining binary string but reversed, where the prefix array $s$ is recomputed as $s'$. We apply the exact same method to $b'$, taking into account that we have already deleted $s[i]$ $1$'s, so the cost after deletion of prefix $[0,j)$ will be $\max\{x-(i-s[i])-(j-s'[j]), s[i] + s[j]\}$. We can repeat the same process starting from deleting the right side of $b$ and then the left.

However, this fails on input $1000110110001$. In this case it is not the case that greedily deleting the prefix which yields the lowest score is best. This is because we may use our deletions inefficiently if we restrict ourselves first to the prefix and then the suffix. In some cases, it is best to delete a bit from both sides.

So we try a binary search over the set of possible costs $[0,x]$ since if we can achieve a cost of $c$, we can certainly achieve a higher cost. The problem then becomes: how can we efficiently check if a cost of $c$ can be achieved? For a cost of $c$, we need our remaining string to have $\leq c$ zeros in it and for this string to be reached with $\leq c$ deletions of ones. Therefore, we look at the substrings with $i$ ones deleted from the left and $c-i$ deleted from the right for every $0\leq i\leq c$ and check that for at least one of them, the number of zeros is $\leq c$.

If we pre-compute an array $p$, where $p[i]$ is the position of the $i$th one from the left, we can find the substring with $i$ ones deleted from the left and $c-i$ ones from the right between positions $p[i+1]$ and $p[c-i-1]$. Also pre-computing array $z$, where $z[i]$ is the number of zeros in positions $[0,i)$, we can check in $O(1)$ time if the substring $[p[i+1], p[c-i-1]]$ has $\leq c$ zeros by checking $z[p[c-i]]-z[p[i]]\leq c$. Thus we have a $O(n\log{x})$ solution since we need $O(n)$ time for this pre-computation of arrays $p$ and $z$, and then perform $O(\log{x})$ binary search rounds each taking $O(n)$ time.

To recap, the main observations used are that binary search is an option and that by pre-computing relevant information about the ones and zeros, we can determine in $O(n)$ time if $b$ can have cost $\leq c$. Perhaps there is a faster solution although I am unaware of it.

Generalized analysis of distributed random walk algorithm

We previously described a distributed algorithm for constructing random walks of length $l$ in dynamic graphs which runs in time $\tilde{O}(\sqrt{lD})$, where $D$ is the dynamic diameter. The author's Atish Das Sarma, Anisur Rahaman Molla and Gopal Pandurangan prove their algorithm is correct in the $\mathsf{CONGEST}(\log^2{n})$ model. The reason being that w.h.p the per-round congestion through any edge is $O(\log^2{n})$ bits. Therefore, w.h.p there will be no congestion when constructing the random walks meaning that every round all random walks increase their length by one.

Now suppose we generalise the distributed model the algorithm operates in to the $\mathsf{CONGEST}(B)$ model. Can we adapt their algorithm to work correctly at the cost of $\mathsf{polylog}(n)$ overhead?

First we observe that for $B\in \Omega(\log^2{n})$, the algorithm provided will work as is, because if we have $B\in\Omega(\log^2{n})$ bits of bandwidth per edge and we only need $O(\log^2{n})$ bits with high probability, then there will be no congestion.

If we have $B<c\log^2{n}$ for every constant $c$, then w.h.p we have $O(\frac{\log^2{n}}{B})$ additional rounds due to congestion.

proof. Each edge has bandwidth $B$ bits. We have previously established that w.h.p $\log^2{n}$ bits pass through an edge in each round. Thus $\frac{\log^2{n}}{B}$ additional rounds will be needed w.h.p to account for congestion.

Therefore, for their algorithm to work in the $\mathsf{CONGEST}(B)$ model, we just need to run the first phase of the algorithm for $2\lambda\log^2{n}/B$ rounds, where we give each random walk $\log^2{n}/B$ rounds to extend its length by one edge to account for congestion.

Hitting time analysis on smoothed dynamic graphs

The random walk can be a very useful tool in distributed algorithms. This is because it is lightweight, simple and local in the sense that no global information is needed. Additionally, since the process is random, it seems likely that it will intuitively be robust to dynamic changes in the graph. We explore to what extent this is true.

Theorem 1: There exists a dynamic graph $\mathcal{G}=(V, \mathcal{E})$ for which the maximum hitting time is $2^{\Omega(n)}$.

proof idea. We construct a dynamic graph $\mathcal{G}$ which is a star over $n$ vertices. Vertex $n$ remains a leaf and all others move clockwise around the center taking turns being the center vertex. Thus after exiting the center, a vertex will be a leaf for $n-2$ rounds. If we start the random walk from a leaf we have two options, move to center or stay at the same leaf. If we move to the center, the center then becomes a leaf, getting us nowhere. Thus we need to stay at the leaf until it is the vertex's turn to become the center. This means staying at the leaf for $n-2$ rounds, which occurs with probability $1/2^{n-2}$. Then we expect this sequence of moves to occur once every $2^{n-2}$ moves, giving the theorem.

This is quite discouraging since it seems as though random walks are no longer feasible as graph exploration methods in dynamic graphs. However, we can analyse hitting time under $k$-smoothing and see if this improves the hitting time.

We can show that this exponential lower bound on hitting time (and hence cover time) is fragile in the sense that if we add a small number of random edges to our worst-case graph, the resulting graph has polynomial hitting time.

Theorem 2: The maximum hitting time $H(u,v)$ of a random walk on any $k$-smoothed dynamic graph is $O(n^3/k)$.

proof. Suppose the random walk is at vertex $w$. If there is an edge $\{w,v\}$, then with probability at least $1-k/n^2$ it will remain an edge under smoothing. If there is no such edge, then an edge $\{w,v\}$ will be added by smoothing with probability at least $k/n^2$. Then if the edge $\{w,v\}$ is actually in the smoothed graph, we have at least $1/n$ probability of the random walk moving to $v$. Therefore, we have at least $k/n^3$ probability of moving to $v$ at each step. Therefore, we expect to reach $v$ in $O(n^3/k)$ steps.

We can also give a lower bound on the maximum hitting time.

Theorem 3: The maximum hitting time $H(u,v)$ of a random walk on a $k$-smoothed dynamic graph is $\Omega(n^{5/2}(\sqrt{k}\ln{n}))$.

The proof is omitted.

Distributed random walk algorithm

Atish Das Sarma, Anisur Molla, and Gopal Pandurangan give an efficient algorithm for the construction of a distributed random walk from some source node $s$. The purpose being to perform this random walk of sufficient length so that the last node in the random walk is sampled according to the invariant distribution. 

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. 

What is the mixing time of a random walk?

We already know that a random walk is a Markov chain with the vertices as its states, and we know that an ergodic Markov chain converges to its invariant distribution. But we do not know how fast. The mixing time is a measure of how quickly it converges. We now formally define this concept.

Def 1: The variation distance between two distributions $D_1$ and $D_2$ on a countable state space $S$ is given by $$||D_1-D_2|| = \frac{1}{2}\sum_{x\in S}{|D_1(x) - D_2(x)|}$$

The factor of one half ensures that the variation distance remains between $0$ and $1$.

Def 2: Let $\pi$ be the invariant distribution of an ergodic Markov chain with state space $S$. Let $p_{x}^t$ represent the distribution of the state of the chain starting at state $x$ after $t$ steps. We define $$\Delta_x(t) = ||p^t_x-\pi||$$ and $$\Delta(t) = \max_{x\in S}{\Delta_x(t)}$$

So $\Delta_x(t)$ is the variation distance between the invariant distribution and $p^t_x$, and $\Delta(t)$ is the maximum of these. Now we can define the mixing time.

Def 3: Similarly we defined $$\tau_x(\epsilon) = \min\{t: \Delta_x(t)\leq \epsilon \}$$ and $$\tau(\epsilon)=\max_{x\in S}{\tau_x(\epsilon)}$$ where $\tau_x(\epsilon)$ is the first time when the variation distance between $p^t_x$ and the invariant distribution is $\leq \epsilon$ and $\tau(\epsilon)$ is the maximum of these. $\tau(\epsilon)$ is called the mixing time.

We say that a Markov chain is rapidly mixing if $\tau(\epsilon)$ is polynomial in $\log(1/\epsilon)$ and the size of the problem.

Random walks against adaptive dynamic graphs

[cite 1] have studied random walks on dynamic graphs against an oblivious adversary. They find that the hitting time of a random walk is $\Omega(2^n)$. However, [cite 2], apply smoothed analysis to this to show that this lower bound is very fragile in the sense that after $k$-smoothing, the bound is reduced to $\Omega(n^{5/2}/(\sqrt{k}\log{n}))$. However, all this assumes the adversary to be oblivious to the random walks location at each step. One could imagine that in some scenarios, the adversary may have knowledge of the random walks position at each step. This is why we are interested in studying random walks against an adaptive adversary.

Claim 1: The hitting  and cover time of a random walk is unbounded against an adaptive adversary.

proof. We construct a dynamic graph which will forcefully constrain the random walk to two nodes only. Thus the adversary can guarantee that the random walk will not hit the desired vertex.

Suppose the adaptive adversary knows the set 

$$S(r)=\{v\in V\text{ }|\text{ }v\text{ has been visited by the random walk in round} \leq r\}$$

and the node the random walk is at, at the start of the current round $r$, $u_r$. Then it will construct the dynamic graph $\mathcal{G}_{\text{bad}}=(V, \mathcal{E})$ where $V=\{v_1,v_2,...,v_n\}$ and

$$\mathcal{E}(r)=\left(\bigcup_{w\in S(r)\setminus \{u_r, v\}}{\{\{w, u_r\}\}}\right)  \cup \{u_r, v\} \cup \left(\bigcup_{w\in V\setminus S(r)}\{{\{v, w\}\}}\right)$$

where $v \in S(r)\setminus \{u_r\}$. We can prove by induction that the random walk will only explore two nodes in $\mathcal{G}_{\text{bad}}$.

However, this feels quite strict/contrived. Perhaps the hitting/cover time is only unbounded on a small class of adaptive dynamic graphs. However, $k$-smoothing can be used to reduce this to $O(n^3/k)$.

Project Goal

In this blog post I want to make it clear what the project objectives are and give the project an overarching goal.

Goal: To study distributed random walks, their properties and uses, in dynamic graphs.

Namely, we are interested in:

• hitting time of a random walk in a dynamic graph.
• cover time of a random walk in a dynamic graph.
• mixing time of a random walk in a dynamic graph.
• smoothed versions of these.
• computing hitting, cover and mixing times on various dynamic graphs by simulation.
• application of distributed random walks to solve $k$-gossip.
• other applications of distributed random walks.

Perhaps we could look into various algorithms for page rank using random walks.

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.