Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Distinguishing A Biased Coin From a Fair Coin

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

You have with two coins: one is fair and the other has a biased chance p > 1 2 of coming up heads. Unfortunately, you don’t know which is which. How can you determine which is the biased coin? What do you need to know?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. How to numerically compute the probability of a majority of heads in a sequence of paired coin flips of a biased coin and a fair coin.
  2. How to numerically compute the probability of statistical evidence of a biased coin in a sequence of paired coin flips of a biased coin and a fair coin.
  3. Bayesian analysis using likelihood ratios as statistical evidence of a biased coin in a sequence of paired coin flips of a biased coin and a fair coin.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. A sequence of independent Bernoulli trials with probability 12 of success on each trial is metaphorically called a fair coin. One for which the probability is not 12 is a biased or unfair coin.
  2. Suppose a fair coin 1 is in the left hand and a biased coin 2 is in the right hand. The coin in the left hand comes up heads kL times and the coin in the right hand comes up heads kR times. Let k = (kL,kR) and call this scenario 𝜃L. The likelihood of this scenario occurring is
    Q(k|𝜃L) = B(kL,n,p1)B(kR,n,p2).

  3. If fair coin 1 is in the right hand and biased coin 2 is in the left hand then call this scenario 𝜃R. The likelihood ratio is
    Q(k|𝜃L) Q(k|𝜃R).

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

A Simple Probability Problem

This problem serves as a warmup for the more detailed calculations below.

You have two coins. One is fair with H = 1 2. The other coin is biased with H = 2 3. First you toss one of the coins once, resulting in heads. Then you toss the other coin three times, resulting in two heads. Which coin is more likely to be the biased coin, the first or the second?

Joint Probability Solution

Assuming tossing the biased coin once and tossing the fair coin three times the probability of observing the outcome is

2 3 3 2 1 2 2 1 2 1 = 2 8.

On the other hand, assuming tossing the fair coin once and tossing the biased coin three times the probability of observing the given outcome is

1 2 3 2 2 3 2 1 3 1 = 2 9.

This means it was more likely that is was the biased coin tossed once while tossing the fair coin three times.

Using Bayes Theorem

Take a uniform prior, that is, assume that the first coin is equally likely to be either of the two coins. Let K = (k1,k2) denote the observation, and B the event that the first coin is biased. Then

B = BC = 1 2.

The conditional probabilities are

K|B = 2 3 3 2 1 2 2 1 2 1 = 2 8

and

K|BC = 1 2 3 2 2 3 2 1 3 1 = 2 9.

From Bayes Theorem,

B|K = K|B B K|B B + K|BC BC = 28 28 + 29 = 9 17 > 1 2.

Using Likelihood Ratios

Take even prior odds to be even, that is, assume that the first coin is equally likely to be either of the two coins. Let K = (k1,k2) be the observed outcomes. The likelihood ratio is

L(K) = E|B E|BC = 2 3 1 2 3 1 2 2 3 2 1 3 1 = 224 454 = 9 8.

Then the odds in favor of the first coin being biased and the second coin being fair are 9 : 8, so the probability is 9 8+9 = 9 17.

A Larger Problem

The following problem appeared in the FiveThirtyEight.com weekly Riddler puzzle column on September 29, 2017:

On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips you must flip both coins at once, one with each hand would you need to give yourself a 95 percent chance of correctly identifying the doctored coin?

Extra credit: What if, instead of 60 percent, the doctored coin came up heads some percent p of the time? How does that affect the speed with which you can correctly detect it?

This problem appeared in a paper “What’s Past is Not Prologue” by James White, Jeff Rosenbluth, and Victor Haghani. In turn, a problem posed in a paper “Good and bad properties of the Kelly criterion” by MacLean, Thorp and Ziemba inspired the problem by White, Rosenbluth, and Haghani.

Solving this problem requires some interpretation and computation.

Probability of a Majority of Heads

In any fixed number of simultaneous flips, there is always a chance that the fair coin will have more heads than the biased coin. But the Weak Law of Large Numbers says that the probability that the biased coin will have a majority of heads increases to 1 as the number of flips increases. One way to determine which is the biased coin is to choose the coin which has a majority of heads. The authors White, Rosenbluth, and Haghani want to calculate how many paired flips of 2 coins, one biased and one fair, we must observe in order to be 95% confident that the coin with more heads is the biased coin.

