Markov Chain Robustness

There appear to be three reasonable choices for the power of an adversary choosing $P_t$.²²2Note that we give the adversary more power by allowing $P_t$ to depend on $t$; otherwise we could get three more choices for the adversary’s power.

1. 1.

   Oblivious: $P_t$ is chosen independently of $\{X_s\}$;

2. 2.

   Markovian: $P_t$ may depend on $X_t$ but not $X_s$ for ;

3. 3.

   Non-Markovian: $P_t$ may depend on $X_s$ for all $s\le t$.

Note that an oblivious adversary corresponds to a non-homogeneous (or time-dependent) Markov chain. Oblivious and Markovian adversaries are equivalent if $𝒫$ is closed under “row replacement”: replacing a row in any $P\in 𝒫$ by the corresponding row in another $P^{\prime }\in 𝒫$. The equivalence follows because the adversary can choose the $i$th row assuming the Markov chain is in state $i$. The Markovian and non-Markovian adversaries are equivalent if an adversary is trying to affect the hitting time, but not equivalent for cover time. Hartfiel, [4], and recent work on dynamic graphs implicitly use an oblivious adversary (and don’t discuss the others).

We focus on the most powerful, non-Markovian adversary, although we make some observations about the other adversaries.

Can we understand a Markov set chains (MSC) in terms of a related Markov chain? Although reversibility is not required for all of our theorems, we usually assume the related chain is reversible, i.e., a random walk on an undirected graph. We further assume the graph is connected; otherwise we could restrict attention to the appropriate connected component. The most important probability distribution related to a Markov chain is the stationary distribution $\pi$. The most important quantities of interest in Markov chains are the mixing time $t_{\mathrm{mix}}$, the time it takes to approach $\pi$; the max hitting time $t_{\mathrm{hit}}$, the maximum expected time to go from one vertex to another; and the cover time $t_{\mathrm{cov}}$, the expected time to visit all nodes from a worst-case starting node.

First, we discuss the stationary distribution. Suppose all chains in an MSC have the same stationary distribution $\pi$. Will this MSC converge to $\pi$? It depends on the adversary. For an oblivious adversary, the MSC will converge to $\pi$ – the usual proof works. For a Markovian adversary, the MSC need not converge, even if all underlying chains are reversible; see Section 3.1.

There are two natural special cases of MSCs that we consider. First, an interval chain is an interval of matrices $𝒫=[P^{-},P^{+}]\cap {ℳ}_n$, where $[P^{-},P^{+}]$ denotes the set of matrices $P$ such that for all states $i,j$, we have $P^{-}(i,j)\le P(i,j)\le P^{+}(i,j)$. For interval chains, oblivious and Markovian adversaries are equivalent, since $𝒫$ is closed under row replacement.

For our standard adversary, we consider interval chains of the following form. For $P$ a Markov chain³³3We identify a Markov chain with its transition matrix. and $\epsilon >0$, we consider the interval chain $[P^{-}=(1-\epsilon )P,P^{+}=(1+\epsilon )P]$. When convenient, we consider the essentially equivalent interval chain $[P^{-}=e^{-\epsilon }P,P^{+}=e^{\epsilon }P]$.

Second, [4] introduced a model of biased random walks where a controller biases the random walk. That is, given a Markov chain $P$ and a parameter $\epsilon >0$, a controller chooses an arbitrary stochastic matrix $B$ with $\mathrm{supp}(B)\subseteq \mathrm{supp}(P)$ and the biased random walk follows $(1-\epsilon )P+\epsilon B$. That is, with probability $\epsilon$ the controller biases the walk, but has to respect the graph structure. Haslegrave, Sauerwald, and Sylvester [13] studied this in the time dependent setting. The focus of these papers is on a friendly controller who tries to improve the situation from the simple random walk. Our focus is on an adversarial controller who seeks to make matters worse. This will be our strong adversary.

In other words, in both cases, we have that $(1-\epsilon )P$ is left alone. A strong adversary may distribute the remaining $\epsilon$ probability arbitrarily on its support. A standard adversary is limited to change each probability by a bounded relative amount. However, a strong adversary with parameter $\epsilon$ is at most as powerful as a $(d_{\max }\epsilon )$-standard adversary, where $d_{\max }$ denotes the maximum degree. Since we are thinking of $d_{\max }$ as small or constant, we don’t dwell on the difference between the adversaries.

