Sam also initiated a tradition of entertaining the community, usually at holiday-time, with well-chosen puzzles, some of which I am still chewing over. Here's a message from Sam.
From: Sam Roweis
cc: "David J.C. MacKay"
Subject: coin puzzle
Here's a summer coin flipping puzzle to keep you occupied:
"You are given a biased coin, whose bias you do not know.
Using a sequence of independent flips of this coin, simulate
a sequence of independent flips of a fair (unbiased) coin."
The goal is to do this as efficiently as possible, in the
sense that you use as few flips (on average) of the biased
coin per simulated flip of the unbiased coin.
Here's an inefficient but correct way to get you thinking:
Flip the biased coin twice. If it comes up HH or TT, try again.
If it comes up HT, output H.
If it comes up TH, output T.
Of course if the bias is near 0 or 1 you will be rejecting a lot...
Sam, you were a wonderful, wonderful colleague and friend. Life was always filled with fun and humour and interest and intensity when you were around. We will miss you terribly, but you are not gone - you are still with us now, in the memes with which you have infected us.