Stochastic Processes Solution – Problem 25: Find

Question

Consider the following random walk starting from the root of an infinite binary tree: if the current state is the root, jump to a uniformly chosen child; otherwise, with probability 3/4 jump to the parent, and with probability 1/4 jump to a uniformly chosen child (so each child has jump probability 1/8). Let $\tau$ be the first return time to the root (note $\tau\geq1$ ).

(a) Find $E_{\tau}$ .

(b) Given that the first child of the root was visited 10 times before returning to the root, find the conditional expectation of $\tau$ .

Step-by-step solution

(a) Let $E$ be the expected time for a non-root vertex $v$ to first reach its parent $P(v)$ . By the self-similarity of the infinite binary tree, $E$ is the same for all non-root vertices.

From any non-root vertex $v$ : 1. With prob. $3/4$ , jump to parent: cost 1 step. 2. With prob. $1/4$ , jump to a child $c$ : cost $1 + E + E = 1 + 2E$ (return from $c$ to $v$ , then from $v$ to parent).

By the law of total expectation: $E = 3/4 \cdot 1 + 1/4 \cdot (1 + 2E) = 1 + E/2$ , so $E = 2$ .

For $\tau$ : the first step goes to a child (cost 1), then return to root costs $E = 2$ . $E_{\tau} = 1 + E = 3$ .

(b) Let $u$ be the designated first child of the root. Given $u$ is visited 10 times before returning to root, decompose $\tau$ into three parts:

1. Root to $u$ : 1 step (first visit to $u$ ). 2. 9 dive-and-return cycles at $u$ : Each of the first 9 visits to $u$ must be followed by a descent to a child (otherwise the walk would return to root, ending with fewer than 10 visits). Each cycle costs $1 + E = 3$ steps. Total: $9 \times 3 = 27$ . 3. $u$ back to root: On the 10th visit, the walk must go directly to root (cost 1 step).

$E[\tau | N_u = 10] = 1 + 9 \times 3 + 1 = 29$ .

Final answer

(a) 3 (b) 29

Marking scheme

1. Checkpoints (max 7 pts total)

Note: This section contains parallel solution paths. Determine which method the student used, score the highest-scoring path, and do not combine points across paths.

(a) Finding $E_{\tau}$ (4 pts)

Path A: Recursive Expectation (Official Solution)

[2 pts] Establish the recurrence for $E$ : Define $E$ as the expected return time from a non-root vertex to its parent. Write $E = 3/4 \cdot 1 + 1/4 \cdot (1 + 2E)$ or equivalent. *Key*: must reflect "after descending, one must return to the current vertex and then to the parent" (the $2E$ or $E+E$ term). Writing $1+E$ (missing one return step) earns 0 for this checkpoint.
[1 pt] Solve $E = 2$ : Simple algebra. If the equation is wrong but solving is correct, no credit.
[1 pt] Compute $E_{\tau}$ : Correctly apply $E_{\tau} = 1 + E$ and obtain 3.

Path B: Stationary Distribution

[1 pt] Establish detailed balance equations between root/child and child/grandchild.
[2 pts] Sum and normalize (identify geometric series with ratio 1/3), solve $\pi_{\text{root}} = 1/3$ .
[1 pt] Apply Kac's formula $E_{\tau} = 1/\pi_{\text{root}} = 3$ .

(b) Conditional expectation (3 pts)

[1 pt] Path structure decomposition: Identify the three-part structure: first step to $u$ (1 step) + 9 dive-and-return cycles + final step to root (1 step). The expression $1 + 9 \times (\dots) + 1$ suffices.
[1 pt] Single cycle expectation: State or compute that each dive-and-return from $u$ costs $1 + E = 3$ . *Error propagation allowed*: if $E$ is wrong in (a) but the logic $1+E$ is correct, this point is awarded.
[1 pt] Final computation: Correctly combine to get $1 + 27 + 1 = 29$ . If the student interprets "visited 10 times" as "at least 10 times" and gets 30, deduct this point but keep the first two.

Total (max 7)

2. Zero-credit items

Merely copying the probability values (3/4, 1/4) without setting up equations.
Listing "law of total expectation" or "Markov chain" without concrete application.
In (a), guessing $E=2$ or $E_\tau=3$ with no derivation.
In (b), simply multiplying $E_\tau$ by 10 or other illogical arithmetic.

3. Deductions

Arithmetic error: Correct setup but computational mistake in final value: -1 pt (once only).
Logical contradiction: Computing $E < 0$ but taking absolute value without explanation: -1 pt.
Condition misunderstanding: In (b), not realizing the 10th visit must go directly to root, adding $E$ instead (getting 30): lose the final computation point only (2/3 for part b).

Stochastic Processes – Problem 25: Find