Choosing One Stone Without Keeping Them All

The first promising stone goes into my pocket. Ten metres farther along, there’s another: flat, comfortable between finger and thumb, apparently willing to become airborne. By the next bend, I’ve inspected a dozen candidates and started negotiating with my pockets.

Suppose I allow myself exactly one stone, and want every suitable candidate along the walk to have an equal chance. Choosing the first favours the start of the beach. Replacing it whenever something catches my eye favours whatever I noticed last.

Reservoir sampling makes the decision without keeping the collection. Keep the first candidate. For candidate number n, replace the pocket’s occupant with probability 1/n.

Here’s the pocket in JavaScript; run it with Node.js:

const stones = ['slate', 'grey oval', 'flat pebble', 'dark disc'];
let pocket;
let seen = 0;
for (const stone of stones) {
  seen += 1;
  if (Math.random() < 1 / seen) {
    pocket = stone;
  }
}
console.log(`Chosen from ${seen}: ${pocket}`);

The array stands in for stones encountered one at a time. The selection itself retains only a count and one candidate, even if the shoreline supplies a million.

Save the Erlang version as shore.escript and run escript shore.escript:

#!/usr/bin/env escript
main(_) ->
    Stones = [slate, grey_oval, flat_pebble, dark_disc],
    io:format("Chosen: ~p~n", [choose(Stones, 0, undefined)]).
choose([], _, Pocket) -> Pocket;
choose([Stone | Rest], Seen, Pocket) ->
    N = Seen + 1,
    Next = case rand:uniform(N) of
        1 -> Stone;
        _ -> Pocket
    end,
    choose(Rest, N, Next).

JavaScript updates its pocket; Erlang passes the next pocket into a tail call. Both make the same bargain with chance.

Why is it fair? With four candidates, the fourth gets a 1/4 chance immediately. The third was selected with probability 1/3, then survives with probability 3/4: also 1/4. Earlier stones survive more replacement decisions, balancing their earlier opportunities.

Fairness doesn’t select the best skipping stone. I’d screen candidates for a comfortable grip and suitable shape first, then sample among those. Controlled spin and a low release still belong to the thrower. The algorithm merely settles which eligible stone gets its audition, using constant extra memory and no advance knowledge of where the walk ends.