So we have an undirected graph with vertices labeled 0,1...n. We start at 1 and we can go either left or right . We want to know the # of steps expected to get to 0.
I figured that half the time you get to 0, and the other half you get to 2. At 2 half the time you get to 1, half the time you get to 3. You get n equations and just sub it in and get expected steps starting at 1. However, I keep getting "1" as the answer, which doesn't make sense.
What's a good way to tackle the problem?