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