Assuming independence, since each coin has a binomial distribution the joint probability mass distribution after n flips is the product of the individual binomial probability mass distributions. Denote by Q(n; j,k) the probability of j heads for the fair coin and k heads for the biased in n flips. Use p for the probability of heads of the biased coin and 1 2 for the probability of heads for the fair coin. Then

Q(n; j,k) = n j 1 2 j 1 2 nj n kpk(1 p)nk.

Then summing over values where j < k gives the probability that the biased coin has more heads than the fair coin in n flips

j < k = 1 2n kn j<kn j n kpk(1 p)nk.

This sum has no closed formula evaluation so calculation is necessary. First create two vectors of length n + 1 with the binomial distribution on 0 to n with probability 1 2 for the fair coin and with probability p for the biased coin. Then using the outer product of these two vectors create the bivariate binomial distribution for the two coins. This will be an (n + 1) × (n + 1) matrix. The element in row i and column j is the product of the binomial probability of i 1 heads for the fair coin and the binomial probability of j 1 heads for the biased coin. The sum is over column indices strictly greater than the row indices. To create the sum, set the lower triangular part of the matrix and the diagonal of the matrix to 0 and use the sum command to sum all entries of the matrix. This seems to be efficient, even for values of n up to 200. To find the minimal value of n for which this probability is greater than 0.95 use binary search in n over a reasonable interval.

It might seem possible to use a bivariate normal approximation of the bivariate binomial distribution to calculate the probability. Although approximation of the bivariate binomial distribution with a bivariate normal distribution is possible, the double integration of the bivariate normal with a non-zero covariance would be over a region of the form y > x 𝜖. The R language has no direct way to calculate the integral over a region of this form, so it is actually easier to calculate with the bivariate binomial distribution.

The result is that it takes 143 flips of the two coins for the probability to be greater than 0.95 for the 0.6 biased coin to have more heads than the fair coin.

The same analysis for various probabilities of heads p for the biased coin and for values 0.95, 0.9 and 0.75 of certainty is in Figure 1. The number of flips required decreases as the bias p increases, as expected. The number of flips required also decreases as the certainty decreases.


Majority binary search results

PIC

Figure 1: The number of flips N required to get a majority of heads with certainty 0.95 (black), 0.9 (red) and 0.75 (blue).

Using the Central Limit Theorem

Assume that the biased coin is in the left hand. Let Lj be the result of left-hand coin flip j, knowing it is biased so Lj = Head = 1 with probability 0.6, Lj = Tail = 0 with probability 0.4. Let Rj be the result of right-hand coin flip j, knowing it is fair so Rj = Head = 1 with probability 0.5, Rj = Tail = 0 with probability 0.5. Let Xj = Lj Rj. This is a trinomial random variable with Xj = 1 with probability 15 = 0.2, Xj = 0 with probability 12 = 0.5, Xj = 1 with probability 310 = 0.3.

Consider the statistics of Xj,

𝔼 Xj = (1) (0.2) + 0 (0.5) + (+1) (0.3) = 0.1, Var Xj = (1)2 (0.2) + (0)2 (0.5) + (+1)2 (0.3) (0.1)2 = 0.49, σ[Xj] = 0.7.

Let Sn = 1 n j=1nX j be the sample mean. The distribution of Sn is on 1 to 1 by increments of 1n for a total of 2n + 1 points with

𝔼 Sn = 0.1, Var Sn = 0.49n, by independence,  σ[Sn] = 0.7n.

Thus the distribution of Sn clusters around 110 with standard deviation 7(10n). If the biased coin is in the right hand, the distribution of Sn clusters around 110 with standard deviation 7(10n).The goal is find a number of flips such that with high probability the sample mean Sn is closer to the theoretical mean 0.1 (when the biased coin is in the left hand) than the value 0.1 (the theoretical mean coming from the situation with the biased coin in the right hand). Take “the sample mean closer to 0.1 than 0.1” to mean that Sn is closer to 0.1 than the distance to the midpoint 0 between the two means. Precisely, the goal is to find n so that Sn 0.1 > 0.1 0.95. This is the same event as Sn > 0 = Ln Rn > 0 = Ln > Rn which is the same criterion as having the majority of heads above.

