By: Júlio Hoffimann
Re-posted from: https://juliohm.github.io/science/coin-flipping/
In this post, I would like to contrast two ways of thinking about a coin flip process—one of which is very intuitive and one of which can be very useful for certain applications. This insight is inspired on a stochastic modeling class by Ramesh Johari.
Discrete-time coin flip process
Suppose that I ask you to simulate a sequence of i.i.d. (independent and identically distributed) coin flips in a computer where the probability of flipping a coin and observing a head () is and the probability of flipping a coin and observing a tail () is :
, , , , , , ,
There are at least two ways of doing this:
Solution A — popular solution
The most popular solution by far is to go to your favorite programming language (e.g. Julia :blush:) and sample a sequence of :
using Distributions
p = .5 # probability of head
N = 100 # number of coin flips
coin_flips = rand(Bernoulli(p), N)
# 1, 0, 0, 0, 1, 1, ...
Solution B — not so popular solution
Think of a head (or ) as a successful coin flip. For example, you earn $1 whenever the head comes up and nothing otherwise. Keep track of the times when you had a successful outcome
Now is the trick. In a coin flip process, the interarrival times between successes are i.i.d. . Instead of simulating the coin flips directly, simulate the times at which a head will occur:
using Distributions
p = .5 # probability of head
N = 100 # number of coin flips
T = rand(Geometric(p), N)
head_times = cumsum(T+1)
# construct process in a single shot
coin_flips = zeros(N)
head_times = head_times[head_times ≤ N]
coin_flips[head_times] = 1
# 1, 0, 1, 1, 0, 0, ...
Why is solution B relevant?
In other words, why would you care about a solution that is more verbose and somewhat less intuitive?
Imagine that the probability of success is extremely low. Would you like your computer spending hours generating tails (or ) before it can generate a head? For some applications, this is a critical question.
More than that, sometimes Solution A is not available…
Continuous-time coin flip process
The Poisson process is the equivalent of the coin flip process in continuous-time. Imagine that you divide real time (a real number) into small intervals of equal lenght :
If a coin is to be flipped at each of these marks in the limit when , then Solution A is not available! There are uncountably many coin flips in the interval .
However, simulating this process in a computer is possible with Solution B. For a Poisson process with success rate , the interarrival times are i.i.d. .