Timeline for Generalization of Penney's game (Penney's paradox)
Current License: CC BY-SA 4.0
25 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jul 27, 2018 at 8:39 | comment | added | joriki | @usul: The apparent tie is a tie by symmetry; Bob's sequences are the complements of Alice's sequences. Bob can always tie in this way unless Alice chooses two complementary sequences. An interesting question might be whether Alice can choose complementary sequences such that Bob can't even tie. | |
Jul 20, 2018 at 12:42 | comment | added | usul | That is to say: as far as I can tell, if Alice plays (HTTT, TTTH), then Bob's best legal response is (HHHT, THHH), resulting in an apparent 50% win rate. If this is correct, then it shows Bob does not have a winning strategy for k=4. | |
Jul 18, 2018 at 16:12 | comment | added | David G. Stork | It is not permissible for Bob to choose the same sequence as Alice (TTTH); we cannot allow ties. | |
Jul 18, 2018 at 12:13 | comment | added | usul | For $k=4$, suppose Alice plays (HTTT, TTTH). My simulations say that if Bob is allowed to play (HHTT. TTTH), where he's copied one of Alice's pair, then he can win 58% of the time. But if this is disallowed as per the rules, then his best strategy seems to be (HHHT, THHH) resulting in (apparently) a tie. | |
Jul 18, 2018 at 7:57 | comment | added | zabroshenie goroda | Suppose we identify the set of $k$-bit sequences with $\{0,...,2^k-1\}$ in the natural way. It seems there is a function from the set of infinite binary strings with starting points and in which every $k$-bit sequence appears at least once to the symmetric group on $\{0,...,2^k-1\}$, and it naturally gives rise to a probability distribution on such a set of permutations. Perhaps the original question could be asked for any probability distribution? | |
Jul 18, 2018 at 0:59 | comment | added | zabroshenie goroda | Seems there are some variations of this problem in the $n$-level game. (A and B each pick $n$ distinct $k$ bit sequences, all $2n$ sequences distinct.) The most natural definition of a win for B is the last of the $2n$ sequences to appear belongs to A, but even then there are ${2n-1 \choose n}$ possibilities that the choices of A and B may appear in. Perhaps some variations could fix some subset of these possibilities as winning for B. | |
Jul 18, 2018 at 0:00 | comment | added | David G. Stork | Excellent point. Makes sense. I would have thought that the largest odds ratio would show up, though. I will try A: HHH and TTT, B: HTT and THH. | |
Jul 17, 2018 at 23:57 | comment | added | Gerry Myerson | The intransitivity in the one-level game only shows up for $k\ge3$. Perhaps the calculations of @usul are telling us that intransitivity in the two-level game doesn't show up at $k=3$, but that might just mean we need to look at some larger $k$ to find it. | |
Jul 17, 2018 at 20:06 | comment | added | usul | Clear and consistent with my current code. Again my comment was not clear enough! :) (I had tried to edit it, but passed the 5 minute window) | |
Jul 17, 2018 at 18:39 | comment | added | David G. Stork | In the two-level game winning is the FIRST to get BOTH his sequences. They need not both be before both the opponent’s sequences. If A then B then A then B... A wins. Clear? | |
Jul 17, 2018 at 17:56 | comment | added | usul | oops, I was unclear. I refer not to the original problem but to your question about two-level generalization. When I simulate Alice's choice of the two sequences (THH, HHT), I cannot find any pair of length-3 sequences $(x,y)$ for Bob such that, with probability noticeably over 0.5, both $x$ and $y$ appear as subsequences prior to both TTH and HHT. | |
Jul 17, 2018 at 16:42 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 573 characters in body
|
Jul 17, 2018 at 16:18 | history | edited | David G. Stork | CC BY-SA 4.0 |
[Edit removed during grace period]
|
Jul 17, 2018 at 16:10 | comment | added | David G. Stork | @usul: My computer simulations confirm the 2:1 odds ratio described in the wikipedia page. Please check that page and your code. Also, on that page there is a helpful "intuitive" explanation why the non-transitive dominance woks. | |
Jul 17, 2018 at 15:34 | comment | added | David G. Stork | @usul: Please check your code and assumptions. As the table (Analysis of the three-bit game) in the linked wikipedia page states, the odds in favor of $TTH$ over $THH$ are 2:1. (I'll run my own simulations to confirm too.) . en.wikipedia.org/wiki/Penney%27s_game | |
Jul 17, 2018 at 10:42 | comment | added | usul | My brute-force simulation for k=3 does not find that Bob can beat Alice's pair THH, HHT. None of his strategies beat 50% with statistical significance in a million trials. (It is possible he has a slight edge but more trials are needed to detect it.) | |
Jul 17, 2018 at 5:33 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 3 characters in body
|
Jul 16, 2018 at 23:49 | history | edited | David G. Stork | CC BY-SA 4.0 |
edited body
|
Jul 16, 2018 at 23:46 | history | edited | YCor |
edited tags
|
|
Jul 16, 2018 at 23:45 | history | edited | David G. Stork | CC BY-SA 4.0 |
edited body
|
Jul 16, 2018 at 23:41 | history | edited | David G. Stork | CC BY-SA 4.0 |
deleted 1 character in body
|
Jul 16, 2018 at 23:12 | history | edited | David G. Stork | CC BY-SA 4.0 |
deleted 1 character in body
|
Jul 16, 2018 at 23:00 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 44 characters in body
|
Jul 16, 2018 at 22:54 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 6 characters in body
|
Jul 16, 2018 at 22:46 | history | asked | David G. Stork | CC BY-SA 4.0 |