Expressing the precise distribution of Sn analytically is difficult. So instead, use a numerical calculation of the distribution. To numerically calculate the distribution of the sample mean Sn, use the R package distr and specifically the function convpow that takes the n-fold convolution power of a distribution to create the distribution of the n-fold sum of a random variable. Note that mathematically the support of the distribution of, for instance S100, would be from 1 to 1, with 201 points. However, the actual calculated distribution support of, for instance, S100, is 111 points from 46 to 64. The reason is that convpow ignores points with probability less than 1016 and so these points are not included in the domain. So use match(0, (support(D100))) to find the index of 0. This turns out to be index 47. So summing the distribution over indices from 47 + 1 to 111 gives the probability that the random variable Sn > 0. Searching for a value of n large enough that the probability exceeds 0.95 gives the required number of flips. From some experimentation, the numerical support of the distribution is positive for n 150, that is, Sn 0 = 1 for n 150. That means that the numerical search should start from a high of 150.

Using this algorithm, the necessary number of flips to distinguish a biased coin with a probability of heads 0.6 from a fair coin with a certainty level of 0.95 is 143. The same analysis for various probabilities of heads p for the biased coin and for values 0.95, 0.9 and 0.75 of certainty is in Figure 2. The number of flips required decreases as the bias increases as expected. The number of flips required also decreases to 5 for certainty 0.95, 4 for certainty 0.9 and 3 for certainty 0.75.


Statistical bianry search results


Figure 2: The number of flips N required to statistically distinguish a coin with probability p from a fair coin with 0.95 (black), 0.9 (red) and 0.75 (blue).

Connections between the Two Calculations


Connection between the two calculations

Figure 3: The support of the bivariate binomial and the calculation of the multinomial distribution for n = 10.

The calculation of the probabilities uses fundamentally the same information, as the diagram in Figure 3 for the case n = 10 illustrates. The 11 × 11 array of dots represents the support of the bivariate binomial distribution as a matrix, with rows from 0 to 11 for the number of heads from the fair coin and columns 0 to 11 for number of heads for the biased coin.

The probability that the majority of flips is from the biased coin is the sum of the probabilities in the strict upper triangle of the support of the bivariate distribution. The shaded portion of Figure 3 shows this domain.

The multinomial probability distribution on 10 to 10 of the sum j=010(L j Rj) is the sum of the probabilities along diagonals of the bivariate binomial distribution as indicated by the red arrows. In the case the biased coin has p = 0.6 so the mean of Ln Rn = 0.1, the probability of the event

[Sn > 0] = 1 n j=1n(L j Rj) > 0 = j=1n(L j Rj) > 0 = j=1nL j > j=1nR j

is the sum of the probabilities in the strict upper triangle. This is the same criterion as for the majority of heads above. For p = 0.6 the search using the sample mean again requires 143 pair flips to distinguish the coins with certainty 0.95.

The framing of the application motivates the choice of criterion. The original problem posed in FiveThirtyEight.com comes from a white paper by James White, Jeff Rosenbluth, and Victor Haghani from Elm Partners Investing. The paper “Good and bad properties of the Kelly criterion” by McLean, Thorp and Ziemba motivated their example. The question is a simplified and idealized version of an investment question about how to identify a higher performing investment, modeled by a biased coin, from a lower performing investment with just an even chance at making a profit, modeled by a fair coin. In that case, the 95% certainty of a majority of gains is a reasonable choice of criterion. If the question is merely to identify the biased coin, then it makes sense to use the Central Limit Theorem to distinguish the mean given that the biased coin is in the left hand from the mean given that the biased coin is in the right hand.

Bayesian Solution

The coin flips are independent. So if a coin comes up heads with probability p and we flip it n times, the binomial distribution B(k,n,p) = n k pk(1 p)nk gives the probability that it comes up heads exactly k times. Number the coins 1 and 2 probabilities of coming up heads p1 and p2 respectively. Flip each coin n times and record how many times each coin come up heads, but we don’t know which coin is which. Say the coins come up heads kL and kR times for the left and right coin respectively. Call the vector of observed data k = (kL,kR).

Exactly two possible scenarios occur:

