Here's an interesting little scenario.

You get challenged to a game of coin toss. Both players pick a sequence of coin toss results (heads or tails). The coin is repeatedly tossed until the sequence for one of the players occurs. The loser pays the winner a dollar. You'd assume that you each have an equal chance of winning. However, using two little "tricks" you can tip the odds in your favour. The first trick is to always choose second. If you can manage this then your strategy is as follows:

Your first choice should be the opposite of your opponent's second choice.
Your second and third choices should be the same as your opponents first two choices.

The top three buttons are for player A, the bottom three for player B. You can set the choices manually by clicking the buttons. If you click on "Choose B for me" then player B will be set to the choices based on the above strategy. Each time you click "Start" a new game is played with the coin tosses and game results displayed in the listbox.

For the GUI, the top three buttons are named Button1, Button2 and Button3. The bottom three are Button4, Button5, and Button6. The remaining three controls are (buttons) btnChoose, btnStart, and (listbox) lbxResults.

Edited 9 Months Ago by Reverend Jim: typo

Attachments clip-0009.jpg 25.73 KB
Public Class Form1

    Private aWon As Integer = 0     'number of games won by player A
    Private bWon As Integer = 0     'number of games won by player B

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load

        'Assign common handler to toggle choice buttons

        For i As Integer = 1 To 6
            Dim btn As Button = Me.Controls("Button" & i)
            AddHandler btn.Click, AddressOf Button_Click
        Next

    End Sub

    Private Sub btnStart_Click(sender As System.Object, e As System.EventArgs) Handles btnStart.Click

        'Repeat coin tosses until one player wins

        Dim rnd = New Random()
        Dim ht() As Char = {"H", "T"}
        Dim res(2) As Char

        'Seed with three initial tosses

        For i As Integer = 0 To 2
            res(i) = ht(rnd.Next(0, 2))
        Next

        Dim done As Boolean = False

        Do Until done

            lbxResults.Items.Add(res(0) & "-" & res(1) & "-" & res(2))

            Select Case True
                Case CheckWin(1, res)
                    lbxResults.Items.Add("Player A wins")
                    aWon += 1
                    done = True
                Case CheckWin(4, res)
                    lbxResults.Items.Add("Player B wins")
                    bWon += 1
                    done = True
            End Select

            res(0) = res(1)
            res(1) = res(2)
            res(2) = ht(rnd.Next(0, 2))

            'Keep most recent results in view (scroll to bottom)

            lbxResults.SelectedIndex = lbxResults.Items.Count - 1

        Loop

        Me.Text = "A - " & aWon & " games    " & "B - " & bWon & " games"

    End Sub

    Private Sub Button_Click(sender As System.Object, e As System.EventArgs)

        'Toggle H or T in a choice button

        Dim btn As Button = sender
        btn.Text = IIf(btn.Text = "H", "T", "H")

    End Sub

    Private Sub btnChoose_Click(sender As System.Object, e As System.EventArgs) Handles btnChoose.Click

        'Set player B to optimal choices

        Button4.Text = IIf(Button2.Text = "H", "T", "H")    'Opposite of player A 2nd choice - Feb 22 corrected typo Button3 -> Button2
        Button5.Text = Button1.Text                         'Same as player A 1st choice
        Button6.Text = Button2.Text                         'Same as player A 2nd choice

    End Sub

    Private Function CheckWin(start As Integer, seq() As Char) As Boolean

        'Check if the next 3 buttons match the given sequence

        For i As Integer = 0 To 2
            Dim btn As Button = Me.Controls("Button" & i + start)
            If btn.Text <> seq(i) Then Return False
        Next

        Return True

    End Function

End Class

Computer languages in which I have developed applications

Assembler (DEC, Data General, 8080, GE, SEL, IBM 360)
WATFOR (Waterloo FORTRAN)
FORTRAN (SEL)
APL (IBM 360, IBM VSAPL)
PL/1
C/C++
Borland Paradox
VB.net
vbScript

