Es­ti­mat­ing the Weights of Bi­ased Coins

Sup­pose we flip a coin four times. If the coin lands on head­s, we win a dol­lar. If the coin lands on tail­s, we lose a dol­lar. Af­ter four toss­es of the coin, the best pos­si­ble out­come is a win­ning to­tal of four dol­lars. The worst pos­si­ble out­come is a loss of four dol­lars. Let’s as­sume the coin is a bi­ased coin. Fur­ther­more, let’s al­so as­sume a dif­fer­ent bi­ased coin is used on each flip de­pend­ing on the to­tal amount won or lost since the be­gin­ning of the game. How can we de­ter­mine the bias of each coin giv­en a prob­a­bil­i­ty mass func­tion of the ex­pect­ed out­come?

In this post, I want to ex­plore a tech­nique that can be used to an­swer this ques­tion. I am hop­ing this mod­el can be ex­pand­ed to give some bet­ter in­sights in­to ob­ser­va­tions made in my pre­vi­ous posts re­gard­ing the dis­tri­b­u­tion of price fluc­tu­a­tions and the strange be­hav­ior of the Chi­nese yuan.

Markov Mod­el

The afore­men­tioned coin toss game can be mod­eled as a Markov chain. The game starts in the ini­tial ze­ro state. Each toss of the coin de­ter­mines whether the sys­tem tran­si­tions to a high­er state or a low­er state. If the coin lands on head­s, we move to a high­er state. If the coin lands on tail­s, we move to a low­er state. Each state de­ter­mines the weight of the bi­ased coin used in the next toss. Here is a graph­i­cal rep­re­sen­ta­tion of the Markov mod­el:

In this mod­el, the coin in the ze­ro state is al­ways a fair coin. A fair coin will land on heads 50% of the time and tails 50% of the time. Ad­di­tion­al­ly, this mod­el is al­so sym­met­ri­cal. The bi­ased coins in the neg­a­tive states are weight­ed in­verse­ly to the bi­ased coins in the cor­re­spond­ing pos­i­tive states. The di­a­gram above can al­ter­nate­ly be de­pict­ed as fol­lows:

Note that the pos­i­tive and neg­a­tive fourth states can on­ly be ter­mi­nal states, so there is nev­er a tran­si­tion out of them. Al­so, keep in mind that the Markov mod­el does not nec­es­sar­i­ly have to be sym­met­ri­cal. I chose to make it sym­met­ri­cal to re­duce the num­ber of vari­ables and to sim­pli­fy the mod­el.

Monte Car­lo Sim­u­la­tion

If we know the weights of the bi­ased coin­s, we can use a Monte Car­lo sim­u­la­tion to es­ti­mate the ex­pect­ed out­come of the coin toss game. Sim­ply put, we can run a mil­lion sim­u­lat­ed rounds of the coin toss game, with four flips in each round, and ob­serve the dis­tri­b­u­tion of pos­si­ble out­comes. Sup­pose each coin is weight­ed fair­ly:

The val­ues above can be pre­sent­ed vi­su­al­ly on a chart like this:

In a Monte Car­lo sim­u­la­tion, we use a ran­dom num­ber gen­er­a­tor to sim­u­late the out­come of each coin toss. We record the ter­mi­nal state af­ter each round of four coin toss­es. Af­ter run­ning one mil­lion rounds of the coin toss game, the dis­tri­b­u­tion of ter­mi­nal states looks like this:

This gives us an es­ti­mate of the ex­pect­ed out­come af­ter four toss­es of the coin. No­tice that on­ly even ter­mi­nal states are pos­si­ble when there is an even num­ber of coin toss­es. Odd­-num­bered ter­mi­nal states would on­ly be pos­si­ble if there were an odd num­ber of toss­es. It is al­so worth not­ing that the chart above close­ly ap­prox­i­mates a bi­no­mi­al dis­tri­b­u­tion. Here is a break­down of the ex­pec­ta­tion for each in­di­vid­ual coin toss se­quence:

