Skip to main content
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