Fair on Left
Fair coin 1 was in the left hand and biased coin 2 was in the right hand and the observed outcome is k = (kL,kR). Call this scenario 𝜃L. The likelihood of this scenario occurring is
Q(k|𝜃L) = B(kL,n,p1)B(kR,n,p2).

Fair on Right
Fair coin 1 was in the right hand and biased coin 2 was in the left hand and the observed outcome is k = (kL,kR). Call this scenario 𝜃R. The likelihood of this scenario occurring is
Q(k|𝜃R) = B(kL,n,p2)B(kR,n,p1).

Compute the posterior probability by using Bayes rule:

Q(𝜃L|k) = Q(k|𝜃L) 𝜃L Q(k|𝜃L) 𝜃L + Q(k|𝜃R) 𝜃R

and similarly for Q(𝜃R|k). Assume that scenarios 𝜃L and 𝜃R have the same prior probability so 𝜃L = 𝜃R = 12. Therefore, the Bayesian condition for confidence simplifies to

Q(k|𝜃L) Q(k|𝜃L) + Q(k|𝜃R) > 1 α or  Q(k|𝜃R) Q(k|𝜃L) + Q(k|𝜃R) > 1 α.

To be confident with level α about one of the scenarios then the posterior probability must be greater than 1 α.

Fair on Left
If Q(𝜃L|k) > 1 α, then we are confident in Scenario Fair on Left.
Fair on Right
If Q(𝜃R|k) > 1 α, then we are confident in Scenario Fair on Right.

By definition, Q(𝜃L|k) + Q(𝜃R|k) = 1 for all k. So the two cases above can’t simultaneously be true when α < 12. Rearranging these inequalities, we have

Q(k|𝜃L) Q(k|𝜃R) > 1 α α  or Q(k|𝜃R) Q(k|𝜃L) > 1 α α .

The implication is that we can stop flipping coins once the difference between log-likelihoods grows sufficiently large. The smaller is α, the larger the difference in log-likelihoods must be before we can declare that we are confident. Simplify the expression by substituting the definition for the likelihoods Q(k|𝜃L) and Q(k|𝜃R) in terms of the binomial probabilities becoming

Q(k|𝜃L) Q(k|𝜃R) = p1 p2 kLkR 1 p2 1 p1 kLkR .

Take logarithms of both sides and combine the expressions into a single inequality involving the absolute difference of log-likelihoods

log Q(k|𝜃L) log Q(k|𝜃R) > log 1 α 1 .

The implication is that we can stop flipping coins once the difference between log-likelihoods grows sufficiently large. The smaller is α, the larger the difference in log-likelihoods must be before we can declare that we are confident. After simplification, this becomes

kL kR log 1 p1 1 log 1 p2 1 > log 1 α 1 .

The number of heads kL and kR in the left and right hands are random variables. In one hand the number of heads from the coin with p1 will have the binomial probability distribution with mean np1 and standard deviation np1 (1 p1 ). In the other hand the number of heads from the coin with p1 will have the binomial probability distribution with mean np2 and standard deviation np2 (1 p2 ). Normal distributions with corresponding means and standard deviations can approximate each binomial distribution.

As a first approximation, substitute the empirical probabilities p̂1 = kLn and p̂2 = kRn obtained from the distribution means. Rearrange to isolate n to obtain

n > 1 p̂1 p̂2 log 1 α 1 log 1 p1 1 log 1 p2 1 .

This expression is a lower bound on the number of samples required, in terms of the confidence α, the known probabilities p1 and p2 and the empirical probabilities p̂1 and p̂2. Note that if p1 p2 0, then n which is expected. Taking p̂1 = p1 = 0.5, p̂2 = p2 = 0.6 and α = 0.05, then n = 72.619. More generally, Figure 4 shows a plot of the number of flips required as a function of p2 for fixed p1 = 0.5 and fixed α = 0.05, so in percentages 95% confidence.


Minimum flips required as function of p

Figure 4: Number of flips required as a function of p2 for fixed p1 = 0.5 and α = 0.05.

However, this is only a lower bound on the real number of flips required to find the biased coin since kL and kR can be closer than what was used above. In fact, in the scenario Fair on Left can have kL in the range [0,np1 + zβnp1 (1 p1 )] and kR in the range [np2 zβnp2 (1 p2 ),n]. The probability of each of these events is determined by quantiles zβ of the binomial distribution, or approximately by the normal distribution. Since np2(1 p2) < n 1 2 1 2 = 1 2n

