Loading ...
Sorry, an error occurred while loading the content.

Random walk question

Expand Messages
  • Svein Olav Nyberg
    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
    Message 1 of 1 , Apr 19 12:05 AM
    • 0 Attachment
      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
      exotic counterexample.

      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.


      Regards,
      Svein Olav Nyberg


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.