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

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.

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)

Okay so we have some function that generates a True value with p = 0.60 and a False value with p = 0.40 . Suppose for a second we run this function twice? What is the probability that the results will be the same.

so F_1 == true and F_2 == true happens with p( 0.60 * 0.60 ) = 0.36

and F_1 == false and F_2 == false happens with p( 0.40 * 0.40 ) = 0.16

and F_1 != F_2 happens with p( 0.6 * 0.4 + 0.6 * 0.4 ) = 0.48

that will give you a function with returns true 0.52 percent of the time, which isn't quite what we are looking for but is interesting.

A much simple solution would be to say: If I have true 60 % of the time, then what percent of the time ( which what probability ) should I change that value to false in order to be true 50 % of the time.

That's all I'll say because this is homework.

Approach:

You run your 40/60 function until you hit result that returns 40% probability. Once this happens you calculate result.

0.5 is calculated this way.

0.5 = 0.6 - 0.6^2 + 0.6^3 + 0.6^4 - 0.6^5 - 0.6^6 + 0.6^7 + 0.6^8 - 0.6^9 + ....
(if current result is more than 0.5 you add else you substract)

Once you hit 0.4 you calculate result of this function. If it is > 0.5 you return true, else you return false.

hey how about this approach: We know that calling F1() 10 times: 6 times it'll return true and 4 times false

So in F2() we can have a counter that counts to 5. With every call to F1() we increment the counter. F2() returns what F1() returns. When the counter reaches 5 F2() returns "false" and re-initializes the counter. What say?