kL kR > (np2 zβnp2 (1 p2 )) (np1 + zβnp1 (1 p1 )) = n(p2 p1) zβ(np2 (1 p2 ) + np1 (1 p1 ))n > n(p2 p1) zβn

with probability determined by the quantile zβ. (Note that since p2 p1 > 0 this is positive for sufficiently large n.) The number of flips then required to determine which is the biased coin is then determined by

n(p2 p1) zβn > 1 p̂1 p̂2 log 1 α 1 log 1 p1 1 log 1 p2 1 .

Choosing a quantile zβ, substituting for p1, p2 and α, and then solving for n gives a lower bound for the number of flips required for distinguishing the fair coin from the biased coin.

For example, choosing zbeta = 1.96 gives the approximate probability β = 0.975 that kL in the range [0,np1 + zβnp1 (1 p1 )] and independently that kR in the range [np2 zβnp2 (1 p2 ),n]. Then the probability of both events is approximately (0.975)2 = 0.95. Using p1 = 0.5, p2 = 0.6 and α 0.05, the inequality is

0.1n 1.96n > 7.62.

Solving for n gives n = 525.51. As another example set zβ = 0.559 with a probability of 0.712 of kL in the range [0,np1 + zβnp1 (1 p1 )] and independently that kR in the range [np2 zβnp2 (1 p2 ),n] and joint probability of 0.507. Then solving 0.1n 0.559n > 7.62 gives n = 143. As a final example, choosing zβ = 0 gives a probability of 0.5 of kL in the range [0,np1] and independently with probability approximately 0.57 that kR in the range [np2,n] and joint probability of 0.254. This is equivalent to the original calculation giving the lower bound of n = 72.6.

The extended Bayesian analysis introduces another parameter zβ. Using two parameters zβ1 and zβ2, as long as np1 + zβ1np1 (1 p1 ) < np2 + zβ2np2 (1 p2 ) for reasonable values of n, might be better. Now some experimentation, including binary search, is necessary to choose a value of n 73 required to determine the biased coin with certainty 0.95. The scripts below show the results of that experimentation and compare it to the other determination methods based on the majority and the Central Limit Theorem. For example, with p1 = 0.5 in the left hand, and p2 = 0.6 in the right hand it takes 189 flips to identify the fair coin in the left hand with 95% certainty. A close look at the results show why the log-likelihood Bayesian criterion requires more flips for the same certainty. The short answer is that the log-likelihood is a stricter requirement than the majority requirement in the other two approaches. In one trial with 200 flips, the fair coin in the left hand came with 108 heads while the biased coin in the right hand came up with 110 heads. The majority of heads was in the right hand, but the absolute difference of the log-likelihoods is 0.8109302, not greater than log(1α 1) = 2.944439. Both heads totals are well within the two-standard deviation range around the respective expected values of 100 heads and 120 heads respectively.

An R script testing all three methods against placing the fair and biased coins in the left and right randomly is in the scripts section. In summary, even with more flips, the Likelihood method is slightly less effective than the two majority methods. It is also a more complicated procedure.

Sources

The definition of biased coin is from Wikipedia.

The simple probability problem is adapted from Bogolmony, Cut-the-Knot, Two Coins, One Fair, One Biased.. The same problem appears in FlyingColoursMaths Two Coins, One Fair, One Biased..

The problem of how many tosses to find the biased coin appeared in the FiveThirtyEight.com weekly Riddler puzzle column on September 29, 2017. This first subsection with the majority solution is adapted from a white paper “What’s Past is Not Prologue” by James White, Jeff Rosenbluth, and Victor Haghani from Elm Partners Investing. In turn, their example is motivated by a paper “Good and bad properties of the Kelly criterion” by McLean, Thorp and Ziemba. The second subsection with the statistical solution is original.

The Bayesian analysis is adapted and extended from
Lessard,Finding the baised coin..

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

Scripts

R

R script for Majority Binary Search..

