Bounds for finite Markov chains

Question

Problem

Let $G$ be a strongly connected directed graph with $n$ vertices, and let $d(v)$ denote the out-degree of vertex $v$. Let $M_G$ be a finite discrete-time homogeneous Markov chain defined over $G$ s.t. the vertices are the states of $M_G$. And for any two vertices $u,v$ probability of going to state $v$ from state $u$ is given by $$ p_{uv} = \begin{cases} \frac{1}{d(u)} \text{ }\text{ if } u \to v \text{ is a directed edge in } G \\ 0 \text{ }\text{ otherwise} \end{cases} $$ Let $h_{uv}$ denote the expected time (or number of steps) to reach $v$ from $u$. The hitting time $h$ of $M_G$ is $\max\limits_{u,v}\{h_{uv}\}$. Can $h$ be upper bounded just in terms of $n$ ?

What I know

1. For connected undirected graphs, the hitting time is known to be upper bounded by $\mathcal{O}(n^3)$.
2. For strongly connected directed graphs one can come up with instances with exponential hitting time (reference: https://cstheory.stackexchange.com/questions/2908/cover-time-of-directed-graphs).

My approach

Let $m$ be the number of edges in $G$. Then $\frac{1}{d(v)} > \frac{1}{m}$. We define the following experiment: We have a biased coin that gives heads with probability $\frac{1}{m}$. We flip it till we get $n-1$ consecutive heads. Then the expected number of coin flips required is bounded from above by $m^n$ (reference: Expected number of tosses for two coins to achieve the same outcome for five consecutive flips). I argue $h$ is bounded from above by $m^n$ as well. For any arbitrary $u,v$ let the longest path $P$ from $u$ to $v$ be of length $l$ ($l\le n-1$). Expected number of steps required to reach $v$ from $u$ by such that the walk ends in $P$ is $\ge h_{uv}$. Let $P$ be $w_1 \to w_2\cdots \to w_{k}$ ($u=w_1,v=w_k$). The probability for going from $w_i$ to $w_{i+1}$ is $\frac{1}{d(w_i)} > \frac{1}{m}$. If the random walk at some point diverges from $P$ (makes a "wrong" choice), we are at some vertex $u^{'}$ and we argue similarly as we did for $u$.
In the biased coin flip experiment also we need $n-1$ "correct" choices (heads) to happen. And the probability of a correct choice in the experiment is $\frac{1}{m}$. Which is less than the probability of a "correct" choice ($\frac{1}{d(v)}$ for some $v$) in the random walk. Thus the expected number of coin flips is $\ge h$.

Is my approach flawed? If yes, is it possible to obtain a bound at all?

PS. I would highly appreciate a hint only or a nudge in a direction I can explore.

Answer 1

So your actual estimate appears to be basically $ml$: making each step of progress along the path requires on average $m$ steps and there are $l$ of them to make. But this is not right, because errors can increase how much further you need to go.

Consider for a simple case a chain with $n+1$ states $0,1,2,\dots,n$ where $k \to k+1$ with probability $1/2$ and $k \to 0$ with probability $1/2$. The longest acyclic path from $0$ to $n$ has $n$ steps in it, and the expected number of steps before you make a traversal is $2$. But this does not mean the expected hitting time is $2n$. Far from it, because an "excursion" only succeeds with probability $2^{-n}$, so the expected hitting time is instead $2^n$ times the expected length of an excursion which is $2$.

(It actually looks like this is exactly the graph described in the OP of your link, but I actually did not click your link until after I wrote that, so I'll leave it.)

That being said the hitting time cannot be worse than exponential in an irreducible chain, because the probability of a particular path of length $n$ is no more than exponentially small (greater than $\frac{1}{m^n}$, say) and the expected recurrence time in an irreducible chain is finite (being given by the reciprocal of the invariant probability to be in that state). You can combine these to get a (potentially extremely bad) bound for the hitting time:

$$E[\tau_i \mid X_0=j]=E[\tau_i \mid \tau_i<\tau_j,X_0=j] P[\tau_i<\tau_j]+E[\tau_i \mid \tau_i \geq \tau_j]P[\tau_i \geq \tau_j] \\ \leq l \frac{1}{D^l} + (E[\tau_i \mid X_0=j]+\pi_j^{-1}) \left ( 1 - \frac{1}{D^l} \right )$$

where $D$ is the maximum out-degree of any one vertex and $l$ is the length of any path from $j$ to $i$.

Thus $E[\tau_i \mid X_0=j] \leq l + D^l \pi_j^{-1}$.