For a random walk process on the complete infinite binary tree starting from root (i.e. level $0$), we assume that the object moves to the neighbor nodes with equal probability. Let $X_n$ denote the level number at time $n$. Prove that $$\mathbb{E}[X_n]\le \frac{n+4}{3}.$$
Of course when the node is not the root there’s probability $\frac{1}{3}$ of level down and probability $\frac{2}{3}$ of level up, which has an average of level $\frac{1}{3}$ up. However the problem occurs when dealing with the root. The root has an $1$ probability of level up, the probability of returning $1$ is big and it’s hard to estimate it’s influence to $\mathbb{E}[X_n]$. So are there anyways of ‘bounding’ the influence of the root to the final expectation? Thanks!
The problem can be also rephrased as a infinite Markov chain with one state per level of the binary tree. I'll count the states from $0$ and use $p_n(i)$ for the probability of being in state $i$ after $n$ steps. So our system is defined by: $$ p_0(0) = 1 \\ p_0(i) = 0 \textit{, for $i > 0$} \\ p_{n+1}(0) = \frac13 p_n(1) \\ p_{n+1}(1) = p_n(0) + \frac13 p_n(2) \\ p_{n+1}(i) = \frac23 p_n(i-1) + \frac13 p_n(i+1) \\ $$ Next, we try to see how $E[X_{n+1}]$ compares to $E[X_n]$. $$ E[X_{n+1}] = \sum_{i=0}^\infty i \cdot p_{n+1}(i) \\ = 0 \cdot \frac13 p_n(1) + 1 \cdot (p_n(0) + \frac13 p_n(2)) + \sum_{i=2}^\infty i \cdot \left(\frac23 p_n(i-1) + \frac13 p_n(i+1)\right) \\ = p_n(0) + \frac13 p_n(2) + \frac23\sum_{i=1}^\infty i\cdot p_n(i) + \frac23\sum_{i=1}^\infty p_n(i) + \frac13\sum_{i=3}^\infty i \cdot p_n(i) - \frac13\sum_{i=3}^\infty p_n(i) \\ = p_n(0) + \frac13 p_n(2) + \frac23 E[X_n] + \frac23 \cdot (1 - p_n(0)) + \frac13 \cdot (E[X_n] - p_n(1) - 2 p_n(2)) - \frac13 \cdot (1 - p_n(0) - p_n(1) - p_n(2)) \\ = E[X_n] + \frac13 + \frac23 p_n(0) $$ From this we can get the value of the expected level as $E[X_n] = \frac n3 + \frac23\sum_{k=0}^{n-1} p_k(0)$.
This shows that your intuition is correct and that the main challenge is the root, because now we have left to prove $\frac23\sum_{k=0}^{n-1} p_k(0) < \frac43$, which in fact means that we want something even stronger: $S := \sum_{k=0}^\infty p_k(0) \leq 2$.
Now we focus on $p_k(0)$, the probability of being back at the initial state after exactly $n$ steps. We can write a run of n steps as a sequence of parentheses, using $($ for a forward step and $)$ for a backward step. With this convention, notice that runs that start and end at the root correspond to a string of properly closed parentheses. The first thing to get from this is that $p_k(0) = 0$ when $k$ is odd.
For $n = 2u$ we have that the total number of paths starting and ending at the root is the same as the number of strings of properly closed parentheses of length $2u$, which is Catalan's number $C_u = \frac1{u+1}{2u \choose u}$. The probability of a given path depends on the number of times it leaves the origin, because that probability is $1$ instead of $2/3$ for other forward steps. So for a given path of length $2u$ which leaves the root $v$ times, the probability is $\left(\frac23\right)^u \cdot \left(\frac13\right)^{u - v}$. To get the value of $S$ we will group these paths by $v$, noting that a path that leaves the root $v$ times is the concatenation of $v$ paths that only leave the root once, and it's probability is the product of the probabilities of those subpaths.
For a path that only leaves the root once, of length $2u+2$, the probability can be rewritten as $\left(\frac23\right)^{u+1} \cdot \left(\frac13\right)^{u} = \frac13 \cdot \left(\frac29\right)^{u}$. With this, we can count the paths grouped by how many times they leave the root node as: $$ T := \sum_{v\geq 1}\left(\frac13\right)^v\sum_{u_1,\ldots,u_v\geq 0} \prod_{i=1}^v C_{u_i} \left(\frac29\right)^{u_i} = \sum_{v\geq 1}\left(\frac13\right)^v \left( \sum_{u \geq 0} C_u \left(\frac29\right)^u \right)^v = \sum_{v\geq 1} \left( \frac13 \sum_{u \geq 0} C_u \left(\frac29\right)^u \right)^v $$ Note that if we show that $T$ converges, then we will have $S=T$ also.
Now notice $C_{n+1}/C_n = 1 + \frac3{n+2}$. With this, we can use induction to prove $C_n \leq \left(\frac94\right)^n$ and then use this to get $$ \frac13 \sum_{u \geq 0} C_u \left(\frac29\right)^u = \frac13 \sum_{u \geq 0} \left(\frac94\right)^u \left(\frac29\right)^u = \frac23 \Rightarrow T \leq \sum_{v\geq 1}\left(\frac23\right)^u = 2 $$ And this completes the proof.