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
3 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

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 - 3 years, 3 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 - 3 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...