I’ve been trying to write directly about some of the aspects of controlled experiments and A/B testing recently. An example is: A/B testing for engineers. The goal is to undo some of the cruft and convention that has built up over the years by both proper (but telegraphic) and improper (and insidious) use of citations.

I am hoping to work up to a new article on Wald’s Sequential Analysis, which itself fixes many of the issues of early inspection that plague controlled experiments. Along these lines I have been preparing some basic material on the Markov chain and stopping time analyses methods that underly the Wald system. In doing this I think I found something pretty neat.

First consider the following, horribly unfair, game. We pick an integer a ≥ 0 as our “game width.” We then start our game state at the integer 0. The game is stopped and “the player wins” if the state ever reaches -1. The game is alternatively stopped and “the house wins” if the game state reaches the non-negative integer a. While the game is not stopped, we repeatedly flip a fair (50/50) coin and add one to our state on “heads” and subtract one from our state on “tails.”

Below is an animation of several plays of this game (thank your Dr. Nina Zumel for making this in R!!!).

This looks great for “the player” (left hand side).

From “the house”‘s point of view: the game is unfair because “the player”‘s win condition (state = -1) is very close to the starting position. With some algebra one can even work out “the player” wins a given game with probability a / (a + 1), which favors “the player” greatly for a ≥ 2.

Now consider an unfair coin that is “heads, add 1” with probability 2/3 and “tails, subtract 1” with probability 1/3. Such a “coin” can be easily simulated with a standard 6-sided dice (assigning 1 through 4 to “heads, add 1” and 5 and 6 to “tails, subtract 1“).

The really cool result is: this game favors “the house” for any non-negative integer a.

Let’s take a look for the case a = 6.

That looked fair to pretty good for “the house” (right hand side).

With some work, one can show the probability of the house winning is: 1/(2 - 2**(-a)) per game.

The above sort of calculations are quite nasty, until one becomes familiar with the various tricks (picking what to track, and what to abstract out) for working with Markov chains. I hope to share this sort of familiarity in later work.

A cute way to implement the game would be for a bartender to place a bowl on the bar. The player places their keys in the bowl, and their friends all place their keys on the bar top. The player’s goal or win condition is getting all the keys back (or out of the bowl), the bar’s win condition is collecting all the keys in the bowl.

To repeat in detail. The player wins if the bowl if ever empty of keys, and the bar wins if the bar top is ever empty of keys. The moves are: with probability 2/3rds move a keyset from the bar to the bowl, else move a keyset from the bowl to the bar top. For all crowd sizes this favors the bar, even if players add keys to the bar top late to help their friend (though the bar/house advantage is slight).

Categories: Expository Writing Mathematics Tutorials Uncategorized

Tagged as: A/B testing Markov Chains probability sequential analysis

jmount

Data Scientist and trainer at Win Vector LLC. One of the authors of Practical Data Science with R.