Random Walks

We can think of a function p of type int -> int as a path generator in the (infinite) complete graph on integers. Given a starting value start, the path of length 3 generated by p starting at start is

[start; p start; p (p start); p (p (p start))]

For example, the function fun x -> x + 2 generates the length 5 path [0;2;4;6;8;10] starting at 0.

We can analogously think of a function r of the similar type int -> int list as a random walk generator in the same graph. Rather than taking a single step from x to r x, we choose one of the vertices in r x uniformly at random.

For example, the classic drunkard's walk can be represented by the function

let drunkard x = [x + 1; x - 1]

Taking a random walk for a number of steps n from a starting point start defines a distribution over the vertices in our graph, telling us the probability of being at each vertex after taking n steps from start.

type rat = {
  num : int;
  denom : int;
}

type distr = (int * rat) list

A (discrete) probability distribution is a collection of values paired with rational numbers, representing the probability of each value. If a value does not appear in this list, then it has probability 0. We maintain that:

• the sum of the probabilities is 1;
• there is at most one pair (v, prob) for any value v;
• the values are in increasing order;
• the rational numbers in the distribution are in reduced form.

Implement the function

val random_walk : (int -> int list) -> int -> int -> distr

so that the distribution random_walk walk start num_steps is the one defined over vertices of the complete graph on integers after taking a num_steps-length random walk starting at start. Specifically, if the probability of being at vertex \(n\) is \(p\), then (n, p) should appear in the resulting distribution.

let drunkard x = [x + 1; x - 1]
let _ = assert (random_walk drunkard 0 0 = [(0, {num=1;denom=1})])
let _ = assert (random_walk drunkard 0 1 =
    [(-1, {num=1;denom=2}); (1, {num=1;denom=2})])
let _ = assert (random_walk drunkard 0 2 =
    [(-2, {num=1;denom=4}); (0, {num=1;denom=2}); (2, {num=1;denom=4})])