When tossing a coin we can (and will) make following assumptions:
1. the result will allways only be tails or heads
2. the coin is fair i.e. the probability of tails is the same as heads, P(T) <=> P(H)
3. the coin tossing is stateless operation i.e. the coin does not and can not "remember" last result
4. from the previous assumptions follows that given any sequence of coin tossing results, the next toss has the probability P(T) <=> P(H)

Let's say that player A chooses a sequence T, T and T. Tossing this sequence has, according classic probability theory, likelihood P(T) * P(T) * P(T), (or 1/2 * 1/2 * 1/2 = 1/(2^3) = 1/8 because P(T) <=> P(H) and the coin is fair as stated above).

Using the given strategy player B chooses a sequence: H, T and T. Tossing this sequence has the probability
P(H) * P(T) * P(T) or 1/2 * 1/2 * 1/2 = 1/(2^3) = 1/8 which is exactly the same as the probability of the player A's sequence.

From this follows that
1. using the strategy, how to choose the sequence, does not increase the probability of that sequence
2. to always choose second does not help i.e. increase the probability of the sequence

Am I right?

I don't know the math, but by running the code you can see that player B will win either by a little or by a lot. You can modify the code, for example, so that each click on Start playes 100 or 1000 games and check the results.

It's one of those problems where the "obvious" solution is not the correct solution. Take the following problem, for example. Let's assume, for the moment, that the Earth is perfectly round and flat. Imagine that you could build a solid ring that touches the surface at every point along the equator. The ring would be (if Google is correct) 40,075 km long. Now let's imagine that you want to enlarge the ring so that it is one meter above the surface at every point. Without doing the calculation, approximately how much material (length) would you have to add to the ring? would you guess 100 meters?, 1000 meters?, 10,000 meters? The actual answer is just over 6 meters. It doesn't seem logical but that's the answer you get if you do the math. Your common sense tells you one answer and the math, another.

Picture it this way. Imagine the Earth is a cube whose perimiter is 40,075 km, If you cut the ring at the corners and lift the four segments one meter up, all you would have to add is an arc of material at the four corners. The arc has a radius of one meter and the four corners form a circle of diameter 2 meters. The circumference of that circle is 2 * 3.1415 or just over 6 meters. But the earth isn't a cube. Well then, make it an octagon (in profile). The segments you have to add still combine to make a circle. This is true no matter how many sides you use.

Being deeply sceptical about this, and agreeing with Teme64, I hacked together a little Java version of the logic (no GUI needed), ran 10000 iterations with all 8 possible "A" choices and guess what - absolutely no consistent or significant difference in the number of wins. Here's the code in case I made a mistake...

public class CoinTosser {

    public static void main(String[] args) {

        ThreeTosses first, second;

        for (int i = 0; i <= 7; i++) { // try all 8 possible choices
            first = new ThreeTosses((i & 1) == 1, (i & 2) == 2, (i & 4) == 4);

            second = first.optimumResponse();

            int firstWins = 0, secondWins = 0;

            for (int j = 0; j < 10000; j++) {
                ThreeTosses random = ThreeTosses.newRandomResult();
                if (random.equals(first)) {
                    firstWins++;
                }
                if (random.equals(second)) {
                    secondWins++;
                }
            }
            System.out.print(first + " vs " + second);
            System.out.println(" : " + firstWins + "  " + secondWins);
        }
    }

}

class ThreeTosses {

    private static java.util.Random r = new java.util.Random();

    final public boolean a, b, c;

    ThreeTosses(boolean a, boolean b, boolean c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public static ThreeTosses newRandomResult() {
        return new ThreeTosses(r.nextBoolean(), r.nextBoolean(), r.nextBoolean());
    }

    public ThreeTosses optimumResponse() {
        return new ThreeTosses(!b, a, b);
    }

    public boolean equals(ThreeTosses other) {
        return a == other.a && b == other.b && c == other.c;
    }

    @Override
    public String toString() {
        return a + "," + b + "," + c;
    }
}

There was a small typo in my code (corrected in the original post). In the button_Choose handler the line should be

Button4.Text = IIf(Button2.Text = "H", "T", "H")    'Opposite of player A 2nd choice

I had the comment right but made a typo in the code. Button3 should have been Button2.

@James - try your code again with the corrected line. My results show an advantage for player B. Running a thousand trials with each configuration I get the following results