The val­ues are all rough­ly the same, in­di­cat­ing that all pos­si­ble coin toss se­quences have about an equal prob­a­bil­i­ty of be­ing ob­served in any giv­en round of the coin toss game, as­sum­ing we’re al­ways us­ing fair coin­s. The Monte Car­lo sim­u­la­tion is a brute force ap­proach that yields fair­ly ac­cu­rate re­sult­s. We can ar­rive at more pre­cise val­ues by find­ing the re­sults an­a­lyt­i­cal­ly.

An­a­lyt­i­cal Eval­u­a­tion

With four toss­es of the coin, there are six­teen pos­si­ble coin toss se­quences and five unique ter­mi­nal states. The fol­low­ing ta­ble lists every pos­si­ble coin toss se­quence along with its ter­mi­nal state and a for­mu­la for the prob­a­bil­i­ty of each com­bi­na­tion:

Keep in mind that the mod­el is sym­met­ri­cal. We can use the fol­low­ing no­ta­tion to rep­re­sent the prob­a­bil­i­ty of land­ing on each of the five pos­si­ble ter­mi­nal states:

Since the mod­el is sym­met­ri­cal, the chance of end­ing up in any giv­en pos­i­tive ter­mi­nal state is equal to the prob­a­bil­i­ty of end­ing up in the cor­re­spond­ing neg­a­tive ter­mi­nal state. The equa­tions above can be rewrit­ten as fol­lows:

Plug­ging in the prob­a­bil­i­ty for­mu­la for each of the coin toss com­bi­na­tion­s, the equa­tions above can be ex­pressed like this:

By de­f­i­n­i­tion, since our mod­el is a sym­met­ri­cal one, we know that the coin used in the ze­ro state is al­ways a fair coin:

Sub­sti­tut­ing the val­ue above for the weight of the coin at the ze­ro state and then sim­pli­fy­ing, we can ar­rive at the fol­low­ing set of equa­tion­s:

This set of equa­tions rep­re­sents the re­la­tion­ship be­tween the weights of the bi­ased coins and the ex­pect­ed out­come of the coin toss game. If we know the weights of the coin­s, we can com­pute the prob­a­bil­i­ty mass func­tion of the ex­pect­ed out­come af­ter four toss­es of the coin. To il­lus­trate, let’s as­sume each coin is weight­ed fair­ly:

This is the same sce­nario we start­ed with when do­ing the Monte Car­lo sim­u­la­tion above, so we can ex­pect to get the same or sim­i­lar re­sult­s. Plug­ging in the num­ber­s, here are the com­put­ed re­sult­s:

These re­sults can be pre­sent­ed vi­su­al­ly with the fol­low­ing chart:

These are the ex­act fig­ures that were es­ti­mat­ed by the Monte Car­lo sim­u­la­tion demon­strat­ed in the pre­vi­ous sec­tion. This is a bi­no­mi­al dis­tri­b­u­tion. The com­put­ed ex­pec­ta­tion of each in­di­vid­ual coin toss se­quence is shown be­low:

This con­firms the re­sult es­ti­mat­ed by the Monte Car­lo sim­u­la­tion as well. When al­ways us­ing a fair coin, each of the six­teen com­bi­na­tions of coin toss se­quences has an equal prob­a­bil­i­ty of be­ing ob­served.

Many Pos­si­ble So­lu­tions

We know from the pre­vi­ous sec­tions that if all the coins are fair­ly weight­ed, then the ex­pect­ed out­come af­ter four coin toss­es is a bi­no­mi­al dis­tri­b­u­tion. But what if we start with a bi­no­mi­al dis­tri­b­u­tion as the ex­pect­ed out­come and work back­wards to find the weights of the coin­s? We al­ready know that hav­ing fair­ly weight­ed coins is one pos­si­ble so­lu­tion. But can there be oth­er pos­si­ble so­lu­tions as well?

Let’s in­tro­duce the fol­low­ing no­ta­tion. We have seen a graph­i­cal il­lus­tra­tion of what a bi­no­mi­al dis­tri­b­u­tion looks like in the pre­vi­ous sec­tion. Here is the sym­bol­ic form of the prob­a­bil­i­ty mass func­tion for a bi­no­mi­al dis­tri­b­u­tion:

For suc­cinct­ness, I am us­ing an al­ter­nate ze­ro-based in­dex to rep­re­sent the ter­mi­nal states. The fol­low­ing re­la­tion­ship hold­s:

