Hello guys, There is an infinite tree structure named "the 3-1 tree", denoted by $T_{3-1}$. The tree is constructed as follows: The origin vertex (which can be referred to as the zero level) has two sons. In each level $n$ we have $2^n$ vertices. In order to construct the next level, we split the $2^n$ vertices into two groups (the left half which consists of $2^{n-1}$ vertices and the right half which consists of the other $2^{n-1}$ vertices). From each left vertex we have three edges leaving it (therefore it has three sons) and for each right vertex we have only one edge leaving (therefore it has only one son). This way, in every level there are indeed $2^n$ vertices and a total of $2^{n+1}$ edges leaving that level. This is the structure. It is a know fact that simple weighted random walk (all edges have weight which equals to 1, i.e. $c(x,y)=1$ $\forall$ $x,y\in T_{3-1}$) on $T_{3-1}$ is recurrent. I would like to prove this using simple tools such as electrical networks, martingales and standard probability tools. Thank you very much!
Simple random walk on the 3-1 Tree is recurrent
Daniel D
- 91
- 1