 A   B  AWIN BWIN 
HHH THH  232  768
HHT THH  348  652
HTH HHT  401  599
HTT HHT  444  556
THH TTH  378  622
THT TTH  377  623
TTH HTT  325  675
TTT HTT  235  765

Edited 9 Months Ago by Reverend Jim

I don't think I had that particular bug in my code anyway, and here are my reuslts for 1000 trials of each

false,false,false vs true,false,false = 120 vs 122
true,false,false vs true,true,false = 125 vs 126
false,true,false vs false,false,true = 126 vs 137
true,true,false vs false,true,true = 133 vs 106
false,false,true vs true,false,false = 130 vs 146
true,false,true vs true,true,false = 122 vs 123
false,true,true vs false,false,true = 141 vs 114
true,true,true vs false,true,true = 109 vs 124

With 3 coins you would expect a 1/8 hit rate against any given choice, as seen above.
Your results show vastly too many hits. No amount of majic will make three tosses come up THH 768/1000 times. Sorry, but I'm sure you have a bug somewhere.
Anyone else try this?

<EDIT>

Sorry - I misunderstood your definition of "trial". Here's a typical run usig your def'n

T,T,T vs H,T,T = 504 vs 496
H,T,T vs H,H,T = 483 vs 517
T,H,T vs T,T,H = 513 vs 487
H,H,T vs T,H,H = 477 vs 523
T,T,H vs H,T,T = 519 vs 481
H,T,H vs H,H,T = 490 vs 510
T,H,H vs T,T,H = 495 vs 505
H,H,H vs T,H,H = 516 vs 484

supporting code (re-written) follows

public class CoinTosser {

    public static void main(String[] args) {

        ThreeTosses first, second;

        for (int i = 0; i <= 7; i++) { // try all 8 possible choices
            first = new ThreeTosses((i & 1) > 0 ? Coin.H : Coin.T,
                    (i & 2) > 0 ? Coin.H : Coin.T,
                    (i & 4) > 0 ? Coin.H : Coin.T);

            second = first.optimumResponse();

            int firstWins = 0, secondWins = 0;

            while (firstWins + secondWins < 1000) {
                ThreeTosses random = ThreeTosses.nextRandom();
                if (random.equals(first)) {
                    firstWins++;
                }
                if (random.equals(second)) {
                    secondWins++;
                }
            }
            System.out.print(first + " vs " + second);
            System.out.println(" = " + firstWins + " vs " + secondWins);
        }
    }

    enum Coin {

        H, T;
        private static java.util.Random r = new java.util.Random();

        public static Coin nextRandom() {
            return r.nextBoolean() ? H : T;
        }

        public Coin flip() {
            return (this == H) ? T : H;
        }
    }

    static class ThreeTosses {

        final public Coin a, b, c;

        ThreeTosses(Coin a, Coin b, Coin c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        public static ThreeTosses nextRandom() {
            return new ThreeTosses(Coin.nextRandom(), Coin.nextRandom(), Coin.nextRandom());
        }

        public ThreeTosses optimumResponse() {
            return new ThreeTosses(b.flip(), a, b);
        }

        public boolean equals(ThreeTosses other) {
            return a == other.a && b == other.b && c == other.c;
        }

        @Override
        public String toString() {
            return a + "," + b + "," + c;
        }
    }
}

Edited 9 Months Ago by JamesCherrill

I don't speak java (luddite, I suppose). In case there is a misunderstanding about the tosses, when I do the tosses I don't generate three new tosses at each pass. i throw out the oldest toss and generate one new toss. I start by seeding three tosses (1,2,3) and compare those to both players. Then I generate a new toss (2,3,4) and compare those, then (3,4,5), (4,5,6), etc.

It looks to me that you generate three new tosses on every turn which would signficantly change the parameters of the game.

The idea (I suppose, from a street grifter point of view) is to present a game of chance that appears to have even odds but which is weighted in favour of one player.

Edited 9 Months Ago by Reverend Jim

OK, I tried generating each trial as (sorry, did some renaming since last code posted)