Since there are on­ly four coin toss­es in the mod­el we’re us­ing here, we can sub­sti­tute:

Now re­call the fol­low­ing from the pre­vi­ous sec­tion:

We can sub­sti­tute the al­ter­nate no­ta­tion and rewrite it like this:

Plug­ging in the num­bers and do­ing the math, we can com­pute the fol­low­ing val­ues to rep­re­sent the bi­no­mi­al dis­tri­b­u­tion:

This rep­re­sents the ex­pect­ed out­come af­ter four coin toss­es. Now we want to fig­ure out what weights of the bi­ased coins will give us this ex­pec­ta­tion. Based on the analy­sis in the pre­vi­ous sec­tion, we al­ready know that play­ing the coin toss game with fair­ly weight­ed coins will give us our de­sired re­sult:

How­ev­er, this is not the on­ly so­lu­tion. As it turns out, there is an en­tire range of pos­si­ble so­lu­tions that re­sult in an ex­pect­ed out­come that takes the form of a bi­no­mi­al dis­tri­b­u­tion. Con­sid­er the fol­low­ing equa­tions de­rived in the pre­vi­ous sec­tion:

Any so­lu­tion that fits these equa­tions is a valid so­lu­tion pro­vid­ed that the fol­low­ing con­straints are met:

The con­straints are nec­es­sary be­cause a coin can­not land on heads less than 0% of the time, nor can it land on heads more than 100% of the time. Us­ing the equa­tions above, we can re­arrange them and solve for the weights of the bi­ased coins in the +2 and +3 states in terms of the weight of the coin in the +1 state:

Any val­ue for the weight of the bi­ased coin in the +1 state can be used pro­vid­ed that the afore­men­tioned con­straints are met for the weights of all coin­s. There is a range of pos­si­ble val­ues for the coin in the +1 state. This range has a low­er and up­per bound. We can de­ter­mine the low­er bound for the weight of the coin in the +1 state by set­ting the weight of the coin in the +2 state to the max­i­mum val­ue of one:

With the weights of the coin in the +2 state held con­stant at one, we can solve for the weights of the coins in the +1 and + 3 states:

Plug­ging the val­ues in­to the equa­tion­s:

Here are the weights of all the coins when the weight of the coin in the +1 state is at the low­er bound of the range:

Us­ing the above weight­s, we can eval­u­ate the ex­pect­ed out­come of the coin toss game and show that it in­deed does re­sult in a bi­no­mi­al dis­tri­b­u­tion:

This is the same ex­pect­ed out­come we would get if all the coins were fair coin­s. How­ev­er, con­sid­er the ex­pec­ta­tion of each in­di­vid­ual coin toss se­quence:

Not all coin toss com­bi­na­tions are equal. Some have a high­er prob­a­bil­i­ty of be­ing ob­served than oth­ers when the bi­ased coins are weight­ed un­fair­ly. We can ob­serve a sim­i­lar phe­nom­enon when the weights of the coins are at the op­po­site ex­treme of the range of pos­si­ble val­ues. Sup­pose the weight of the coin in the +3 state is set to the max­i­mum val­ue of one:

With this held con­stan­t, we can find the up­per bound for the weight of the coin in the +1 state and the low­est val­ue for the weight of the coin in the +2 state:

Plug­ging the val­ues in­to the equa­tion­s:

Here are the weights of all the coins when the weight of the coin in the +1 state is at the up­per bound of the range:

Again, us­ing the above weight­s, we can eval­u­ate the ex­pect­ed out­come of the coin toss game and show that it in­deed does re­sult in a bi­no­mi­al dis­tri­b­u­tion:

Like be­fore, this is the same ex­pect­ed out­come we would get if all the coins were fair coin­s. But in this case, we get a dif­fer­ent set of ex­pec­ta­tions for each coin toss se­quence:

The ex­am­ples il­lus­trat­ed in this sec­tion demon­strate two ex­tremes of a range of pos­si­ble val­ues for the weights of bi­ased coin­s. In both ex­am­ples, these val­ues yield an ex­pect­ed out­come in the shape of a bi­no­mi­al dis­tri­b­u­tion when play­ing the coin toss game with four toss­es. And this is the same out­come we can ex­pect when play­ing the game with fair coin­s. Of course, there are many oth­er pos­si­ble val­ues that will give us a bi­no­mi­al dis­tri­b­u­tion as well.

