Heads and Tails Game - Part 1 of 2

-
Let's suppose that we play the following game:
  1. Pick a sequence of heads (H) and tails (T). Any sequence, of a reasonable length, say 10
  2. Suppose your sequence is HTTHTHTHTT. Call this sequence O (for Opponent)
  3. The computer will then pick a random sequence of same length
  4. Let's suppose the sequence is THHHHTTHHT. Call this sequence C (for Computer)
  5. We'll then start tossing coins up randomly, in sequence
  6. The first sequence (O or C) to be generated wins a point. Notice that Ad Infinitum eventually O or C will be generated (assuming a reasonably random random-number generator)
  7. Repeat steps 5 and 6 for 1M (one million) times
  8. Whoever has the most points wins :)
We then play this game, and this is one of the results ("I" means the computer):

Well, I win!!! :)
You win 499610 times (or 49.961% of the total)
And I win 500390 times (or 50.039% of the total)

Well, pretty close, it could have gone either way, near 50% chance of win to each party. OK, let's try again but changing the computer's random string to something else, such as TTTTTHTTTT:

You win!!! :)
You win 660232 times (or 56.8951669889593% of the total)
And I win 500204 times (or 43.1048330110407% of the total)

Not that close anymore. Yet again changing to something random such as HTHTHHHHTT, we then have:

You win!!! :)
You win 687640 times (or 50.0058540388141% of the total)
And I win 687479 times (or 49.9941459611859% of the total)

Pretty even again.

I guess by now you're wondering: "so what, the probability of victory either way will approach 50% over time, this is a complete random game".

Well...

OK, now the computer will generate something slightly smarter. Now let's just say that the sequence C will be a function of the sequence O, or in other words C = F(O). I'll get to that function later on, but let's try again the same input for O = HTTHTHTHTT but this time C = F(O):

Well, I win!!! :)
You win 374722 times (or 37.4722% of the total)
And I win 625278 times (or 62.5278% of the total)

Wow!!! The computer now wins with a mind-blowing 62.5% of chances! This is starting to not look random anymore. OK, we then change our input from the previous O to something a little different: O = THHHTHHHTH. We run our machine again:

Well, I win!!! :)
You win 286820 times (or 28.682% of the total)
And I win 713180 times (or 71.318% of the total)

Wait a minute, 71% chance of victory is far from being "random"!! Let's bite the bullet and have something very unique for O, such as O = HHHHHHHHHH. Run it again:

Well, I win!!! :)
You win 498754 times (or 39.9148170615568% of the total)
And I win 750792 times (or 60.0851829384432% of the total)

Better, but still no chance - the computer's chance of winning is still > 60%. Let's then try a longer sequence, very long, with a truly random permutation, such as O = HTTHTHHHTHTTTHTTTHTHHHHTHHTHTHTHTTTTTHTHTHHHHHTHTHHHTH. After all, the longer the sequence, the more likely the results will converge to 50-50. OK, the results:

Well, I win!!! :)
You win 135462 times (or 13.5462% of the total)
And I win 864538 times (or 86.4538% of the total)

Wait, what?! 86% of winning chances for the computer?!? What's going on??? I mean, really, one could come up with any crazy formula as much as one wants, but at the end of the day, both my sequence and the computer's sequence are just sequences just like any other, and they should occur with the same probability. Sure, running the tests many times might results in some slight variations, but with such a long length and with 1M runs, surely it should converge to 50-50. This is what fundamental statistics would tell us.

Well, but F(O) is a special function! It does wonders, and sure enough it can bring the chances of winning to anywhere from 60% to 90%, but always way north of 50%.

How does F(O) work? Stay tuned for the next episode......

Marcelo



Comments

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

Hard Leetcode Problem: Grid Illumination

-
Image
Here is the problem:  https://leetcode.com/problems/grid-illumination/ On a  N x N  grid of cells, each cell  (x, y)  with  0 <= x < N  and  0 <= y < N  has a lamp. Initially, some number of lamps are on.   lamps[i]  tells us the location of the  i -th lamp that is on.  Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals ( similar to a Queen in chess ). For the i-th query  queries[i] = (x, y) , the answer to the query is 1 if the cell (x, y) is illuminated, else 0. After each query  (x, y)  [in the order given by  queries ], we turn off any lamps that are at cell  (x, y)  or are adjacent 8-directionally (ie., share a corner or edge with cell  (x, y) .) Return an array of answers.  Each value  answer[i]  should be equal to the answer of the  i -th query  queries[i] . Example 1: Input: N = 5 , lamps = [[0,0],[4,4]] , queries = [[1,1],[1,0]] Output: [1,0] Explanation: Before performing the first query we have both lamps [0
Read more