        ThreeCoins nextIncrementalRandom() {
            return new ThreeCoins(b, c, Face.nextRandom());
        }

and got the same results - no statistical difference at all.

We desparately need some whone who speaks both languages so they can spot what we're doing differently.

Edited 9 Months Ago by JamesCherrill

OK, got the answer. You have to rotate the throws as you describe until someone wins, then throw a complete new set of 3. With those rules I get

T,T,T vs H,T,T = 122 vs 878
H,T,T vs H,H,T = 309 vs 691
T,H,T vs T,T,H = 336 vs 664
H,H,T vs T,H,H = 275 vs 725
T,T,H vs H,T,T = 263 vs 737
H,T,H vs H,H,T = 354 vs 646
T,H,H vs T,T,H = 349 vs 651
H,H,H vs T,H,H = 144 vs 856
Final score: A won 2152, B won5848



public class CoinTosser {

    public static void main(String[] args) {

        int aTotal = 0, bTotal = 0;

        for (ThreeCoins playerA : ThreeCoins.allPossibleCombinations()) {

            ThreeCoins playerB = playerA.optimumResponse();

            int aWins = 0, bWins = 0;

            ThreeCoins random = ThreeCoins.nextRandom();

            boolean weHaveAWin = false;
            while (aWins + bWins < 1000) {
                random = random.nextIncrementalRandom();
                if (random.equals(playerA)) {
                    weHaveAWin = true;
                    aWins++;
                }
                if (random.equals(playerB)) {
                    weHaveAWin = true;
                    bWins++;
                }
                if (weHaveAWin) {
                    random = ThreeCoins.nextRandom();
                    weHaveAWin = false;
                }
            }
            System.out.print(playerA + " vs " + playerB);
            System.out.println(" = " + aWins + " vs " + bWins);
            aTotal += aWins;
            bTotal += bWins;
        }
        System.out.println("Final score: A won " + aTotal + ", B won" + bTotal);
    }

    enum Face {

        H, T;

        private static java.util.Random r = new java.util.Random();

        static Face nextRandom() {
            return r.nextBoolean() ? H : T;
        }

        Face flip() {
            return (this == H) ? T : H;
        }
    }

    static class ThreeCoins {

        final Face a, b, c; // immutable class

        ThreeCoins(Face a, Face b, Face c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        static ThreeCoins[] allPossibleCombinations() {
            ThreeCoins[] all = new ThreeCoins[8];
            for (int i = 0; i <= 7; i++) {
                all[i] = new ThreeCoins((i & 1) > 0 ? H : T,
                        (i & 2) > 0 ? H : T,
                        (i & 4) > 0 ? H : T);
            }
            return all;
        }

        static ThreeCoins nextRandom() {
            return new ThreeCoins(Face.nextRandom(), Face.nextRandom(), Face.nextRandom());
        }

        ThreeCoins nextIncrementalRandom() {
            return new ThreeCoins(b, c, Face.nextRandom());
        }

        ThreeCoins optimumResponse() {
            return new ThreeCoins(b.flip(), a, b);
        }

        boolean equals(ThreeCoins other) {
            return a == other.a && b == other.b && c == other.c;
        }

        @Override
        public String toString() {
            return a + "," + b + "," + c;
        }
    }
}

I think I know why as well....

A is looking for a,b,c
B is looking for -b,a,b
the trials are rotating as described.

For A to win you need to get a,b,c
The previous try will have been x,a,b - which B has a 50/50 chance of matching.
Ie for any sequence that is a match for A, B has a 50/50 chence of matching it on the previous turn.

Conversely for B to win you need to get -b,a,b
The previous try will have been x,-b,a - which A has zero chance of winning.

Its the rolling "random" rolls, combined with A= a,b,x and B= y,a,b that gives B the edge in matching on the turn before A can match, but not ViceVersa.

Very neat.

The origin of the problem is the Random object itself. Suppose our Random object outputs only 0's and 1's (just like tossing a coin gives only heads and tails). Ideally Random object would somehow output a sequence that meets the conditions

