Simple random walk on the 3-1 tree is recurrent - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T15:48:25Z http://mathoverflow.net/feeds/question/102283 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102283/simple-random-walk-on-the-3-1-tree-is-recurrent Simple random walk on the 3-1 tree is recurrent Daniel D 2012-07-15T12:31:41Z 2012-08-16T16:28:47Z <p>Hello guys,</p> <p>There is an infinite tree structure named <em>"the 3-1 tree"</em>, denoted by $T_{3-1}$. The tree is constructed as follows:</p> <p>The origin vertex (which can be referred to as the zeroth 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 <strong>left half</strong> which consists of $2^{n-1}$ vertices and the <strong>right half</strong> which consists of the other $2^{n-1}$ vertices). From each <strong>left</strong> vertex we have three edges leaving it (therefore it has three sons) and for each <strong>right</strong> 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.</p> <p>It is a known fact that simple weighted random walk (all edges have weight 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.</p> <p>Thank you very much!</p> http://mathoverflow.net/questions/102283/simple-random-walk-on-the-3-1-tree-is-recurrent/102289#102289 Answer by Douglas Zare for Simple random walk on the 3-1 tree is recurrent Douglas Zare 2012-07-15T14:41:55Z 2012-07-15T23:33:37Z <p>For any vertex $v$ which is not in the all-left ray, there is some generation $n$ so that all descendants of $v$ in the $n$th generation are in the right half. (If the fraction of vertices to the left of $v$ in its level is $\alpha$, this happens by $\lceil \log_{3/2} 1/(2\alpha) \rceil$ generations below $v$, since the fraction of vertices to the left expands by a factor of $3/2$ until the generation when it reaches $1/2$.) This means the number of descendants of $v$ in each generation is eventually constant, so the resistance in the downward direction is infinite. Therefore, with probability $1$ a random walk starting at $v$ will reach the parent of $v$. </p> <p>So, a random walk on the $3-1$ tree almost surely retracts to a random walk on the all-left ray. Since this random walk is recurrent, the random walk on the $3-1$ tree is recurrent.</p> http://mathoverflow.net/questions/102283/simple-random-walk-on-the-3-1-tree-is-recurrent/103078#103078 Answer by Dan jenkin for Simple random walk on the 3-1 tree is recurrent Dan jenkin 2012-07-25T08:47:19Z 2012-07-25T08:47:19Z <p>I was trying to solve this problem by showing that every flow from $o$ to $\infty$ on this graph must have infinite energy. Therefore, by Lyons criterion the graph must be recurrent. But I didn't succeed finishing the proof. Does any of you guys have suggestions?</p> <p>Thanks</p> http://mathoverflow.net/questions/102283/simple-random-walk-on-the-3-1-tree-is-recurrent/104857#104857 Answer by Jimi for Simple random walk on the 3-1 tree is recurrent Jimi 2012-08-16T16:28:47Z 2012-08-16T16:28:47Z <p>Hi,</p> <p>Can you explain this:</p> <p>"the resistance in the downward direction is infinite"</p> <p>Thanks</p>