1prob <- function(n, p) { 
2    fair <- dbinom(0:n, n, 0.5)         #fair binomial distribution 
3    biased <- dbinom(0:n, n, p)         #biased binomial dist 
4    bivarBinom <- fair %o% biased       #outer product, (n+1) x (n+1) matrix 
5    bivarBinom[ lower.tri(bivarBinom, diag=TRUE) ] <- 0 
6    # retain only the upper triangular values, without diagonal 
7    sum( bivarBinom )                   #add them all up 
8} 
9 
10reqN <- c()                             #initialize vector to hold results 
11 
12for (certainty in c(0.95, 0.9, 0.75)) { #three representative values 
13    high <- 1000                        #arbitrary guess for max for search 
14    for (p in seq(0.55, 0.99, length=45)) { #array of bias values 
15        low <- 1                            #minimum to start search 
16 
17        while (high - low > 1) { 
18            try <- floor( (low + high)/2 ) #binary search 
19            if ( prob(try, p) <= certainty ) low <- try else high <- try 
20            ## uses monotone increasing nature of probability 
21        } 
22 
23        reqN <- c(reqN, low)            #add search result to vector of results 
24    } 
25} 
26 
27N <- matrix(reqN, 45,3)                 #reformat to three columns, one for each certainty 
28 
29ps = seq(0.55, 0.99, length=45)         #array of bias values to plot on horiz 
30plot( ps, N[,1], pch=20, xlab="p", ylab="N") #plot required N for certainty 0.95 
31points( ps, N[,2], pch=20, col="red")        #add plot for required N for 0.90 
32points( ps, N[,3], pch=20, col="blue")       #add plot for required N for 0.75
4cAp1x1-1800033:

R script for Statistical Binary Search..

1library(distr) 
2 
3prob <- function(nn, p) { 
4    D1 <- DiscreteDistribution( -1:1, c((1-p)/2, 1/2, p/2) ) 
5    ## trinomial distribution of X_n = L_n - R_n 
6    Dnn <- convpow(D1, nn) 
7    ## distribution of sum_{j=1}^n X_n 
8    end0 <- NROW( (support(Dnn)) ) 
9    ## last non-zero support point 
10    start0 <- match( 0, (support(Dnn))) + 1 
11    ##  index of support point of 0, then add 1 
12    distDnn <- d(Dnn)(support(Dnn)) 
13    ## extract vector of distribution values on [start0, end0] 
14    sum( distDnn[start0:end0] )         #add up the probability 
15} 
16 
17reqN <- c()                             #initialize vector to hold results 
18 
19for (certainty in c(0.95, 0.9, 0.75)) { #three representative value 
20    high <- 150                          #place to start search 
21    for (p in seq(0.55, 0.99, length=45)) { #array of bias values 
22        low <- 1                            #minimum to start search 
23        # high <- high from previous        #a maximum to start with 
24        ## For greater efficiency, note that the required number of flips 
25        ## for the next p  will be not more than the number of flips for previous 
26        ## p, so restrict search to interval n=1 to to n=reqN from previous search 
27        while (high - low > 1) { 
28            try <- round( (low + high)/2 ) #binary search 
29            if ( prob(try, p) <= certainty ) low <- try  else high <- try 
30        } 
31 
32        reqN <- c(reqN, high)            #add search result to vector of results 
33    } 
34} 
35 
36N <- matrix(reqN, 45,3)                 #reformat to three columns, one for each certainty 
37 
38ps = seq(0.55, 0.99, length=45)         #array of bias values to plot on horiz 
39plot( ps, N[,1], pch=20, xlab="p", ylab="N") #plot for required N for certainty 0.95 
40points( ps, N[,2], pch=20, col="red")        #add plot for required N for 0.90 
41points( ps, N[,3], pch=20, col="blue")       #add plot for required N for 0.75
4cAp2x1-1800042:

R script for Log Likelihood..

