2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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).$ $\endgroup$ – whuber Oct 7 at 16:04
  • $\begingroup$ @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$). $\endgroup$ – Shirish Kulhari Oct 7 at 16:09
  • 1
    $\begingroup$ That does not make the test redundant--but it does reveal the problem with the algorithm. $\endgroup$ – whuber Oct 7 at 16:14
  • $\begingroup$ @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. $\endgroup$ – Shirish Kulhari Oct 7 at 16:18
2
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.