Random walk question
- Dear group, I have an embarrassingly simple question for you:
Given a finite graph and a reversible random walk on that graph with
not necessarily uniform transition probabilities OR transition times
For a pair of nodes on the graph, x and y, let T be the average
transversal time from x to y ...
THEN there exists a subgraph
* stretching from x to y,
* without loops or branches
such that the average transition time for process, restricted to the
subgraph, with standard conditional probabilities, is less than T.
It is the kind of theorem that is so obvious that it is either in
some old textbook and has its own name, or there exists some truly
I would be grateful if any of you could recall where I can find such
a theorem (probably better stated than the above), and its name.
Svein Olav Nyberg
[Non-text portions of this message have been removed]