Hill Climb­ing Al­go­rithm

What if the ex­pect­ed out­come is not a bi­no­mi­al dis­tri­b­u­tion? Sup­pose we ob­serve many rounds of the coin toss game and de­ter­mine the ex­pect­ed out­come is a tri­an­gle dis­tri­b­u­tion in­stead. We know the coins are bi­ased, but how can we es­ti­mate the weights of the bi­ased coin­s? Con­sid­er the sym­bol­ic form of a tri­an­gle dis­tri­b­u­tion:

Us­ing the tech­niques de­scribed in the pre­vi­ous sec­tion, we can com­pute the fol­low­ing val­ues for the tri­an­gle dis­tri­b­u­tion:

We can al­so rep­re­sent this vi­su­al­ly with the fol­low­ing chart:

And us­ing the tech­niques de­scribed in the pre­vi­ous sec­tion, we can al­so com­pute the low­er and up­per bounds of the range of pos­si­ble val­ues that will yield a tri­an­gle dis­tri­b­u­tion. The val­ues are il­lus­trat­ed be­low:

While the weights il­lus­trat­ed above are valid to pro­duce a tri­an­gle dis­tri­b­u­tion, they might not be the best es­ti­mates to mod­el a re­al-world sce­nar­i­o. A coin that al­ways lands on heads or al­ways lands on tail­s, for ex­am­ple, might not be the most ac­cu­rate mod­el of re­al­i­ty. It might be bet­ter to come up with an in­ter­me­di­ate so­lu­tion that lies some­where in be­tween the two ex­tremes.

In­stead of try­ing to find an in­ter­me­di­ate so­lu­tion an­a­lyt­i­cal­ly, we can try to find one in­cre­men­tal­ly. We can start with an ini­tial guess some­where in the mid­dle and then in­cre­men­tal­ly try to im­prove our ini­tial es­ti­mate. We can re­peat this process un­til we con­verge on a valid so­lu­tion that fits the tri­an­gle dis­tri­b­u­tion. This would ef­fec­tive­ly be a type of hill climb­ing al­go­rith­m.

Sup­pose we start with an ini­tial guess of all fair­ly weight­ed coin­s. We can ran­dom­ly pick one of the es­ti­mat­ed weight­s, ad­just it up or down by a small amoun­t, and then mea­sure whether or not the ad­just­ment brings the com­put­ed out­come clos­er to that of a tri­an­gle dis­tri­b­u­tion. If the ad­just­ment is an im­prove­men­t, then we ac­cept it. If the ad­just­ment is not an im­prove­men­t, then we re­ject it and re­vert back to the pre­vi­ous val­ue. We can re­peat this process many times. Here is an il­lus­tra­tion of this al­go­rith­m:

This al­go­rithm it­er­ates one mil­lion times, ac­cept­ing or re­ject­ing a pro­posed in­cre­ment to one of the es­ti­mat­ed weight­s. It’s ba­si­cal­ly a tri­al and er­ror process. Ap­ply­ing this al­go­rithm gives us the fol­low­ing es­ti­mates for the weights of the bi­ased coin­s:

Play­ing the coin toss game with the above weights for the bi­ased coins will yield an ex­pect­ed out­come that is very close to the tri­an­gle dis­tri­b­u­tion. This is not an ex­act so­lu­tion, but it is very close. This is al­so not the on­ly so­lu­tion. One of the idio­syn­crasies of this ap­proach is that the re­sult can be dif­fer­ent de­pend­ing on what val­ues are used for the ini­tial guess. Re­mem­ber, there is a range of pos­si­ble so­lu­tion­s, all equal­ly valid.

The fol­low­ing sec­tions cat­a­log the ap­pli­ca­tion of this es­ti­ma­tion process to a few vari­a­tions of a dis­crete dou­ble ex­po­nen­tial dis­tri­b­u­tion in­stead of a tri­an­gle dis­tri­b­u­tion.

