# How easy is it to create false evidence for a biased coin?

I have a biased coin which comes up heads with probability $$p$$. I know the value of $$p$$, but I want to falsely claim that the coin has a different probability of heads, $$q$$, where $$q > p$$.

To support my claim I decide to produce some false evidence: I flip the coin repeatedly and record the fraction of flips that were heads, and keep flipping until the fraction is at least $$q$$. I also make sure I flip the coin at least $$100$$ times before stopping (so I flip $$100$$ times initially, then I keep flipping until the fraction of heads so far is at least $$q$$). I report the total number of flips, and the fraction of heads, as evidence that the coin has probability of heads (approximately) $$q$$.

1. In terms of $$p$$ and $$q$$, what is the probability that I can successfully produce evidence for my false claim? (I.e. what is the probability that after $$100$$ initial flips, my repeated flipping will eventually terminate with a fraction above $$q$$ in a finite amount of time?)

2. Given that I do successfully produce the false evidence, what is the expected number of flips required?

I thought of this question out of curiosity, when pondering about how we can soundly use data to infer unknown probabilities.

For Question 1, the probability is positive: in fact, it's at least $$p^{100}$$ since the first $$100$$ flips could all be heads. It's less clear if the probability is $$< 1$$, but I think it is. The question can be phrased as a random walk in two dimensions, where the false evidence is produced if the random walk enters into the region of points $$(x,y)$$ where $$y > q \cdot (x + y) \text{ and } x + y \ge 100$$.

For Question 2, probably thinking about it as a random walk is also the first step.

For either question, I would be happy with upper/lower bounds or approximations, if an exact answer is not easy.

• The answer to (2) would be infinite if $q=p$ so it would be curious if it was not infinite for $q \gt p$ Commented May 22, 2019 at 17:18
• @Henry Why is it infinite for $q=p$? Commented May 22, 2019 at 18:30
• JairTaylor: For example with a balanced 1-D $\pm1$ random walk, the expected time of the first return to $0$ is infinite Commented May 22, 2019 at 18:40
• @Henry: I don't think that would be curious. We're conditioning on actually achieving $q$. For $q=p$, this can be achieved arbitrarily late, but for $q\gt p$ it becomes very unlikely over time, so the conditional expectation could be dominated by the early opportunities and be finite. Commented Dec 12, 2019 at 23:38
• I wonder whether Hoeffding's inequality helps for 1. Let $S_n$ denote the number of heads after $n$ flips. This is a series of Bernoulli trials with parameter $p$. We have $E(S_n)=pn$. Hoeffding's inequality yields (see the "Proof" section for the statement) $$P(S_n\geq qn) = P\big(S_n-E(S_n)\geq qn-pn\big) \leq \exp\big(-2n^2(q-p)^2\big).$$ Commented May 12, 2020 at 12:30

# A few thoughts on your question 1

The number $$S_n$$ of heads after $$n$$ flips follows a standard binomial distribution with parameters $$n$$ and $$p$$. Alternatively, the sequence $$(S_n)$$ is a Bernoulli process.

## A larger lower bound

