0
$\begingroup$

I was looking around this problem:

If two people randomly move in tic - tac - toe with random turns according to coin flips, what is the probability each wins (or that there is a draw)? In other words we fill an entire 3*3 matrix only according to coin toss. Intuitively it should be 50% for each player, but why?

SO we made 9 coin flips and we have for ex.(H,T,H,T,T,T,T,H,T) According to this values we fill a game board with XorO rispectivelly.

$\endgroup$
7
  • 2
    $\begingroup$ How are you populating the squares? "Heads is $X$" or something? If so then you have to compute the probability of a stalemate, call that $\psi$, in which case the answer is $\frac 12\times (1-\psi)$. $\endgroup$
    – lulu
    Nov 6, 2017 at 19:29
  • 2
    $\begingroup$ No, it should be less than $50\%$ because of draws. $\endgroup$ Nov 6, 2017 at 19:29
  • 1
    $\begingroup$ I don't see how this game is well-defined. Do we just proceed one square at a time, filling in $X$ or $O$ according to a coin flip, and continue until one side has three-in-a-row, or the board is full? $\endgroup$ Nov 6, 2017 at 19:34
  • $\begingroup$ It seems to me that $X$ should have an advantage. $\endgroup$
    – Doug M
    Nov 6, 2017 at 19:41
  • $\begingroup$ SO we made 9 coin flips and we have for ex.(H,T,H,T,T,T,T,H,T) According to this values we fill a game board with XorO rispectivelly. $\endgroup$ Nov 6, 2017 at 19:43

1 Answer 1

1
$\begingroup$

A tie can occur in the following ways.

First, we could get a board where nobody has 3-in-a-row. In that case, up to symmetry, the board must look one of the three tied positions you can achieve in tic-tac-toe:

X X O    X X O    X X O
O X X    O O X    O O X
X O O    X X O    X O X

There are $32$ boards in this category. For the first board, we can rotate it in $4$ ways, reflect it or not, and swap X with O or not, giving $16$ variations; for the second and third, reflections don't help (since they're symmetric) so we get $8$ variations of each.

Second, we could get a board where both players have one 3-in-a-row. No player can claim a diagonal: if that happens, there is no other 3-in-a-row for the other player to claim. Similarly, no player can claim both a vertical and a horizontal 3-in-a-row. So we are left with boards like this one:

X X X
O O O
X O O

There are $72$ boards in this category. We can choose in $2$ ways whether the 3-in-a-rows are vertical or horizontal. Once we do, we can permute the "win for X" line, the "win for O" line, and the third line in $3! = 6$ ways, and specify the outcomes along the third line in $2^3 - 2 = 6$ ways (it cannot be X X X or O O O, but any of the other outcomes are valid).

So the probability of a tie is $\frac{32 + 72}{2^9} = \frac{104}{512} = \frac{13}{64}$, leaving a probability of $\frac{51}{128}$ that X wins and a probability of $\frac{51}{128}$ that O wins. (Each of these is just over $39.8\%$.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .