Expected number of steps to traverse a graph

Question

i have a graph

adj(a)={b,e} adj(b)={a,c} adj(e)={a,d} adj(d)={e,c} adj(c)={b,d}

at any vertex i can go it's adjacent vertex with probability 1/2. So what is the expected number of steps to reach 'c' starting from 'a'?

Answer 1

I'm short on time, but here are some hints.

Not being well-versed in probability theory, I can only give a naive answer. I would think the answer is:

$$\sum^{\infty}_{k=0}\frac{n(k)\ k}{2^k}$$

Where $n(i)$ is the number of paths of length $i$ that start at $a$ and end at $c$, and $2^i$ should be the number of paths of length $i$ from a to $c$, since at each node of the path you choose between moving clockwise or moving counterclockwise. So this is just a power series at $x=1/2$.

Since moving around a pentagon is basically just doing addition modulo $5$, where at each step we either add or subtract $1$, we can think of a path of length $k$ as a finite sequence of numbers $1$ and $-1$ (or $1$ and $4$ if you prefer). If we associate $a$ with $0$, then $c$ is $2$ and the condition that the path ends at $c$ is simply that the sum of those numbers is equal to $2$ modulo $5$. So how many sequences of length $k$ of the numbers $1$ and $-1$ sum to $2$ modulo $5$, and such that the sums of all of its prefixes are different to $2$ modulo $5$? That's $n(k)$.

Assuming the above isn't complete gibberish, and if you can find a nice expression for $n(k)$, you have the coefficients for your power series, which you can then hopefully prove is convergent and calculate its sum.

Answer 2

This is standard Markov chain hitting time stuff. For every vertex $x$, call $n(x)$ the mean number of steps needed to reach $c$ starting from $x$. The question is to compute $n(a)$ and the idea in this context is to compute every $n(x)$, using the fact that they solve a Cramér system of affine equations.

By symmetry, $n(a)=n(e)$ and $n(b)=n(d)$, furthermore $n(c)=0$. The usual one-step analysis yields $n(a)=1+\tfrac12(n(b)+n(e))$ and $n(b)=1+\tfrac12(n(a)+n(c))$. This can be rewritten as $2n(a)=2+n(b)+n(a)$ and $2n(b)=2+n(a)$, which yields $n(a)=$ $____$.

Answer 3

Let $x$ be the expected number of steps from $a$ to $c$.
The expected number of steps from $e$ to $c$ is $x$ by symmetry.
The expected number of steps from $c$ to $c$ is $0$.
The expected number of steps from $b$ to $c$ is $1+\frac{x+0}2=\frac{x+2}2$.
Solving the equation$$x=1+\frac{x+\frac{x+2}2}2$$I get $x=6$.

Answer 4

Here's an easy to remember shortcut. For a symmetric random walk on a circle, the expected number of steps to reach state $c$ starting at state $a$ is the product of two numbers: the distance from $a$ to $c$ clockwise, and the distance from $a$ to $c$ counterclockwise.

In the OP's problem, these are 2 and 3 respectively so the answer is 6.