Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What exactly does a "transient random walk on a graph/binary tree" mean? Does it mean that we never return to the origin (assuming there is one as for the tree) or just any vertex of the graph or tree? Thanks.

share|cite|improve this question
up vote 1 down vote accepted

You can define transience on an infinite graph, but you need sufficient conditions on the graph so that transience means the same thing for all vertices. For example, if you can go from every vertex to every vertex with positive probability, then this is sufficient.

(In particular, if you have a simple random walk on the graph, it is sufficient to suppose that the graph is connected and locally finite, that is, any two vertices are joined by a finite path and all degrees are finite.)

On a finite connected graph the random walk is always recurrent.

share|cite|improve this answer

I not so familiar with the terminology exactly for random walks on graphs, but since any random walk on graph is a Markov Chain, we just can refer to the Wikipedia article about Markov Chains: the state is called transient if there is non-zero probability to never return to that state. The Markov Chain is called transient if any state of it is transient.

Following your logic for the binary tree that would impossible to define transience of a random walk on any digraph in the natural way, because there we may not have an origin.

share|cite|improve this answer
I think you've written "recurrent" where you meant to write "transient". – Gerry Myerson Oct 28 '11 at 10:12
@GerryMyerson: thanks, weird typo (8 letters). Apparently I was thinking about my problem typing the answer. – Ilya Oct 28 '11 at 10:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.