Waste less time on Facebook — follow Brilliant.
×

notrand()

You are given a black-box function, notrand(), which returns 0 with 60% probability and 1 with 40% probability. Create a new function, rand(), which returns 0 and 1 with equal probability (i.e. 50% each) using only notrand() as your source of randomness.

I've heard many interesting approaches to the problem. I'll post my own solution later after hearing some from the community!

Note by Brian Rodriguez
2 years, 5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Here is a possible function for rand():

  1. Run notrand() twice.
  2. If the outputs are 0 and 1, return 0.
  3. If the outputs are 1 and 0, return 1.
  4. Otherwise, go back to step 1.
Jon Haussmann · 2 years, 5 months ago

Log in to reply

let a0, a1 use notrand() to assign a value. so a0 = {0: 60%, 1: 40%}, a1 = {0: 60%, 1: 40%}.

Consider a0 + a1:

0(60%) + 0(60%) = 0b00

0(60%) + 1(40%) = 0b01

1(40%) + 0(60%) = 0b01

1(40%) + 1(40%) = 0b10

Note the least significant bit (which can be found with the xor of a0 and a1) has a different weight than the notrand() function, namely:

a0 ⊕ a1 = {0: 52%, 1: 48%}

Now if we combine two of these results (4 calls to notrand() in total) the percentages change again to:

0(52%) ⊕ 0(52%) = 0

0(52%) ⊕ 1(48%) = 1

1(48%) ⊕ 0(52%) = 1

1(48%) ⊕ 1(48%) = 0

or {0: 50.08%, 1: 49.92%}

This pattern will approach 50/50 as the sub iterations get larger, however, the associative property of xor gives one more detail:

((a ⊕ b) ⊕ (c ⊕ d)) ⊕ ((i ⊕ j) ⊕ (k ⊕ l)) = (a ⊕ b ⊕ c ⊕ d ⊕ i ⊕ j ⊕ k ⊕ l)

and so xor'ing multiple calls of notrand() actually brings the function closer to 50/50 regardless of the number of calls used and the order they are combined in. Brian Rodriguez · 2 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...