In the previous installment we considered a simple coin tossing came and the probabilities of winning it. We used explicit listing of all possible outcomes to infer the resulting probabilities of winning or losing that game. In this installment we take a different approach: inferring the success probabilities for the same coin tossing game by observation of games being played.
Assume for a moment I offered the coin tossing game to somebody else. You arrived later at the scene as an observer. That is, you were never told the rules of the game. Still, it is of interest to you to infer the probabilities of winning or losing (you might join the game later on). Therefore we need to infer the ‘real’ probabilities from observing the outcomes of the game.
Inference of probabilities from observations is part of the mathematical field of inferential statistics. Each observation, or sample, will contribute to a more complete picture of the game being played. The more samples we collect the better will be our estimate of the real probabilities involved. We should, however, keep in mind that we will never be able to tell the probabilities with absolute certainty, because for any number of samples drawn, a coin tossing game, similar to the one described, can be formulated that contains an additional rule that with high probability hasn’t been observed by the collected samples.
To avoid playing the coin tossing game by hands and prevent us from tracking the outcomes by pencil and paper, we will fall back to simulating the game by a computer program. We have, however, to keep in mind that although computers are excellent at calculating deterministic things, they show weaknesses at indeterministic challenges such as generating randomness. We will use a so called pseudo random number generator in our simulation and accept the bias that it introduces.
The game introduced at the beginning of the previous installment is mapped to function in a ruby program that can be found in coin_tossing_engine.rb, which is part of the accompanying software package that can be downloaded from the links section at the bottom of this post.
# Play n-rounds of the coin tossing game def play(rounds) you = Account.new author = Account.new rounds.times do # Toss: 0 equals tail, 1 equals head sum = rand(2) + rand(2) case sum when 1 # Rule 2.2: One head, one tail you.transfer_to(author, 0.5) when 2 # Rule 2.1: Both heads author.transfer_to(you, 0.6) end end return you.amount, author.amount end
We start our observation by playing the game a hundred times and counting the number of times the author and his opponent wins. This is implemented in coin_tossing_count.rb. One possible outcome is
> ruby coin_tossing_count.rb 100 Playing 100 times Opponent wins 24 times Author wins 53 times
Note that, although played a hundred times, the above numbers do not sum to hundred. In 23 cases no one won (secretly we know that this is due to rule #3). To estimate the probabilities of the event ‘opponent wins’ we need to calculate the relative frequency of the event. This is defined by dividing the number of times the event is observed by the number of total observations which is 0.24.
The inferred probability of the event ‘opponent wins’ is 24% and the probability of the event ‘author wins’ is 53%.
The Binomial Test
What if I tell you that the opponent had bad luck, the game is fair and ask you to join the game. Would you? And if not, based on what judgement would you decline? What’s the certainty of dealing with an unfair game when in one observation the opponent wins in 24 of 100 times? These questions can be answered by the binomial test.
The binomial test is based on the binomial distribution. The binomial distribution is a discrete probability distribution for experiments with two possible output events (yes/no, success/failure, win/lose) where each event occurs with a certain probability. Remember the binomial coefficients from the previous installment? The binomial coefficients are a special case of the binomial distribution when the probability for both events is 0.5. The binomial distribution represents the probability of seeing exact, x, occurrences of success in an experiment of n trials and a success probability of p.
Below you can see a diagram of the probabilities of the binomial distribution of the observed game (in red) and the binomial distribution of a complete fair game (in blue). The diagram was cut at n=80 to make the diagram more readable.
Try looking up the probability of seeing 24 events of type “opponent wins” using the binomial distribution of the fair game. This will tell you beforehand that the coin tossing game cannot be fair.
The binomial test relies on the binomial distribution and works by formulating a null-hypothesis that can either be accepted or rejected based on the outcome of our test. In our case we hope to reject the following null-hypothesis “The coin tossing game is a fair game” based on our previous observations.
Using the binomial distribution, parametrized by n=100 and p=0.5 (its said to be fair), we can count the probability of seeing exactly 24 events of type ‘opponent wins’. We need to add the probability of seeing 23, 22, 21, 20, …, 0 such events. In this way we obtain a probability of seeing the observed result (24) or even less occurrences. Using binomial_test.rb we obtain
> ruby binomial_test.rb 100 0.5 24 Probability of null hypothesis 0.00000
In other words, with almost a hundred percent certainty we can reject the null-hypothesis and decline the offer to join the game. Even if we observed 40 wins by the opponent we would still need to be cautious
> ruby binomial_test.rb 100 0.5 40 Probability of null hypothesis is 0.02844
which means we would have a 97% chance of being right to reject the hypothesis that the coin game is fair.
- Ruby scripts containing expected loss calculation, game simulation, binomial distribution calculation for big numbers, the binomial test and much more.