# Program analysis of a coin toss simulator

Here's a problem I'm trying to solve (it's a problem from the CS109 course, assignment 2):

Suppose we want to write an algorithm fairRandom for randomly generating a $$0$$ or a $$1$$ with equal probability ($$= 0.5$$). Unfortunately, all we have available to us is a function: unknownRandom() that randomly generates bits, where on each call a $$1$$ is returned with some unknown probability $$p$$ that need not be equal to $$0.5$$ (and a $$0$$ is returned with probability $$1–p$$). Consider the following algorithm for fairRandom:

def fairRandom():
while True:
r1 = unknownRandom()
r2 = unknownRandom()
if (r1 != r2): break
return r2


a) Show mathematically that fairRandom does indeed return a $$0$$ or $$1$$ with equal probability.

b) Say we want to simplify the function, so we write the simpleRandom function below. Would this also generate $$0$$ and $$1$$ with equal probability? Determine $$P($$simpleRandom$$\text{ returns } 1)$$ in terms of $$p$$.

def simpleRandom():
r1 = unknownRandom()
while True:
r2 = unknownRandom()
if (r1 != r2): break
r1 = r2
return r2


My attempt:

a) Let the number of loops be denoted by $$L$$. Then $$P(r_2=1)=P(r_2=1,L=1)+P(r_2=1,L=2)+P(r_2=1,L=3)+\ldots \\=(1-p)p+[p^2+(1-p)^2](1-p)p+[p^2+(1-p)^2]^2(1-p)p+\ldots$$

since if $$L=n$$, then for $$n-1$$ loops either both $$r_1=r_2=0$$ or $$r_1=r_2=1$$, thereby giving $$[p^2+(1-p)^2]^{n-1}$$ and in the last loop, $$r_1=0$$ and $$r_2=1$$, giving a probability of $$(1-p)p$$. The above expression further simplifies to:

$$(1-p)p\big[1+[p^2+(1-p)^2]+[p^2+(1-p)^2]^2+\ldots\big] \\=\frac{p(1-p)}{1-p^2-(1-p)^2}=\frac{1}{2}$$

Similarly for $$P(r_2=0)$$.

b) The line r1 = r2 is redundant, since that's run only if $$r_1$$ is already equal to $$r_2$$ (otherwise the loop would break in the previous statement). So basically the loop is run till the generated value for $$r_2$$ is different from the initial value of $$r_1$$.

If initially $$r_1=1$$, then the final value of $$r_2$$ would have to be $$0$$, so in that case, $$P(r_2=1\ |\ \text{init }r_1=1)=0$$. But if initially $$r_1=0$$, then $$r_2$$ will surely be $$1$$. So $$P(r_2=1)=P(r_2=1\ |\ \text{init }r_1=0)P(\text{init }r_1=0)=1\times(1-p)=1-p$$

I'm not too sure about either part. Are these correct? Would be grateful for feedback.

• Your claim in (b) about a redundant statement is not correct. As far as the first part of the problem goes, there's a much simpler solution: just compute $\Pr(r_2=1\mid r_1\ne r_2).$
– whuber
Oct 7 '19 at 16:04
• @whuber: In (b), let's say $r_1=1$ initially. If $r_2=1$, then the r1 != r2 condition is not satisfied and the loop continues. r1 = r2 assigns $1$ to $r_1$ and we're back to where we started. If, at any point, r2 gets allocated $0$ value, the loop breaks (since the value of $r_1$ always remains $1$). But the loop breaks only when $r_2=0$ (in the scenario when initial value of $r_1=1$). Oct 7 '19 at 16:09
• That does not make the test redundant--but it does reveal the problem with the algorithm.
– whuber
Oct 7 '19 at 16:14
• @whuber: For sure the test (if condition) isn't redundant. I don't know if that's how the function was supposed to be, because $r_1$ doesn't change from its initial value. Oct 7 '19 at 16:18

In fairRandom we have $$\begin{cases} P(r_1=0, r_2=0) & (1-p)^2 \\ P(r_1=0, r_2=1) & p-p^2 \\ P(r_1=1, r_2=0) & p-p^2 \\ P(r_1=1, r_2=1) & p^2 \end{cases}$$ since we only return for $$P(r_1=0, r_2=1)$$ and $$P(r_1=1, r_2=0)$$ and they have the same probability, it should be obvious $$p=0.5$$.

For b) note that the probabilities of $$P(r_1=0, r_2=1)$$ and $$P(r_1=1, r_2=0)$$ are not the same after the first loop because the probability of $$P(r_1)$$ has changed.

Edit: While commuting to stats class I realized OP was correct for part b). $$r_1$$ never changes in simpleRandom: because the line r1 = r2 only executes if $$r_1$$ is already equal to $$r_2$$. This means simpleRandom: merely returns the inverse of $$r_1$$ and thus has probability of $$1 - p$$.

This is some R code I generated to explore the problem numerically:

unknownRandom <- function(){
return(runif(1) < 0.2) # here our unknown p = 0.2
}

fairRandom <- function(){
r2<-numeric(0)
while(1){
r1 = unknownRandom()
r2 = unknownRandom()
if (r1 != r2){break}
}
return(r2)
}

simpleRandom <- function(){
r1 <- unknownRandom()
while(1){
r2 <- unknownRandom()
if (r1 != r2){break}
r1 <- r2
}
return(r2)
}

fres <- numeric(0)
sres <- numeric(0)
niter<-1e5
for(i in 1:niter)
{
fres[i] <- fairRandom()
sres[i] <- simpleRandom()
}

sum(fres)/niter # prints approx 0.5
sum(sres)/niter # prints approx 0.8 (or 1-p)