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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.