Ex­po­nen­tial Dis­tri­b­u­tion, Pa­ra­me­ter = 0.5

Sup­pose we mod­el the ex­pect­ed out­come as a dis­crete dou­ble ex­po­nen­tial dis­tri­b­u­tion such that the ex­pec­ta­tion of the game fin­ish­ing on a giv­en ter­mi­nal state is 0.5 times that of the ter­mi­nal state with the next high­est ex­pec­ta­tion. Here is the prob­a­bil­i­ty mass func­tion:

Here is a graph­i­cal rep­re­sen­ta­tion of the prob­a­bil­i­ty mass func­tion above:

The fol­low­ing charts are the low­er and up­per bounds of the range of pos­si­ble val­ues for weights that re­sult in the ex­pect­ed out­come de­fined above:

Here are the es­ti­mat­ed weights us­ing the hill climb­ing al­go­rith­m:

The above val­ues were es­ti­mat­ed start­ing with an ini­tial guess of fair­ly weight­ed coins and run­ning the hill climb­ing al­go­rithm through one mil­lion it­er­a­tions.

Ex­po­nen­tial Dis­tri­b­u­tion, Pa­ra­me­ter = 0.4

Sup­pose we mod­el the ex­pect­ed out­come as a dis­crete dou­ble ex­po­nen­tial dis­tri­b­u­tion such that the ex­pec­ta­tion of the game fin­ish­ing on a giv­en ter­mi­nal state is 0.4 times that of the ter­mi­nal state with the next high­est ex­pec­ta­tion. Here is the prob­a­bil­i­ty mass func­tion:

Here is a graph­i­cal rep­re­sen­ta­tion of the prob­a­bil­i­ty mass func­tion above:

The fol­low­ing charts are the low­er and up­per bounds of the range of pos­si­ble val­ues for weights that re­sult in the ex­pect­ed out­come de­fined above:

Here are the es­ti­mat­ed weights us­ing the hill climb­ing al­go­rith­m:

The above val­ues were es­ti­mat­ed start­ing with an ini­tial guess of fair­ly weight­ed coins and run­ning the hill climb­ing al­go­rithm through one mil­lion it­er­a­tions.

Ex­po­nen­tial Dis­tri­b­u­tion, Pa­ra­me­ter = 0.3

Sup­pose we mod­el the ex­pect­ed out­come as a dis­crete dou­ble ex­po­nen­tial dis­tri­b­u­tion such that the ex­pec­ta­tion of the game fin­ish­ing on a giv­en ter­mi­nal state is 0.3 times that of the ter­mi­nal state with the next high­est ex­pec­ta­tion. Here is the prob­a­bil­i­ty mass func­tion:

Here is a graph­i­cal rep­re­sen­ta­tion of the prob­a­bil­i­ty mass func­tion above:

The fol­low­ing charts are the low­er and up­per bounds of the range of pos­si­ble val­ues for weights that re­sult in the ex­pect­ed out­come de­fined above:

Here are the es­ti­mat­ed weights us­ing the hill climb­ing al­go­rith­m:

The above val­ues were es­ti­mat­ed start­ing with an ini­tial guess of fair­ly weight­ed coins and run­ning the hill climb­ing al­go­rithm through one mil­lion it­er­a­tions.

Next Steps

I want to ex­plore this es­ti­ma­tion tech­nique in more depth. I would like to see what the es­ti­mat­ed weights look like when the coin toss game is played with many coin toss­es per round in­stead of just four. Per­haps this will be the top­ic of a lat­er post.

I would al­so like to come up with a more mean­ing­ful cost func­tion for the hill climb­ing al­go­rith­m, one that would give pref­er­ence to valid val­ues clos­er to the mid­dle of the range of pos­si­ble val­ues. With the im­ple­men­ta­tion pre­sent­ed in this post, there is a plateau of valid val­ues that can be es­ti­mat­ed. The val­ue that it con­verges to is high­ly de­pen­dent on the ini­tial guess. Hav­ing a bet­ter cost func­tion would al­low the al­go­rithm to con­verge to the same so­lu­tion re­gard­less of the start­ing point. I’m not sure yet how to do this.

Ac­com­pa­ny­ing source code is avail­able on GitHub.