$N$ nodes $(Node_1 .. Node_N)$ are arranged in a circle, and a robot is placed at $Node_1$. The robot moves clockwise with probability $p$ and counter-clockwise with prob. $(1-p)$. Given integers $S, B \in \mathbb{N}$, where $1<=B<=N$, what's the probability of it landing on $Node_B$ after taking $S$ steps?
I know there's a mathematical formulation of this problem, but I haven't been able to shift from an algorithmic frame of mind. What I've come up with is:
E = minabs(S - B) # How many steps is the minimum allowed to get to Node_B?
if(S < E) { Prob = 0 } # There aren't enough steps to get to Node_B
if (S == E) && (S-B < 0) { Prob = (1 - p)^S } # Only S counter-clockwise steps will get to Node_B.
if (S == E) && (S-B > 0) { Prob = p^S } # Only S clockwise steps will get to Node_B.
However, I'm stuck trying to think through the possible scenarios when $S > E$. Extracting the cases where the robot goes completely around the ring in either direction, or where a move in one direction is countered by the opposite move have me overwhelmed, and thinking there must be a better way.
Let $X$ be the clockwise moves. The net clockwise displacement after $S$ steps is $X-(S-X)=2X-S$. Let $i$ be the position (node index) indexed $0,1\cdots, N-1$. Assume you start at $i=0$, you end in node $j$ if $2X-S = j \pmod N$ or
$$ 2X = j +S \pmod N $$ with $0\le X\le S$
Let $X_i$ be the solutions of this modular equation. Then the probability is simply
$$ P=\sum_i \binom{S}{X_i} p^{X_i} (1-p)^{S-X_i}$$