2

In the book “Quantum Algorithms via Linear Algebra” I found this definition for the hitting time of a random walk:

$k$ giving $max_{u,v}|D(v) - A^l[u,v]| < \epsilon$ for all $l \geq k$ is called the hitting time.

Where $A$ is the walk matrix and $D$ is its stable distribution.

From my understanding, the hitting time for a start node $u$ and target $v$ is the minimum number of steps after which $v$ is hit starting from $u$.

How is this equivalent to the definition in the book, which I read as the minimum number of steps until the probability to reach $v$ from $u$ is almost the same as the probability of $v$ in the stable distribution?

x squared
  • 81
  • They look like different definitions... I'm surprised that the book refers to that $k$ as the hitting time, typically it's called the mixing time. – Chris Jones Jul 15 '17 at 01:30
  • The mixing time they define as “The relation between $\epsilon > 0$ and the power $k$ needed to ensure $||CA^l - D|| \leq \epsilon$ for all $l \geq k$, where ||•|| is the max-norm”. C is an arbitrary initial distribution. – x squared Jul 15 '17 at 11:55
  • Those look like nearly the same definition! The max norm is $|CA^l - D|\infty = \max_v |CA^l(v) - D(v)|$. If we enforce that $C$ is a single vertex $u$, the formula becomes $\max{u,v} |A^l(u, v) - D(v)|$. Notice that this is their formula for the hitting time. – Chris Jones Jul 16 '17 at 18:23

0 Answers0