Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspxHere's a nifty little problem that a friend gave me yesterday that i thought i'd share with you:
You have three items (call them 'a', 'b' and 'c') that you want to choose any one from without bias. If you had a fair three sided die, you could assignen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875) Cyrus Blather Heads or Tails | debt solutionshttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9791537Fri, 19 Jun 2009 21:11:21 GMT91d46819-8472-40ad-a661-2c78acb4018c:9791537 Cyrus Blather Heads or Tails | debt solutions<p>PingBack from <a rel="nofollow" target="_new" href="http://debtsolutionsnow.info/story.php?id=12372">http://debtsolutionsnow.info/story.php?id=12372</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9791537" width="1" height="1"> Cyrus Blather Heads or Tails | debt consolidatorhttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9754525Mon, 15 Jun 2009 22:28:27 GMT91d46819-8472-40ad-a661-2c78acb4018c:9754525 Cyrus Blather Heads or Tails | debt consolidator<p>PingBack from <a rel="nofollow" target="_new" href="http://mydebtconsolidator.info/story.php?id=3697">http://mydebtconsolidator.info/story.php?id=3697</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9754525" width="1" height="1"> Cyrus Blather Heads or Tails | patio cushionshttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9751094Sun, 14 Jun 2009 19:16:32 GMT91d46819-8472-40ad-a661-2c78acb4018c:9751094 Cyrus Blather Heads or Tails | patio cushions<p>PingBack from <a rel="nofollow" target="_new" href="http://patiocushionsource.info/story.php?id=2238">http://patiocushionsource.info/story.php?id=2238</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9751094" width="1" height="1"> Cyrus Blather Heads or Tails | fire pithttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9747411Sun, 14 Jun 2009 06:15:43 GMT91d46819-8472-40ad-a661-2c78acb4018c:9747411 Cyrus Blather Heads or Tails | fire pit<p>PingBack from <a rel="nofollow" target="_new" href="http://firepitidea.info/story.php?id=1462">http://firepitidea.info/story.php?id=1462</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9747411" width="1" height="1"> Cyrus Blather Heads or Tails | Insomnia Curehttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9719163Wed, 10 Jun 2009 03:18:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:9719163 Cyrus Blather Heads or Tails | Insomnia Cure<p>PingBack from <a rel="nofollow" target="_new" href="http://insomniacuresite.info/story.php?id=7322">http://insomniacuresite.info/story.php?id=7322</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9719163" width="1" height="1"> Cyrus Blather Heads or Tails | Quick Dietshttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9715611Tue, 09 Jun 2009 14:33:22 GMT91d46819-8472-40ad-a661-2c78acb4018c:9715611 Cyrus Blather Heads or Tails | Quick Diets<p>PingBack from <a rel="nofollow" target="_new" href="http://quickdietsite.info/story.php?id=4165">http://quickdietsite.info/story.php?id=4165</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9715611" width="1" height="1"> Cyrus Blather Heads or Tails | Uniform Storeshttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9677953Mon, 01 Jun 2009 16:54:04 GMT91d46819-8472-40ad-a661-2c78acb4018c:9677953 Cyrus Blather Heads or Tails | Uniform Stores<p>PingBack from <a rel="nofollow" target="_new" href="http://uniformstores.info/story.php?id=15297">http://uniformstores.info/story.php?id=15297</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9677953" width="1" height="1"> Cyrus Blather Heads or Tails | Outdoor Ceiling Fanshttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9670780Sun, 31 May 2009 21:12:34 GMT91d46819-8472-40ad-a661-2c78acb4018c:9670780 Cyrus Blather Heads or Tails | Outdoor Ceiling Fans<p>PingBack from <a rel="nofollow" target="_new" href="http://outdoorceilingfansite.info/story.php?id=18645">http://outdoorceilingfansite.info/story.php?id=18645</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9670780" width="1" height="1"> Cyrus Blather Heads or Tails | Outdoor Ceiling Fanshttp://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#9670016Sun, 31 May 2009 18:23:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:9670016 Cyrus Blather Heads or Tails | Outdoor Ceiling Fans<p>PingBack from <a rel="nofollow" target="_new" href="http://outdoorceilingfansite.info/story.php?id=1009">http://outdoorceilingfansite.info/story.php?id=1009</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9670016" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#467852Thu, 15 Sep 2005 22:52:34 GMT91d46819-8472-40ad-a661-2c78acb4018c:467852herbieHmmm, after that post I'm starting to think more and more that I am confusing your terms. This paper (pages 7 and 8) better illustrate my questions <a href="<a rel="nofollow" target="_new" href="http://www.cl.cam.ac.uk/users/jeh1004/research/talks/termination-talk.pdf">http://www.cl.cam.ac.uk/users/jeh1004/research/talks/termination-talk.pdf</a>">http://www.cl.cam.ac.uk/users/jeh1004/research/talks/termination-talk.pdf">http://www.cl.cam.ac.uk/users/jeh1004/research/talks/termination-talk.pdf</a></a>.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=467852" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#467046Thu, 15 Sep 2005 08:52:37 GMT91d46819-8472-40ad-a661-2c78acb4018c:467046CyrusNHerbie: "In an infinite sequence of coin flips, you may never see a terminating result, thus the algorithm will never terminate. Am I missing something here?"
<br>
<br>In an infinite sequence of coin flips you *will* see a terminating result. :)
<br>
<br>"Sorry for the bluntness of the previous post, and perhaps I am misunderstanding your claim. I do agree that the algorithm is unbounded. I do not agree that it always terminates. Do you mean that the algorithm will "certainly" terminate (every outcome of coinflips will cause it to terminate), or that it will "almost certainly" terminate (the probability of termination is 1)? "
<br>
<br>No, there is no probability going on. (well, not strictyly true. there is probability, but it's just uninterestingly: 1). The other place where probability came in is in the *expected* number of rounds necessary for it to terminate: 4/3
<br>
<br>What is going on is that even in this perfect math world, it is provable (and has been done so in posts here) that the algorithm cannot take finite time to end. And, as has also been stated, a non-infinite (and thus finite) operation suffices for the term "algorithm".
<br>
<br>What can also be shown is that you cannot state the bound on the algorithm. I.e. if you say that it will end in N steps, one can show that there is a probability (albeit low) that the algorithm might end up taking more than N steps. However, despite being bounded, it is still finite.
<br>
<br>Remember, there is space between unbounded and infinite :)
<br>
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=467046" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#466472Thu, 15 Sep 2005 00:00:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:466472herbieSorry for the bluntness of the previous post, and perhaps I am misunderstanding your claim. I do agree that the algorithm is unbounded. I do not agree that it always terminates. Do you mean that the algorithm will "certainly" terminate (every outcome of coinflips will cause it to terminate), or that it will "almost certainly" terminate (the probability of termination is 1)?<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=466472" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#466424Wed, 14 Sep 2005 22:52:51 GMT91d46819-8472-40ad-a661-2c78acb4018c:466424herbieIn an infinite sequence of coin flips, you may never see a terminating result, thus the algorithm will never terminate. Am I missing something here?<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=466424" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#466409Wed, 14 Sep 2005 22:43:57 GMT91d46819-8472-40ad-a661-2c78acb4018c:466409CyrusNHerbie: Nope. The algorithm cannot take infinite time. It will always be finite and it will always terminate.
<br>
<br>however, the time it takes is not bounded. There's a difference.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=466409" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#466339Wed, 14 Sep 2005 22:04:44 GMT91d46819-8472-40ad-a661-2c78acb4018c:466339herbieThe algorithm may actually take infinite time. There is no guarantee that a fair coin will ever come up heads, for example, even after an infinite number of tosses.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=466339" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#458462Wed, 31 Aug 2005 17:59:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:458462Kristof VerbiestYou ask for equal probability, not for being random.
<br>
<br>I propose this algorithm:
<br>
<br>1) select A
<br>2) select B
<br>3) select C
<br>4) goto 1
<br>
<br>You can use the coin to buy a soda.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=458462" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#456630Fri, 26 Aug 2005 10:15:46 GMT91d46819-8472-40ad-a661-2c78acb4018c:456630locconfirmed. paging doesn't work for any search<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=456630" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#456629Fri, 26 Aug 2005 10:04:23 GMT91d46819-8472-40ad-a661-2c78acb4018c:456629locThe Search feature on the upper right hand corner doesn't work. Searching for "problem" resulted in 7 pages, which all looked the same somehow. But then there's Google.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=456629" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#455191Tue, 23 Aug 2005 20:36:31 GMT91d46819-8472-40ad-a661-2c78acb4018c:455191CyrusNFinal Answer:
<br>
<br>There is no bounded time algorithm for that can be used to pick a item with 1/3 probability given a fair coin. However, what's interesting is that the formal definition of an algorithm doesn't state whether an algorithm be bounded or unbounded. It simply states that it must terminate.
<br>
<br>To be quite specific, an algorithm will terminate if it does not take infinite time. (i.e. it takes finite time).
<br>
<br>So it's important to distinguish bounded/unbounded and finite/infinite.
<br>
<br>In this case, the solutions provided present an unbounded *finite* solution to the problem.
<br>
<br>As scott astutely pointed out. The fun behind this problem is trying to think deeply about the problem and to be rigorous in coming up with a solution.
<br>
<br>It is also interesting to think about the actual implementations as well though and to consider if they woudl be viable. And, as scott excellently showed. The *expected* number of rounds necessary for this to terminate is 4/3s.
<br>
<br>So it would be quite simple to take any of these algorithms, convert them to actual code, and expect them to work excellently in practise. In the end, the expected big-O is O(4/3) (i.e. O(1)), and you really don't get much better than that when coming up with real world algorithms.
<br>
<br>Hope you guys had fun and found it as much of a mind bender as i did.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=455191" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#455054Tue, 23 Aug 2005 14:27:35 GMT91d46819-8472-40ad-a661-2c78acb4018c:455054damien mortonMalio - yes, your algorithm is basically correct (though your code is awkward - using a property IsHeads instead of a function is bad style).
<br>
<br>Flip a coin N times to create an N bit integer, then mod 3 to determine which of the 3 choices are selected. One choice will be advantaged by one part in 2^N.
<br>
<br>Contrast this with the probablistic approach, which does pairs of flips to create numbers in the range 0..3, and terminates when a number in the range 0..2 is created. This requires an average of 8/3 coin flips to produce a result, and is fair to one part in 4^N, where N is the limit to the number of flip pairs you are prepared to consider. The average number of flips requied for a result is independant of the limit N, where N is large.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=455054" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#455041Tue, 23 Aug 2005 13:15:47 GMT91d46819-8472-40ad-a661-2c78acb4018c:455041MaLioWas I right? I'm most curious ...
<br>
<br>MaLio<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=455041" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#454895Tue, 23 Aug 2005 05:12:13 GMT91d46819-8472-40ad-a661-2c78acb4018c:454895CyrusNAnd scott wins the internet.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=454895" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#454831Tue, 23 Aug 2005 02:20:58 GMT91d46819-8472-40ad-a661-2c78acb4018c:454831MaLioHi
<br>
<br>what about converting the results from heads/tails trial to an int? [as in SelectNextItem() below]. The test code I left in as I used it for evaluation, and the chances of a, b or c beeing selected should be very close to equal (that is of course if I am not mistaken ;-). Termination is guaranteed after 8 'flips' in this code.
<br>
<br>MaLio
<br>
<br>
<br>namespace HeadsTailsOutcomes {
<br> /// <summary>
<br> /// Summary description for SelectionTest.
<br> /// </summary>
<br> class SelectionTest {
<br>
<br> // number of distinct items
<br> private const int NUM_ITEMS = 3;
<br> // number of iterations for testing
<br> private const int NUM_ITERATIONS = 100000;
<br> // random number generator
<br> private static System.Random _Random = new System.Random();
<br>
<br> /// <summary>
<br> /// Main
<br> /// </summary>
<br> static void Main(string[] args) {
<br>
<br> int[] items = new int[NUM_ITEMS];
<br>
<br> for (int iteration = 0; iteration < NUM_ITERATIONS; iteration++) {
<br> items[SelectNextItem()]++;
<br> }
<br>
<br> for (int index = 0; index < NUM_ITEMS; index++) {
<br> System.Console.WriteLine("{0} has {1}", index, items[index]);
<br> }
<br>
<br> System.Console.WriteLine();
<br> System.Console.ReadLine();
<br> }
<br>
<br> // SelectNextItem
<br> public static int SelectNextItem() {
<br>
<br> int evaluator = 0;
<br>
<br> for (int i = 1; i < 9; i++) {
<br> if (IsHeads) {
<br> evaluator |= (1 << i);
<br> }
<br> }
<br>
<br> return evaluator % NUM_ITEMS;
<br> }
<br>
<br> // IsHeads
<br> private static bool IsHeads {
<br> get {
<br> return ((_Random.Next(int.MaxValue) % 2) == 0);
<br> }
<br> }
<br> }
<br>}
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=454831" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#454240Sun, 21 Aug 2005 22:11:50 GMT91d46819-8472-40ad-a661-2c78acb4018c:454240locBy the way, I really like the helpful posts you have contributed, Scott. <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=454240" width="1" height="1">re: Heads, or Tails?http://blogs.msdn.com/b/cyrusn/archive/2005/08/12/450733.aspx#454237Sun, 21 Aug 2005 22:05:51 GMT91d46819-8472-40ad-a661-2c78acb4018c:454237locScott, I fully aware that he asked for a perfectly fair solution. I had admitted that it's not possible to come up with.
<br>
<br>My last solution is just kind of a bonus answer outside of his question, like "hey since we can't do it, maybe we can do this (if we ever had to) because it's very close to what you asked". =)<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=454237" width="1" height="1">