Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

An Unfair Coin 3: Return of the Golden Inequality


  • Please log in to reply
10 replies to this topic

#1 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 28 July 2012 - 12:23 AM

The golden ratio is (1+sqrt(5))/2. The reciprocal of this happens to be (sqrt(5)-1)/2 which is about .618.

I happened to have a biased coin that would come up heads with exactly that probability. This was my lucky coin, and I used it to bias my decisions slightly towards the ones I favored. It was quite a tragedy when I lost this coin (not only for it's decision making qualities, but it was, coincidentally, made of gold).

How can I simulate a coin toss from my missing lucky coin using a fair coin instead?
  • 0

#2 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5818 posts
  • Gender:Male
  • Location:New York

Posted 28 July 2012 - 04:23 AM

Spoiler for with a few flips

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#3 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 28 July 2012 - 07:01 AM

Yup, that's essentially what I got.

What's interesting is combining the last puzzle and this one you can show that with any biased (or fair) coin you can emulate any other biased (or fair) coin or any die of any number of sides. I didn't include emulating a biased die, but that's not much of a stretch. (this does assume both heads and tails can and do occur)

Spoiler for My solution


Spoiler for Directly emulating any coin (or die) using any coin (or die)

  • 0

#4 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 28 July 2012 - 03:50 PM

Yup, that's essentially what I got.

What's interesting is combining the last puzzle and this one you can show that with any biased (or fair) coin you can emulate any other biased (or fair) coin or any die of any number of sides. I didn't include emulating a biased die, but that's not much of a stretch. (this does assume both heads and tails can and do occur)

Spoiler for My solution


Spoiler for Directly emulating any coin (or die) using any coin (or die)


Great puzzle. I'd just note that there's equivalent way to do this that may be more intuitive for some people.
Spoiler for spoiler

  • 0

#5 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5818 posts
  • Gender:Male
  • Location:New York

Posted 09 August 2012 - 05:42 PM

Spoiler for spoiler


I thought about the point you're making, but I didn't come to precisely that conclusion. A fair coin requires ony a single flip to give a p=0.5 outcome. By comparison, this scheme can take an arbitrarily long sequence of flips. But only in a vanishingly small fraction of cases. That's the only "finite N" limitation that I see. Almost every "finite N" sequence of flips is sufficient to produce the desired result.

As to whether the scheme produces the exact bias of p, I think it does.

You'd have to run the scheme an arbitrarily large number of times to reconstruct [verify?] the value of p that defines its bias, just as you'd have to do with a fair coin to prove that it's fair. But the bias produced by the scheme, each time it's run, is precisely p.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#6 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 09 August 2012 - 09:21 PM

I thought about the point you're making, but I didn't come to precisely that conclusion. A fair coin requires ony a single flip to give a p=0.5 outcome. By comparison, this scheme can take an arbitrarily long sequence of flips. But only in a vanishingly small fraction of cases. That's the only "finite N" limitation that I see. Almost every "finite N" sequence of flips is sufficient to produce the desired result.

As to whether the scheme produces the exact bias of p, I think it does.

You'd have to run the scheme an arbitrarily large number of times to reconstruct [verify?] the value of p that defines its bias, just as you'd have to do with a fair coin to prove that it's fair. But the bias produced by the scheme, each time it's run, is precisely p.


You're right in that your scheme, which calls for consecutive flips until the outcome differs from the binary representation, returns a probability that is precisely p. I made a mistake earlier in saying that my scheme (flip the coin for a fixed number of time N) is 'equivalent', which it assuredly is not. While that scheme may be more intuitive, it sufferers from approximation error due to the fixed finite N, plus the fact that it is not as computationally efficient. Good point!
  • 0

#7 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 10 August 2012 - 06:41 AM

Spoiler for My solution



Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).
  • 0

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5818 posts
  • Gender:Male
  • Location:New York

Posted 10 August 2012 - 07:14 AM

Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).


Spoiler for intuitive guess

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#9 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 10 August 2012 - 09:16 AM

Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).

Spoiler for It seems to me...

  • 0

#10 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5818 posts
  • Gender:Male
  • Location:New York

Posted 10 August 2012 - 02:45 PM

Spoiler for It seems to me...


What he said. :)
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users