One might suggest an even stronger adversary that can take an arbitrary $\epsilon$ probability and distribute it arbitrarily. In other words, it can choose $P_t$ such that every row of $P$ and $P_t$ differs by at most $\epsilon$ in total variation distance. This adversary generalizes the adversary of [7]. However, if $\epsilon \ge 1/\mathrm{deg}(v)$ for some node $v$, then such an adversary can force the MSC to avoid hitting $v$. This renders some of our questions impossible, so we don’t consider this adversary.

We begin with the robustness of the stationary distribution $\pi$. Although MSCs may not converge to a distribution (see Section 3.1), we can still study the maximum and minimum limiting probabilities of sets. We can define this as follows. For $S\subseteq \mathrm{\Omega }$, let $N_t(S)$ denote the number of visits to $S$ up to time $t$.

We could define a lower limit ${\pi }^{-}$ analogously, but we focus on ${\pi }^{+}$.

For our first theorem, we use a variant of the mixing time that we call $t_{\mathrm{up}}$ (see Section 2.3). Like mixing time, it satisfies $t_{\mathrm{up}}=O(\frac{\log (1/{\pi }_{\min })}{\gamma })$, where $\gamma$ is the spectral gap. We prove the following.

Here the $o(1)$ term goes to 0 as $\pi (S)\to 0$, so in particular we have ${\pi }^{+}(S)=O(\pi {(S)}^{1-\alpha })$ for any $\alpha >0$.

The dependence of $\epsilon$ on $t_{\mathrm{up}}$ is essentially best possible, as the path graph shows.

To interpret this theorem, consider the case when the state space $V$ is exponentially large. Then any event with negligible stationary probability in the original chain has negligible stationary probability in this MSC with a nontrivial adversary. For example, [6] show that compression in their model happens with negligible probability; we deduce that this conclusion holds even if their chain is not followed exactly.

We could define stationary robustness as the largest $\epsilon$ such that the stationary probability analogues increase from $p$ to at most $O(p^{\beta })$ for some . The choice of $\beta$ or quantification over $\beta$ could a priori change the definition. However, Theorem 1.2 implies a robust stationarity of $\mathrm{\Omega }(\sqrt{d{t}_{\mathrm{up}}})$, and at least for the path the choice of $\beta$ doesn’t matter.

We compare Theorem 1.2 to the work of [4]. They only consider a time-independent adversary, although it wouldn’t matter for this theorem. The main difference between their work and ours is that they show a lower bound on the adversarial power, whereas we show an upper bound. Specifically, they showed that for any bounded-degree graph and any node $v$, some strong $\epsilon$-adversary can achieve ${\pi }^{+}(v)\ge \pi {(v)}^{1-\mathrm{\Omega }(\epsilon )}$, and that this is tight for an expander. Haslegrave, Sauerwald, and Sylvester [13] generalized this to more settings. Our Theorem 1.2 upper bounds ${\pi }^{+}(S)$ for every graph and every strong $\epsilon$-adversary.

We now turn to the robustness of the fundamental times associated with a random walk: mixing time, max hitting time, and cover time. We begin with mixing time, which requires some set up. Let $|\cdot |$ denote variation distance. We will generalize the following for a standard random walk. For a node $i$, let ${\mathrm{Pr}}_i$ denote the probability for a random walk starting at $i$. Let

To generalize this to MSCs, we define

Here $\pi$ is the stationary distribution of the original Markov chain, and the sup is over strong $\epsilon$-adversaries. Thus $\delta (t)\le {\delta }^{+}(t)$. We can now define the robust mixing time, which will be a workable definition despite the MSC possibly not converging.

Note that $t_{\mathrm{mix}}\le t_{\mathrm{mix}}^{+}(\epsilon )$, and that $t_{\mathrm{mix}}^{+}(\epsilon )$ may be infinite. This leads to the following definition.

It is not hard to show that the mixing time robustness is $\mathrm{\Omega }(1/(t_{\mathrm{mix}}d))$, where $d$ is the maximum degree; see Proposition 2.12. We achieve the square root of this quantity for constant-degree graphs.

