4
$\begingroup$

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 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 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 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.

Thank you very much!

$\endgroup$
4
  • $\begingroup$ It sounds like you know of a complicated proof. If so, please say what tools that proof involves or give a reference. $\endgroup$ Jul 15, 2012 at 14:49
  • 1
    $\begingroup$ I have a hard time with this description. It doesn't sound as though you've uniquely described any object. You haven't told us whether the sons of left vertices are left vertices, right vertices or a mixture of the two. $\endgroup$ Jul 15, 2012 at 15:39
  • 1
    $\begingroup$ @Anthony, there is a clearer definition on pages 8-9 of Yuval Peres's lecture notes on "Probability on Trees: An Introductory Climb" at stat-www.berkeley.edu/~peres/climb.ps $\endgroup$ Jul 15, 2012 at 17:42
  • $\begingroup$ Thanks @Barry. It looks as though Yuval's notes also answer the OP's question. $\endgroup$ Jul 15, 2012 at 19:45

3 Answers 3

6
$\begingroup$

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$.

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.

$\endgroup$
2
  • $\begingroup$ Hi, Can you explain this: "the resistance in the downward direction is infinite" Thanks $\endgroup$
    – user25748
    Aug 16, 2012 at 16:28
  • $\begingroup$ Consider collapsing all vertices in level $n$ or below which are descendants of $v$ to a single new vertex $v_n$. As $n\to\infty$, the resistance between $v$ and $v_n$ goes to infinity. See chapter $2$ of math.dartmouth.edu/~doyle/docs/walks/walks.pdf . $\endgroup$ Aug 17, 2012 at 2:16
4
$\begingroup$

You can find this example discussed also in my book with Russ Lyons, "Probability on Trees and networks", http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html

As Douglas points out, 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. Thus a flow of finite energy from the root cannot assign any positive mass to an edge off the left ray, since some of this mass has to eventually go down an infinite ray with no branching which yields infinite energy. But a flow confined to the leftmost ray certainly has infinite energy.

$\endgroup$
0
$\begingroup$

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?

Thanks

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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