How many steps to reach the trail's end?

Question

A hiker moves among trail markers 0, 1, and the End (marker 2). Each step: - From marker 0: stay at 0 with probability 0.5, or move to marker 1 with probability 0.5. - From marker 1: reach the End with probability 0.5, or slip back to marker 0 with probability 0.5. The End stops the hike. The hiker starts at marker 0. On average, how many steps until the hiker reaches the End?

Accepted Answer

Let h(0) and h(1) be the expected steps to the End from markers 0 and 1; the End itself needs 0 steps. First-step analysis: one step passes, then add the expected time from the next marker. h(0) = 1 + 0.5\,h(0) + 0.5\,h(1), h(1) = 1 + 0.5 \cdot 0 + 0.5\,h(0). From the first equation, 0.5\,h(0) = 1 + 0.5\,h(1), so h(0) = 2 + h(1). Put this into the second: h(1) = 1 + 0.5\,(2 + h(1)) = 2 + 0.5\,h(1) \implies 0.5\,h(1) = 2 \implies h(1) = 4. Then h(0) = 2 + 4 = 6 	ext{ steps}. So the hiker reaches the End after 6 steps on average. Takeaway. Self-loops (staying at marker 0) and backslides (marke…

How many steps to reach the trail's end?

Your answer

Discussion

Learn the concepts

Related questions