This is tight for the path and the cycle. However, for expander graphs, this gives $\mathrm{\Omega }(1/\sqrt{\log n})$. We prove a constant lower bound for constant-degree expanders.

We now turn to some expected stopping times. Let ${𝔼}_u$ denote the expectation for a Markov (set) chain starting at $u\in V$. Let $H_v$ denote the hitting time of $v$: the time to first visit $v$ after time 0. The standard hitting times in an unbiased random walk are $h(u,v)={𝔼}_u{H}_v$, and the max hitting time is $t_{\mathrm{hit}}={\max }_{u\ne v}h(u,v)$.

Before defining the robust version, we briefly discuss the adversary. Note that if we have a strong $\epsilon$-adversary, the robustness for hitting and covering is less than $1/d_{\min }$, where $d_{\min }$ denotes the minimum degree. That’s because a strong $1/d_{\min }$-adversary can always avoid a particular node. Due to this and our proofs working better with standard adversaries, we define the robust versions for standard adversaries.

Generalizing an observation by [4], the quantities $h^{+}$ are the same for oblivious, Markovian, and non-Markovian adversaries. This is because an adversary’s best strategy at a given node does not depend on the previous history. This basically follows from Markov decision theory.

We focus on $t_{\mathrm{hit}}^{+}$ so we have one quantity rather than $n^2$ quantities. We can now define:

It is not hard to show that the hitting time robustness is $\mathrm{\Omega }(1/t_{\mathrm{hit}})$; see Proposition 2.12. We improve this bound dramatically.

We can improve this bound for trees. Let $\mathrm{\Delta }$ denote the diameter.

Note that $\mathrm{\Delta }=O(t_{\mathrm{mix}})$, and is often significantly less. For example, for the line and cycle on $n$ nodes, $\mathrm{\Delta }=\mathrm{\Theta }(n)$ but $t_{\mathrm{mix}}=\mathrm{\Theta }(n^2)$. Even more dramatically, for the balanced binary tree $t_{\mathrm{mix}}=\mathrm{\Theta }(n\log n)$ but $\mathrm{\Delta }=\mathrm{\Theta }(\log n)$.

For constant degree expanders, Theorem 1.10 gives a bound of $\mathrm{\Omega }(1/\log n)$. We show that this is tight for expanders by giving a matching upper bound, which is a negative result.

We now turn to the cover time. Let the random variable $T$ denote the first time the random walk has visited all nodes. We define the cover time $t_{\mathrm{cov}}={\max }_u{𝔼}_{u}T$.

Note that Markovian and non-Markovian adversaries do not appear to be equivalent, since the prior history is very relevant for the cover time. We now define:

It is not hard to show that the cover time robustness is $\mathrm{\Omega }(1/t_{\mathrm{cov}})$; see Proposition 2.12. We improve this in many cases. We always have $t_{\mathrm{cov}}=O(t_{\mathrm{hit}}\log n)$; we can improve the cover time robustness whenever this is tight up to a constant factor.

There are many graphs where $t_{\mathrm{cov}}=\mathrm{\Theta }(t_{\mathrm{hit}}\log n)$, including expanders (and hence most graphs) [5], the complete graph (coupon collecting), two and higher dimensional grids and tori [2, 25], and the balanced binary tree [24].

It’s instructive to see how our bounds apply to natural examples.

As another perspective, there has been a lot of research investigating the use of weak randomness in computing. In those situations, it is natural to allow computation on the weak randomness, for example to purify it into high-quality randomness. This work disallows such preprocessing, which is particularly natural when the random process models nature or social interactions.

