Modeling a 1D random walk with nonconstant probability in a point

Question

There is a 1D discrete random walk system where the probabilities at all points are $\frac{1}{2}$ (probability of going forward and backward) except one point at on $l$ (which is an integer). The probability of going right is $p$ at this point ($p$ isn't necessarily $\frac{1}{2}$). There is just one number where the probability of going right and left is different from the other numbers.

• How can I model this process?

• For fixed $N$ (number of steps) how can I find the probability of reaching a specified point by starting at $0$?

For example, with $N=10$, $l=3$, and $p=1/3$, what is the probability of ending at (say) $4$ after $10$ steps?

Answer 1

The standard way to do this is to take the transition probability matrix for the Markov chain and raise it to the appropriate power. Since the process starts at state zero its final state will be in the range $-N \leqslant X_n \leqslant N$ so you can do this using a transition probability matrix with $2N+1$ states. This matrix has the form:

$$\mathbf{P}_N = [p_{i,j} | -N \leqslant i,j \leqslant N],$$

where $p_{i,j}$ are the relevant transition probabilities. The relevant transition probabilities after $N$ steps are the elements of the matrix $\mathbb{P}_N^N$. If we start at state zero then the probability of being in state $x$ after $N$ steps is given by the element $\mathbb{P}_N^N[0, x]$.

Implementation in R: We can implement your problem in R by programming a function to compute the relevant probability for ending in state x starting from the zero state. For general application we can program a function transition.prob to compute this probability.$^\dagger$

transition.prob <- function(N, l, prob, x) {
  
  #Deal with special case where x is not in range
  if (!(x %in% (-N):N)) { return(0) }
  
  #Set truncated transition probability matrix for random walk
  P <- matrix(0, nrow = 2*N+1, ncol = 2*N+1)
  rownames(P) <- colnames(P) <- sprintf('S[%s]', (-N):N)
  for (i in (-N):(N-1)) { P[N+i+1, N+i+2] <- 0.5 }
  for (i in (-N+1):N)   { P[N+i+1, N+i]   <- 0.5 }
  
  #Set special transition probability
  if (l %in% (-N):N) {
    if (l != N)  { P[N+l+1, N+l+2] <- prob }
    if (l != -N) { P[N+l+1, N+l]   <- 1-prob } }
  
  #Find transition probability over N-steps
  PN <- diag(2*N+1)
  if (N >= 1) { 
  for (k in 1:N) { PN <- PN %*% P } }
  OUT <- unname(PN[N+1, N+x+1])
  
  #Return output
  OUT }

Using $N=10$, $l=3$, $p=\tfrac{1}{3}$ and $x=4$ we can use this function to compute the $N$-step transition probability. The output shows that the transition probability is $\mathbf{P}_N^N[0, 4] = 0.078125$.

transition.prob(N = 10, l = 3, prob = 1/3, x = 4)

[1] 0.078125

---

$^\dagger$ Note that the above code is illustrative only and is not the most efficient way to program for large values of N. For illustrative purposes I am using a fairly simple way to take matrix powers here and not trying to make it efficient using eigen-decomposition. The code also does not include checks to enforce sensible inputs.