Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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

$$2\sum_{k=1}^{n-1}a_k=2(n-1)+a_1+a_{n-1}+2\sum_{k=2}^{n-2}a_k\;;$$

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

$$a_1+a_{n-1}=2(n-1)\;.$$

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

share|improve this answer
add comment

Your Answer

 
discard

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.