We prove Theorem 1.2 and Theorem 1.6 about stationarity and mixing time robustness by generalizing a potential function argument by Haslegrave, Sauerwald, and Sylvester [13]. Their potential function uses squares to prove a lower bound. We use a potential function based on smaller powers to prove an upper bound. In particular, we need an inequality going in the opposite direction. Specifically, for $x=(x_1,\mathrm{\dots },x_d)\in {[0,\mathrm{\infty })}^d$ define the $\mathrm{\ell }$-power mean $M_{\mathrm{\ell }}(x)={(({\sum }_i{x}_i^{\mathrm{\ell }})/d)}^{1/\mathrm{\ell }}$, $M_{\mathrm{\infty }}={\max }_i{x}_i$, and the $\epsilon$-max-avg operator ${\mathrm{MA}}_{\epsilon }=\epsilon M_{\mathrm{\infty }}+(1-\epsilon )M_1$. We use Holder’s inequality and other ideas to bound ${\mathrm{MA}}_{\epsilon }(x)$ in terms of $M_{\mathrm{\ell }}(x)$ for some $\mathrm{\ell }$ just slightly larger than 1. We also simplify the [13] method somewhat, avoiding the use of trajectory trees.

We prove Theorem 1.7 about mixing time robustness of expanders by adapting the proof that the second largest eigenvalue determines convergence.

We prove Theorem 1.10 about hitting time robustness by showing that in a standard random walk, there’s the “right” probability of hitting a node within twice the separation time $t_{\mathrm{sep}}=O(t_{\mathrm{mix}})$. Specifically, for $h_v={𝔼}_{\pi }[H_v]$, we show that for all $u,v\in V$, we have ${\mathrm{Pr}}_u[H_v\le 2t_{\mathrm{sep}}]=\mathrm{\Omega }(t_{\mathrm{sep}}/h_v)$. We then show that this probability doesn’t decline much even in the robust setting. Dividing the random walk into epochs of length $2t_{\mathrm{sep}}$, we conclude that the hitting time doesn’t increase much. We further use this technique to give a simpler proof of the max hitting time for expanders, which will be in the final version of this paper. Given its utility for both of these theorems, we believe that this technique could be useful elsewhere.

We prove Theorem 1.11 by first observing that we can take the adversary to be oblivious, so the corresponding adversarial walk has a stationary distribution. We then compare the stationary distributions, and apply the “essential edge lemma” from Aldous-Fill about hitting times across cut edges.

We prove Theorem 1.12, the negative result giving a tight bound for expanders, by giving a target distribution and modifying the Metropolis algorithm. Much of this argument is similar to a lower bound on ${\pi }^{+}(S)$ by [4].

Theorem 1.15 about cover time robustness follows from Matthews’ technique for bounding the cover time in terms of the hitting time.

We have not found any previous work giving good bounds on our notions of robustness, except for lossless expanders. Doron, Moshkovitz, Oh, and Zuckerman [9, 10] analyzed extremely strong non-Markovian adversaries for lossless expanders, but their methods don’t apply more generally. They also didn’t analyze hitting or cover times.

In the model introduced by [4] and in follow-up works, the focus is on a controller seeking to minimize hitting and cover times, and they show lower bounds on increasing the probability of being in sets. For example, Haslegrave, Sauerwald, and Sylvester [13] improved a result of [4] and proved that an $\epsilon$-controller can increase the probability of being in a set from $p$ to approximately $p^{1-\epsilon }$. They used this to minimize hitting and cover times, for example showing how to reduce the cover time of an expander to $O(n\log \log n)$. This is different than our work where we view the controller as an adversary, so hitting times and cover times increase rather than decrease. Moreover, the quantification is different: they show that a suitable adversary exists, whereas we show that all adversaries are not too bad.

Chin, Moitra, Mossel, and Sandon [7] studied the power of an adversary in Glauber dynamics. Glauber dynamics is a type of random walk on ${\mathrm{\Sigma }}^V$, where $V$ is a set of nodes in an underlying graph and $\mathrm{\Sigma }$ is a finite alphabet. They proposed an adversary that controls any changes to a subset $A\subseteq V$ with $|A|\le \epsilon |V|$. They studied how such an adversary can affect global features of the system, such as the approximate mixing time. Their methods seem tailored to Glauber dynamics and not generalizable.

There is also research analyzing how the stationary distribution of a Markov chain is affected by perturbations. For example, Liu ([18], Theorem 2.2) showed that if $P$ is perturbed to $\tilde{P}$, which has stationary distribution $\tilde{\pi }$, then

where $|M|$ for a matrix $M$ is the maximum ${\mathrm{\ell }}_1$-norm of any row. Thus, the best bound on robustness that this could give is $\mathrm{\Omega }(1/t_{\mathrm{hit}}^2)$, which is much weaker than what we obtain. Moreover, our robustness is for Markov set chains, which are much more general than Markov chains.