We can use this to somewhat sharpen the lower bound of $$p^{100}$$ you give in your question. Namely, while getting 100 successes in the first 100 trials (let's set $$n_0=100$$) is sufficient, so would be getting only $$\lceil qn_0\rceil$$. The probability for this is the upper tail probability of our binomial distribution,

$$P(S_{n_0}\geq qn_0) = \sum_{k=\lceil qn_0\rceil}^{n_0}{n\choose k}p^k(1-p)^{n-k}.$$

Now, Wikipedia tells us (quoting chapter 11 of Elements of Information Theory by Cover and Thomas, which I admittedly haven't looked at) that

$$P(S_n\geq k) \geq \frac{1}{n+1}\exp\bigg(-nD\Big(\frac{k}{n}\,||\,p\Big)\bigg) \text{ if }p<\frac{k}{n}<1,$$ where $$D\Big(\frac{k}{n}\,||\,p\Big) = \frac{k}{n}\ln\frac{k}{np}+\Big(1-\frac{k}{n}\Big)\ln\frac{1-\frac{k}{n}}{1-p}$$ is the relative entropy between the $$\frac{k}{n}$$-coin and the $$p$$-coin. We note that with $$k=\lceil qn_0\rceil$$ with $$q>p$$, the condition $$p<\frac{k}{n_0}=\frac{\lceil qn_0\rceil}{n_0}<1$$ is satisfied, so we get a lower bound for your probability (resulting solely from the probability of having enough successes in the inital $$n_0$$ flips of)

\begin{align*} &\frac{1}{n_0+1}\exp\bigg(-n_0D\Big(\frac{\lceil qn_0\rceil}{n_0}\,||\,p\Big)\bigg) \\ =& \frac{1}{n_0+1}\exp\bigg(-n_0\frac{\lceil qn_0\rceil}{n_0}\ln\frac{\lceil qn_0\rceil}{n_0p}-n_0\Big(1-\frac{\lceil qn_0\rceil}{n_0}\Big)\ln\frac{1-\frac{\lceil qn_0\rceil}{n_0}}{1-p}\bigg) \\ =& \frac{1}{n_0+1}\bigg(\frac{\lceil qn_0\rceil}{n_0p}\bigg)^{-\lceil qn_0\rceil} \bigg(\frac{1-\frac{\lceil qn_0\rceil}{n_0}}{1-p}\bigg)^{\lceil qn_0\rceil-n_0}, \end{align*} which should be larger than $$p^{100}$$ - for instance, if $$p=0.4$$ and $$q=0.5$$, then $$p^{100}\approx\exp(-91.6)\approx 1.6\times 10^{-40}$$, while this expression comes out to about $$\exp(-6.7)\approx 0.0013$$.

## An upper bound

Next, as noted in a comment, Hoeffding's inequality may be helpful. We have $$E(S_n)=pn$$, and Hoeffding's inequality yields (see the "Proof" section for the statement) that $$P(S_n>qn) = P(S_n-E(S_n)\geq qn-pn) \leq\exp\big(-2n(q-p)^2\big).$$

As you write, we can use the union bound to get a very crude bound on the probability we are interested in: \begin{align*} & P(\exists n\geq n_0\colon S_n\geq qn) \\ \leq & \sum_{n=n_0}^\infty P(S_n>qn) \text{ by the union bound} \\ \leq & \sum_{n=n_0}^\infty \exp\big(-2n(q-p)^2\big) \text{ by Hoeffding, above} \\ = & \sum_{n=n_0}^\infty \Big(\underbrace{\exp\big(-2(q-p)^2\big)}_{=:x}\Big)^n \\ = & \frac{x^{n_0}}{1-x}\text{ as a geometric series} \\ = & \frac{\exp\big(-2n_0(q-p)^2\big)}{1-\exp\big(-2(q-p)^2\big)}. \end{align*}

As an example, for $$p=0.4$$ and $$q=0.5$$ as above, this comes to about $$6.83$$. Hum. It gets more useful for larger $$q$$, e.g., $$q=0.6$$ yields a bound of about $$0.0044$$.

Finally, here is a little simulation. I simulated 100,000 trajectories of our Bernoulli process with $$p=0.4$$ and calculated the running success probabilities $$(\frac{S_n}{n})$$. Below, I plot 10 random trajectories, as well as the trajectory of the maximum of our 100,000 running probabilities. The initial $$n_0=100$$ steps are plotted in gray. I also included a horizontal line at $$q=0.5$$ in red. It seems like the initial steps dominate the question. (Incidentally, out of our 100,000 trajectories, 2,682 had a quotient of $$\frac{S_{n_0}}{n_0}\geq 0.5$$ after the initial $$n_0=100$$ steps, where the bound above would have predicted at least 130.)

R code:

pp <- 0.4
qq <- 0.5
n_0 <- 100

# the original lower bound:
100*log(pp)

# the larger lower bound
-log(n_0+1)-
ceiling(qq*n_0)*log(ceiling(qq*n_0)/(pp*n_0))+
(ceiling(qq*n_0)-n_0)*log((1-ceiling(qq*n_0)/n_0)/(1-pp))

# the overall upper bound from from Hoeffding's inequality and the union bound
exp(-2*n_0*(qq-pp)^2)/(1-exp(-2*(qq-pp)^2))

# the simulation
n_sims <- 1e5
sim_length <- 2e3
initial_length <- 100
set.seed(1)

sims <- matrix(runif(n_sims*sim_length)<pp,nrow=sim_length)
running_quotient <- apply(sims,2,cumsum)/matrix(1:sim_length,nrow=sim_length,ncol=n_sims)

plot(c(1,sim_length),range(running_quotient),type="n",xlab="Step",ylab="Proportion of successes",las=1)
for ( ii in 1:10 ) {
lines(1:sim_length,running_quotient[,ii],col="gray30")
lines(1:initial_length,running_quotient[1:initial_length,ii],col="gray80")
}
lines(1:sim_length,apply(running_quotient,1,max),lwd=2)
lines(1:initial_length,apply(running_quotient,1,max)[1:initial_length],lwd=2,col="gray70")
abline(h=qq,col="red")

sum(running_quotient[100,]>=qq)