2
$\begingroup$

I am working on a computer program. It can be represented as a linear series of states $s_0 \ldots s_n$

Function $N(s_x)$ is defined such that:

  • With a probability $p$ it will return the next state $$s_x \rightarrow \left\{ \begin{array}{ll} s_{x+1} & \mbox{if } x \lt n \\ s_{x} & \mbox{otherwise} \end{array} \right.$$
  • With a probability of $p$ it will return the previous state $$s_x \rightarrow \left\{ \begin{array}{ll} s_{x-1} & \mbox{if } x \gt 0 \\ s_{x} & \mbox{otherwise} \end{array} \right.$$
  • With a probability of $1-2p$ it will return the current state $$s_x \rightarrow s_x$$

The program is an iterative application of $N$ to the initial value $s_i$ $r$ times $$Program = N^r(s_i)$$

I need to find $P(N^r(s_i) = s_x)$ for all $0 \leq x \leq n$ (the probability that applying $N$ iteratively to $s_i$ $n$ times yields the state $s_x$)

For small values I've been manually working out the different combinations that can lead to a particular state. For example, if $n=2$, $i=1$, $p=0.25$ and $r=2$ I can create a tree to help figure out the probabilities:

A tree if n=2, i=1, p=0.25 and r=2

In this case: $$P(s_0) = 0.25*0.25 + 0.25*0.5 + 0.5*0.25 = 0.3125$$ $$P(s_1) = 0.25*0.25 + 0.5*0.5 + 0.25*0.25 = 0.375$$ $$P(s_2) = 0.5*0.25 + 0.25*0.5 + 0.25*0.25 = 0.3125$$

However, this obviously gets impractical for the larger values I need to deal with in real life (e.g. $r=500$). Is there an easier way to calculate the probabilities?

3 Answers 3