I'm stuck on a homework question and am wondering if anyone can offer some hints. Suppose we have some straight line graph G over the set $ V = \{1, 2, 3, ... , n\} $ of vertices, with an edge between $u$ and $v$ if and only if $u$ = $v\pm1$
That is it looks like 1 --- 2 --- 3 --- 4 --- ... --- n
I'm trying to compute the probability $p_{i}$ that starting at node $i$, a random walk hits node $1$ before node $n$. Obviously, $p_1 = 1$ and $p_n = 0$
We've been covering Markov processes in my class, but everything reagrding walks so far has been about the expected hitting time of a node v starting at a node u, and I don't see how to use that here. Computing the hitting time of 1 and n from a node i doesn't allow us to know the probability of reaching one before the other, unless I'm missing something.
So far I've tried using:
$p_i = \frac{p_{i-1}}{2}+\frac{p_{i+1}}{2}$
but I quickly run into trouble doing this, since you get some messy variant of Pascal's triangle.
I also tried proceeding by induction but can't seem to get anywhere doing that either. Surely there's an elegant approach.
Thanks!