Hartfiel [12] studies when Markov set-chains converge, and movement between transient states and absorbing states and the like. He doesn’t address the types of questions we ask.

Avin, Koucky, and Lotker [3] study random walks on evolving graphs. Here an adversary is allowed to completely change the graph, i.e., transition matrix, at every time step. However, the adversary doesn’t know the location of the random walker; in other words, the adversary decides the graphs in advance. They show that the cover time and mixing time could be exponentially larger than the cover times and mixing times of the individual graphs, but are only polynomially larger if the random walk is made lazy. This model is quite different from ours.

Hunter [14] studies a related model, what in our terminology is a strong oblivious adversary. He defines $\eta$ to be the “random target time” – the time for a random walk to hit a random node chosen according to $\pi$ – but confusingly calls this the mixing time. Really, $\eta$ is more closely related to $t_{\mathrm{hit}}$; see [16] for more on the random target time. He then shows that the adversarial walk has a stationary distribution at most $\eta \epsilon$-far from $\pi$ in variation distance. This is much weaker than our results.

There are other adversarial variants of Markov chains that don’t appear relevant for us. For example, the PageRank algorithm [20] and variants (e.g., [23]) allow perturbations where the adversary need not respect the graph structure, which leads to very different results. For another example, [8] define a model that they call “adversarial Markov chains” on an infinite metric space. In their model, transitions are followed exactly except when the chain is in some prespecified bounded subset, in which case an adversary can make arbitrary bounded jumps. They study whether such an adversarial chain remains bounded in probability.

We conjecture the following.

Since $\mathrm{\Delta }=O(t_{\mathrm{mix}})$, this would improve Theorem 1.10. Theorem 1.11 establishes this conjecture for trees, which is tight for the path and cycle.

What do we need to know about a graph to determine its robustnesses? Are the different robustnesses efficiently computable, perhaps up to constant factors?

Another class of interesting open problems is to determine the various robustnesses for natural graphs, such as different dimensional grids, hypercubes, and balanced trees.

We will assume throughout that any undirected graph $G=(V,E)$ is connected. We denote $n=|V|$, $m=|E|$, $\mathrm{\Gamma }(v)$ the set of neighbors of node $v\in V$, and $d_v=|\mathrm{\Gamma }(v)|$ the degree of $v$. A random walk on $G$ is a sequence of random variables $(X_0,X_1,\mathrm{\dots })$ where each $X_t\in V$ and $X_{t+1}$ is uniform on $\mathrm{\Gamma }(X_t)$. We use $P$ to denote the transition matrix of the random walk. Letting $p_t$ denote the probability distribution of $X_t$, viewed as a row vector, so we have $p_{t+1}=p_{t}P$. If $G$ is not bipartite, then $p_t$ converges to the stationary distribution $\pi$ given by $\pi (v)=d_v/(2m)$. Even if $G$ is bipartite, $(p_t+p_{t+1})/2$ converges to $\pi$.

Let ${𝔼}_u$ and ${\mathrm{Pr}}_u$ denote the expectation and probability, respectively, for a random walk starting at $u\in V$. Let $H_v$ denote the hitting time of $v$: the time to first visit $v$ after time 0. The standard hitting times in an unbiased random walk are $h(u,v)={𝔼}_u{H}_v$, and the max hitting time is $t_{\mathrm{hit}}={\max }_{u\ne v}h(u,v)$.

The following lemma is well known.

Expanders are graphs where every subset of nodes has many neighbors. We will use the standard spectral characterization, which is equivalent for constant expansion. For simplicity, assume that $G$ is regular. Denote the eigenvalues of $P$ by $1={\lambda }_1>{\lambda }_2\ge \mathrm{\dots }\ge {\lambda }_n\ge -1$. The last equality holds only when $G$ is bipartite. Let us assume that $G$ is not bipartite, e.g., by adding self loops. Let

denote the second largest eigenvalue in absolute value. Let $\gamma \stackrel{\mathrm{def}}{=}1-\lambda$ denote the spectral gap. We call $G$ a $\gamma$-spectral expander.

