Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

Let $a_k$ be the expected number of steps to reach $0$ when you start at $k$. Clearly $a_0=0$. For $k\ne 0$ we must have $$a_k=1+\frac12a_{k-1}+\frac12a_{k+1}\;,$$ where the arithmetic in the subscripts is performed modulo $n$: you must take a step, and then with probability $1/2$ you’re at node $k-1$, and with probability $1/2$ you’re at node $k+1$. After multiplication by $2$ to clear the fractions, the resulting system (ignoring $a_0$) is

$$\begin{align*} 2a_1&=2+a_2\\ 2a_2&=2+a_1+a_3\\ &\;\vdots\\ 2a_k&=2+a_{k-1}+a_{k+1}\\ &\;\vdots\\ 2a_{n-2}&=2+a_{n-3}+a_{n-1}\\ 2a_{n-1}&=2+a_{n-2}\;. \end{align*}$$

Add these $n-1$ equations to get


after subtraction of common terms on both sides, this is simply


It's clear from symmetry that $a_1=a_{n-1}$, so $2a_1=2(n-1)$, and $a_1=n-1$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.