Homework: function to return one of two values with each call

Question

I'm trying to write a function that will return true or false each time it's called, but with a known frequency, say 60% of the time it'll be true, the other 40% it'll be false. Using that function I'm to create another function that returns true 50% of the time.

My initial approach was to use the random function, and return true if its under 0.6, false if it's over. Not sure how to approach the second part using that.

Answer 1

Let's take the general case: you built a function F1() that returns True with probability P (in your case, P=60%). now you build the second function this way:

F2():
   result1 = F1()
   result2 = F1()
   if result1 = True and result2 = False: return True
   elif result1 = False and result2 = True: return False
   else:  F2()

In this case, the probability of running F1 twice and obtaining (True,False) is the same as obtaining (False,True) and it's P * (1-P). Instead, if you get either (True,True) or (False,False) you call F2 recursively. This means, that after running F2 you always obtain True or False with probability 1/2 since the first two branches have equal probabilities, and the third will always give you the result of a function with 1/2 probability.

I am making this a community wiki in case someone wants to make my answer more clear. I realize it might be a little hard to explain the concept.

The average number of calls

The probability that the function F2() terminates right after n recursive calls is:

{(1-P)^2+P^2}^n*2P(1-P)

Therefore, the average number of recursive calls required is:

\Sum_{i=0}^\infty i*{(1-P)^2+P^2}^i*2P(1-P)