Introduction

This post shows how a biased random walk can be implemented in OCaml as a recursive definition. Consider a walker whoes initial position is n where n is positive integer will go forward 1 step with probability 1/3 and will go backward 1 step with probability 2/3.

What we are interested in here is what is the number of steps that the walker needs to take to go from the position n to 0. Obviously, in the worst-case this number of steps is infinite. However, we can show that the probability that this situation happens is 0, e.g., it is 1/3^m where m go to infinity. We say that this random walk algorithm is almost sure termination.

Thus the more interesting question is what is the expected number of steps that the walker needs to take to go from n to 0. If we call T(n) is the expected number of steps to go from n to 0, then we have the following recursion relation T(n) = 1 + 1/3T(n+1) + 2/3T(n-1). The solution of this relation is T(n) = 3.n. However, the recursion relation solving is not easy problem. If we use our automatic analyzer, Absynth, that can infer the upper bound on this expected value, the we get the same tightest bound 3.max(0,n).

Implementation

let rec biased_rw n counter =
   let () = assert (n >= 0) in match n with
   | 0 -> (0, counter)
   | _ -> 
    let r = Random.int 100 in
    (* encode the probability 2/3 *)
    if (r < 67) then 
        biased_rw (n-1) (counter+1) 
    else 
        biased_rw (n+1) (counter+1)

(* testing function *)
let test nr f n =
   let rt = ref 0 in
   for i = 1 to nr do
      let (_,cost) = f n 0 in
      rt := (!rt) + cost
   done; 
   (float_of_int (!rt)) /. (float_of_int nr)

The following are the average values of counter when we run biased_rw for 10000 times.

# test 10000 biased_rw 10;;
- : float = 29.472