1alpha <- 0.05 
2alphaRatio <- (1-alpha)/alpha 
3logAlphaRatio <- log((1-alpha)/alpha) 
4 
5p1 <-  0.5 
6p2 <- 0.6 
7 
8n <- 200 
9k <- 100 
10 
11# uniform fair in Left hand 
12coinFlipsLeft <- array( (runif(n*k) <= p1), dim=c(k,n)) 
13coinFlipsRight <- array( (runif(n*k) <= p2), dim=c(k,n)) 
14 
15headsTotalLeft <-  apply(coinFlipsLeft, 1, sum) 
16headsTotalRight <-  apply(coinFlipsRight, 1, sum) 
17# see FEATURES for why cumsum, not just column sum 
18 
19logQkleft <-  dbinom(headsTotalLeft, n, p1, log=TRUE) + 
20    dbinom(headsTotalRight, n, p2, log=TRUE) 
21logQkright <-  dbinom(headsTotalRight, n, p1, log=TRUE) + 
22    dbinom(headsTotalLeft, n, p2, log=TRUE) 
23 
24logLikeRatio <- abs(logQkleft - logQkright) 
25logGuessBiased <- logLikeRatio > logAlphaRatio 
26 
27logcorrect <- sum(logGuessBiased == (p1 == 0.5)) 
28logperCentCorrect <- 100 * logcorrect/k 
29logperCentCorrect
4cAp3x1-1800030:

R script for Testing Each Method..

1n <- 200   # number of flips 
2k <- 500   # number of experiments 
3alpha <- 0.05 
4 
5NMaj <- 143  # required for Majority 
6NCLT <- 143  # required for CLT 
7NLL <- 189   # required for logLikelihood 
8 
9# choices <- rep(FALSE, k) 
10choices <- (runif(k) <= 0.5) 
11pLeft <- ifelse(choices, 0.6, 0.5) 
12pRight <-  ifelse(!choices, 0.6, 0.5) 
13 
14ULeft <- array( runif(k*n), dim=c(k,n) ) # flips along rows 
15coinFlipsLeft <- ULeft <= pLeft  # take advantage of recycling 
16URight <- array( runif(k*n), dim=c(k,n) ) # flips along rows 
17coinFlipsRight <- URight <= pRight  # take advantage of recycling 
18 
19headsTotalLeft <- apply(coinFlipsLeft, 1, cumsum) 
20headsTotalRight <- apply(coinFlipsRight, 1, cumsum) 
21 
22LmR <- headsTotalLeft - headsTotalRight 
23CLT <- LmR/(1:n) 
24 
25guessBiasedMajority <- LmR[NMaj,] > 0 
26guessBiasedCLT <- CLT[NCLT, ] - 0.1 > -0.1 
27 
28logQL <- dbinom(headsTotalLeft[NLL, ], NLL, 0.6, log = TRUE) + 
29         dbinom(headsTotalRight[NLL, ], NLL, 0.5, log = TRUE) 
30logQR <- dbinom(headsTotalRight[NLL, ], NLL, 0.6, log = TRUE) + 
31         dbinom(headsTotalLeft[NLL, ], NLL, 0.5, log = TRUE) 
32rhs <- log(1/alpha - 1) 
33guessBiasedLL <- ( (logQL - logQR) > rhs ) 
34 
35correctMajority <- sum(guessBiasedMajority == (pLeft == 0.6)) 
36perCentCorrectMajority <- 100 * correctMajority/k 
37perCentCorrectMajority 
38 
39correctCLT <- sum(guessBiasedCLT == (pLeft == 0.6)) 
40perCentCorrectCLT <- 100 * correctCLT/k 
41perCentCorrectCLT 
42 
43correctLogLike <- sum(guessBiasedLL == (pLeft == 0.6)) 
44perCentCorrectLL <- 100 * correctLogLike/k 
45perCentCorrectLL
4cAp4x1-1800046:

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. You have two coins. One is fair with H = 1 2. The other coin is biased with H = p > 1 2. First you toss one of the coins once, resulting in heads. Then you toss the other coin three times, resulting in two heads. What is the least value of p that will allow you to decide which is the biased coin based on this information?
  2. Show that the log-likelihood expression with the binomial probabilities simplifies to
    kL kR log 1 p1 1 log 1 p2 1 > log 1 α 1 .

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   Leonard C. MacLean, Edward O. Thorp, and William T. Ziemba. Long-term capital growth: the good and bad properties of the Kelly and fractional Kelly capital growth criteria. Quantitative Finance, 10(7):681–687, 2010.

[2]   James White, Jeff Rosenbluth, and Victor Haghani. What’s past is Not prologue. https://ssrn.com/abstract=3034686, April 2017.

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable effort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on September 7, 2018