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)$.