1
$\begingroup$

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?

1 Answers 1

3

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$.