Announcement

Collapse
No announcement yet.

A really neat riddle...

Collapse
This topic is closed.
X
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • A really neat riddle...

    Really neat "bar game" mathematics-type riddle from the 528 website. This is a non political post.

    http://fivethirtyeight.com/features/...this-bar-game/

    I know what my answer to the riddle would be...I want to know what yours is.

    If you don't wanna click the link, here's the riddle:

    Consider a hot new bar game. It’s played with a coin, between you and a friend, on a number line stretching from negative infinity to positive infinity. (It’s a very, very long bar.) You are assigned a winning number, the negative integer -X, and your friend is assigned his own winning number, a positive integer, +Y. A marker is placed at zero on the number line. Then the coin is repeatedly flipped. Every time the coin lands heads, the marker is moved one integer in a positive direction. Every time the coin lands tails, the marker moves one integer in a negative direction. You win if the coin reaches -X first, while your friend wins if the coin reaches +Y first. (Winner keeps the coin.)

    How long can you expect to sit, flipping a coin, at the bar? Put another way, what is the expected number of coin flips in a complete game?
    Last edited by mjr; 07-18-2016, 02:32 PM.
    Skilled programmers aren't cheap. Cheap programmers aren't skilled.

  • #2
    I suppose it would depend on the numbers you get. The vague remains of Probability lessons back in high school are yelling at me that the number of heads and tails will match, given a large enough number of flips, so a game could theoretically extend indefinitely. Real life shows slight differences which could push it either way (size, shape of coin and how worn it is; the person doing the flipping; air movement; etc). It also depends on if -x and +y are equidistant from zero. If we're talking about -3 and +500, I'd bet on -x to win. As for how long...? Short of the indefinite scenario above -- for the numbers I mentioned, a few minutes to an hour., I suppose.
    "For a musician, the SNES sound engine is like using Crayola Crayons. Nobuo Uematsu used Crayola Crayons to paint the Sistine Chapel." - Jeremy Jahns (re: "Dancing Mad")
    "The difference between an amateur and a master is that the master has failed way more times." - JoCat
    "Thinking is difficult, therefore let the herd pronounce judgment!" ~ Carl Jung
    "There's burning bridges, and then there's the lake just to fill it with gasoline." - Wiccy, reddit
    "Retail is a cruel master, and could very well be the most educational time of many people's lives, in its own twisted way." - me
    "Love keeps her in the air when she oughta fall down...tell you she's hurtin' 'fore she keens...makes her a home." - Capt. Malcolm Reynolds, "Serenity" (2005)
    Acts of Gord – Read it, Learn it, Love it!
    "Our psychic powers only work if the customer has a mind to read." - me

    Comment


    • #3
      Unless both players have 1 as their number, the game could go on forever. If I had to guess, you would add up each players number and multiply by 2 for the expected number of flips in a game

      Comment


      • #4
        Quoth EricKei View Post
        I suppose it would depend on the numbers you get. The vague remains of Probability lessons back in high school are yelling at me that the number of heads and tails will match, given a large enough number of flips, so a game could theoretically extend indefinitely. Real life shows slight differences which could push it either way (size, shape of coin and how worn it is; the person doing the flipping; air movement; etc). It also depends on if -x and +y are equidistant from zero. If we're talking about -3 and +500, I'd bet on -x to win. As for how long...? Short of the indefinite scenario above -- for the numbers I mentioned, a few minutes to an hour., I suppose.
        I'm gonna write a quick and dirty program to test a hypothesis, but my "theory" as far as some of this goes is as follows:

        Assume player X gets 2 as their "random" number, and player Y gets -2 (work with me, here).

        So, now let's say that the pointer is at 0, and the first flip is heads. That moves the pointer 1 in the positive direction, giving player X an advantage now. Because his probability of winning is now 1/2, no real change from where player X started, since both player X and player Y started off with 1/2 probability of winning, given 2 and -2 as the numbers. Given that, player Y must now "win" 3 flips instead of two, and player Y must win the second flip, because player Y's probability of winning has now been reduced. Player Y must, at a minimum, win flip 2 to "reset" the pointer to 0, which would then give both players a 1/2 probability of winning, since each flip is a discrete event.
        Last edited by mjr; 07-19-2016, 01:32 PM.
        Skilled programmers aren't cheap. Cheap programmers aren't skilled.

        Comment


        • #5
          So I wrote and executed my program. I obviously couldn't use infinity, so I used 10,000 as the "max" numbers for X and for Y.

          I did 10,000 trials, with the following results:

          Max X distance: 9,998
          Max Y distance: 10,000

          Min X and Min Y were both 1.

          The average range was 9984.506

          Minimum Range: 134
          Maximum Range: 19,880

          Average X distance: 4,991.3842
          Average Y distance: 4,933.12

          So there, Y had a slightly shorter average distance to "win".

          X won 49.52% of the time (4,952 wins) and Y won 50.48% of the time.

          The maximum number of flips was 518,964,263. Oddly enough, the min flips was 1.

          The maximum flips had a range of 16,881, and X won it.

          Assuming 1 flip per second, that's approximately 16.445 years, nonstop, of coin flips before someone wins.

          And that's just limiting the range from -10,000 to 10,000.
          Skilled programmers aren't cheap. Cheap programmers aren't skilled.

          Comment


          • #6
            Oddly enough, the min flips was 1
            Well, yeah...unless I'm missing something (which is very possible...math beyond the "advanced geometry" level (my school called it "Analysis" is out of my depth)) -- You stated that the minimum values for X and Y were both 1 (presumably, you mean -1 for Y and 1 for X). This means that, in theory, a single flip could decide the game if the numbers were something like -1 and 9876.
            "For a musician, the SNES sound engine is like using Crayola Crayons. Nobuo Uematsu used Crayola Crayons to paint the Sistine Chapel." - Jeremy Jahns (re: "Dancing Mad")
            "The difference between an amateur and a master is that the master has failed way more times." - JoCat
            "Thinking is difficult, therefore let the herd pronounce judgment!" ~ Carl Jung
            "There's burning bridges, and then there's the lake just to fill it with gasoline." - Wiccy, reddit
            "Retail is a cruel master, and could very well be the most educational time of many people's lives, in its own twisted way." - me
            "Love keeps her in the air when she oughta fall down...tell you she's hurtin' 'fore she keens...makes her a home." - Capt. Malcolm Reynolds, "Serenity" (2005)
            Acts of Gord – Read it, Learn it, Love it!
            "Our psychic powers only work if the customer has a mind to read." - me

            Comment


            • #7
              Another question is: How long will you try to solve this riddle before giving up?
              "I don't have to be petty. The Universe does that for me."

              Comment


              • #8
                This particular problem is known as a "simple symmetric random walk on a one-dimensional lattice". There's plenty of literature on the subject.

                The "expected mean" of a long series of coin flips is indeed zero. However, the "expected translation distance" is what the problem is asking for - or rather, the number of steps N for which the expected translation distance matches the two limits. This turns out to be proportional to the square of the limits' magnitudes.

                One way to visualise this is by using Pascal's Triangle. The coin will always be on an even integer on even N (given that zero is an even number), and an odd integer on odd N. Pascal's Triangle sums the possible paths to a given coin position at each N. You simply extend Pascal's Triangle until the sum of possibilities at-or-outside the limits is at least equal to the sum of those inside the limits. This is vastly more efficient to calculate than by running explicit coin-flipping trials.

                Actually, using Pascal's Triangle exactly as above does lead to an inaccuracy, because it doesn't account for paths which reach the limit but then regress towards zero. But it is straightforward (and more memory efficient) to modify the calculation to account for this. Also, you should use high-precision floating-point to run the calculation, as word-sized integers in the middle of the triangle will probably overflow after only a few dozen rows.

                Here's a Python script which does exactly that:

                Code:
                #!/usr/bin/python3 -O
                
                import sys
                
                limitA = -int(sys.argv[1])
                limitB =  int(sys.argv[2])
                
                len = 1 + limitB - limitA
                left = 0
                right = len-1
                sumAB = 0.0
                sumIN = 1.0
                N = 0
                
                triangle = [0.0] * len
                triangle[-limitA] = 1.0
                
                while sumAB < sumIN:
                	N += 1
                	sumIN = 0.0
                
                	triangle[0] *= 2
                	triangle[right] *= 2
                
                	if ((limitA ^ N) & 1) == 0:
                		triangle[0] += triangle[1]
                		for i in range(2,right,2):
                			triangle[i] = triangle[i-1] + triangle[i+1]
                			sumIN += triangle[i]
                		if (right & 1) == 0:
                			triangle[right] += triangle[right-1]
                	else:
                		for i in range(1,right,2):
                			triangle[i] = triangle[i-1] + triangle[i+1]
                			sumIN += triangle[i]
                		if (right & 1) == 1:
                			triangle[right] += triangle[right-1]
                
                	sumAB = triangle[left] + triangle[right]
                
                print("expected N = " + str(N))
                print("expected probability A wins by then: " + str(triangle[left] * 100.0 / (sumAB + sumIN)) + "%")
                print("expected probability B wins by then: " + str(triangle[right] * 100.0 / (sumAB + sumIN)) + "%")
                
                if(triangle[left] < triangle[right]):
                	print("B is " + str(triangle[right] / triangle[left]) + " times as likely to win as A")
                elif(triangle[left] > triangle[right]):
                	print("A is " + str(triangle[left] / triangle[right]) + " times as likely to win as B")
                else:
                	print("A and B have equal chance to win")
                Code:
                $ python3 randomwalk.py 42 50
                expected N = 132
                expected probability A wins by then: 52.99678910685934%
                expected probability B wins by then: 0.16454586469270896%
                A is 322.07913098169547 times as likely to win as B
                Interestingly, 322 is very close to 2^((50-42) + 1/3).
                Last edited by Chromatix; 07-20-2016, 10:33 PM.

                Comment

                Working...
                X