Recall the definition of mixing time, Definition 1.3. The choice of $\alpha$ only affects the mixing time up to a constant factor. Specifically:

For this and much more on the mixing time see, for example, the book by Levin, Peres, and Wilmer [16].

Up to a logarithmic factor, the reciprocal of the spectral gap $\gamma$ characterizes the mixing time. Specifically, it is known (e.g., [16] Theorems 12.3 and 12.4) that

We will use a variant of the mixing time called the separation time $t_{\mathrm{sep}}$.

In other words, it’s the minimum $\beta$ such that all nodes $v$ have $p_t(v)\ge (1-\beta )\pi (v)$.

We can now define separation time in the natural way.

For the proof, see Aldous-Fill [1]. Briefly, it’s immediate that $\delta (t)\le s(t)$. Aldous-Fill (Lemma 4.7 in [1]) show that $s(2t)\le 1-{(1-\delta (t))}^2$.

We further define a variant of the separation distance briefly discussed in Aldous-Fill in Equation 4.14. They left it unnamed, so we name it.

In other words, it’s the minimum $\beta$ such that all nodes $v$ have $p_t(v)\le (1+\beta )\pi (v)$.

We can now define upper separation time analogously.

While we have $\delta (t)\le s_{\mathrm{up}}(t)$, we can’t bound $s_{\mathrm{up}}(2t)$ in terms of $\delta (t)$; see Aldous-Fill’s Example 4.9. Nevertheless, the upper bounds of $t_{\mathrm{mix}}$ in terms of the spectral gap $\gamma$ also hold for $t_{\mathrm{sep}}$ and $t_{\mathrm{up}}$, just by examining the proof.

We will use the following notation.

We have the following simple lemma.

Note that this does not hold for a strong $\epsilon$-adversary, since such an adversary could move $\epsilon$ probability to a set $S$ with tiny $p_t(S)$.

It’s not hard to show that each robustness is at least the reciprocal of the corresponding quantity.

First we show that for a Markovian adversary, the MSC will not necessarily converge to $\pi$, even if all underlying chains are reversible. To see this, we define two weighted undirected graphs based on the path graph. Denote $\text{Odd}=\{\{i,i+1\}\mid i\text{ is odd}\}$, and $\text{Even}=\{\{i,i+1\}\mid i\text{ is even}\}$. Graph $G_{odd}$ assigns edges in Odd weight 2, and edges in Even weight 1, and adds weighted self loops at the two endpoints to make all nodes have weighted degree 3. Graph $G_{even}$ is the same but swaps even and odd: it assigns edges in Even weight 2, and edges in Odd weight 1. Let $P_{odd}$ denote a random walk on $G_{odd}$, and similarly for $P_{even}$. Since $G_{odd}$ and $G_{even}$ are both regular, both have uniform stationary distributions.

However, consider a Markovian MSC that chooses $P_{odd}$ if $X_t$ is odd and $P_{even}$ otherwise. If $X_t$ is not an endpoint, then $\mathrm{Pr}[X_{t+1}=X_t+1]=2/3$. We thus have a biased random walk which converges to a very biased distribution very far from uniform.

We prove that if a set $S$ has probability $p$, then a strong $\epsilon$-adversary cannot increase the probability to more than $O(p^{1-o(1)})$ as long as $td{\epsilon }^2=O(1)$. This quadratic dependence on $\epsilon$ improves on the easy linear dependence given by Lemma 2.11. We use a potential function argument that generalizes one by Haslegrave, Sauerwald, and Sylvester [13]. They used a potential function based on squares to prove a lower bound. We use a potential function based on smaller powers to prove an upper bound. In particular, we need an inequality going in the opposite direction as [13].

For $x=(x_1,\mathrm{\dots },x_d)\in {[0,\mathrm{\infty })}^d$ define the $\mathrm{\ell }$-power mean $M_{\mathrm{\ell }}(x)={(({\sum }_i{x}_i^{\mathrm{\ell }})/d)}^{1/\mathrm{\ell }}$, $M_{\mathrm{\infty }}={\max }_i{x}_i$, and the $\epsilon$-max-avg operator ${\mathrm{MA}}_{\epsilon }=\epsilon M_{\mathrm{\infty }}+(1-\epsilon )M_1$. We now develop the inequality we need.