  1. probability of 0 is equal to the probability of 1 ("fair coin")
  2. given any output sequence of 0's and 1's the probability of getting next a '0' is equal to the probability of getting a '1'. That is, knowing any number of previously outputted 0's and 1's does not change the predictability of the next output. On the other words, Random object does neither "remember" what the previous output was nor does it use any previous output to generate next output. This would make Random object stateless (like a coin).

So, how does this Random object "produce" these random 0's and 1's? The answer is: it does not produce anything random. It produces pseudo-random 0's and 1's.

The computers are deterministic like they should be. Algorithms ("computer programs") are deterministic by definition. This is why our Random object is also deterministic and not "random" in statistical sense. When someone wrote the actual code for our Random object, he or she chose an algorith that "mimics" randomness i.e. the outputted values have as uniform distribution as possible and knowing any number of previously outputted values keeps the predictability of the next output as small as possible.

This applies to C#, Java or any programming language which has some sort of Random object or Random function. The best you can get is pseudo-random numbers.

Choosing our three heads and tails, like in the first post, may give a slightly better chance to win. But that is the result of the pseudo-randomness, the algorith used in the Random object or there may even be a bug in the Random object's code. Changing the code to Java simply changes "unfair coin" to another "unfair coin".

I'm sorry, but the "random" functions in major languages are not so terrible that they would give such significant non-random results. That's a complete red herring.

Please re-read my previous post. The first triple is random but the following sequence of triples is very highly corrolated. Any triple a,b,c will be followed by a triple b,c,x. This scam works by exploiting the correlation between successive trys. Because of the carefully chosen difference between A's and B's triples player B has a 50/50 chance of matching A's sequence one turn before A sees it, but A can never match B's sequence before B sees it.

So here are the expected odds:
A's sequence will appear 1 in 8 tries, but half of those will be captured by B in the previous round, so that's 1/16 for A and 1/16 for B
B's sequence will appear 1 in 8 tries, but all of these will be captured by B

So we would expect A to win 1/16 of the time, amd B to win 3/16.
Now here's my result from a run of 1,600,000 tries (200,000 each of A's possible sequences)

T,T,T vs H,T,T = 4999 vs 35027
H,T,T vs H,H,T = 20068 vs 40281
T,H,T vs T,T,H = 16418 vs 33462
H,H,T vs T,H,H = 11256 vs 33399
T,T,H vs H,T,T = 10956 vs 33051
H,T,H vs H,H,T = 16633 vs 33187
T,H,H vs T,T,H = 20056 vs 39915
H,H,H vs T,H,H = 5077 vs 35144
Final score: 1600000 tries, A won 105463, B won283466

That's very slightly better for A than my analysis, but the reason is probably that my analysis doesn't apply to the first one or two tries after a win (because then there's a new random triple, and the odds are 1/8 for both players).

Edited 9 Months Ago by JamesCherrill

When I test the random number generation (for 0, 1) against ten million tosses I compare the number of each result and see only (approximately) a 0.02% difference. In any case, as long as neither player is aware of any inbuilt bias toward either a heads or tails then both players are playing by the same rules. Therefore the difference in the probability of a win for A or B is not due to a problem with the random number generation.

@James - thanks for the analysis

The generation of random numbers is too important to be left to chance.
—Robert R. Coveyou

Edited 9 Months Ago by Reverend Jim

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.