Timeline for Guessing each other's coins
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2019 at 1:08 | comment | added | Claude Chaunier | Or are the two chosen coins discarded from their respective binary sequences before the next attempt ? Is Alice allowed to remember what her different choices for $a$ have been ? | |
| Apr 7, 2019 at 0:51 | comment | added | Claude Chaunier | Am I right in guessing that Alice and Bob lose the game if $A_b\ne B_a$ ? But they play again with the same binary sequences if $A_b=B_a=0$, with only that as added information ? Then a player's strategy is a function $f : \{0,1\}^{\mathbf{N}}\times\mathbf{N} \to \mathbf{N}$ that takes the number of past attempts into account, isn't it ? | |
| Apr 6, 2019 at 19:37 | history | edited | domotorp |
added puzzle tag
|
|
| Apr 4, 2019 at 20:50 | comment | added | Michael | @usul, I don't understand the "recurse to the next bit" part. Isn't game over on the 1st attempt? Maybe I don't understand the statement of the problem. It sounds to me that $P(A_b)=1/2$ and $P(B_a)=1/2$ and I don't see how they could be correlate, leading to $1/4$ being the win probability regardless of strategy. What am I missing here? | |
| Apr 4, 2019 at 19:41 | history | edited | Guillaume Aubrun | CC BY-SA 4.0 |
added 364 characters in body
|
| Apr 4, 2019 at 19:10 | comment | added | Sam Hopkins | I think it is worth editing the question to point out, as Édouard Maurel-Segala said, that this problem is explicitly studied in the paper: arxiv.org/abs/1407.4711 | |
| Apr 2, 2019 at 12:06 | comment | added | Édouard Maurel-Segala | By the way : here is another discussion on some closely related problems (if you accept that a problem on hats that comes in two colors can be translated into a coin problem) : blog.tanyakhovanova.com/2011/04/… | |
| Apr 2, 2019 at 8:17 | answer | added | Édouard Maurel-Segala | timeline score: 24 | |
| Mar 30, 2019 at 21:47 | answer | added | mihaild | timeline score: 16 | |
| Mar 30, 2019 at 14:33 | comment | added | Guillaume Aubrun | @usul that seems correct and it's a great observation. The reason for that is that, whatever the strategies, $\mathbf{P}(A_b=B_a=0)=\mathbf{P}(A_b=B_a=1)$, since each event $\{A_b=0\}$, $\{A_b=1\}$, $\{B_a=0\}$, $\{B_a=1\}$ has probability $1/2$. | |
| Mar 30, 2019 at 13:48 | comment | added | usul | By the way, if we just require the players' bits to match to win (so both finding a zero is also a win), is this the exact same problem with all probabilities doubled? Or is there a difference? | |
| Mar 30, 2019 at 13:40 | comment | added | usul | @student nice, here's another way: consider these cases for the first bits $(A_0,B_0)$ of the two sequences: (0,1), (1,0), (1,1). The players win $1/3$ of these equally-likely cases. In the fourth case (0,0), they recurse on the next bit. | |
| Mar 30, 2019 at 4:05 | history | edited | Guillaume Aubrun | CC BY-SA 4.0 |
added 1028 characters in body
|
| Mar 29, 2019 at 22:13 | comment | added | user114668 | I didn't understand $p = 1/3$ at first, so here goes: If $a < b$, then $B_a = 0$. If $a > b$, then $A_b = 0$. So the players win iff $a = b$, with probability $1/3$. The better strategies allow to get $a = b$ slightly wrong and still win. | |
| Mar 29, 2019 at 20:07 | comment | added | Guillaume Aubrun | That's because I used the following convention: say for N=3, if a player sees 000, he discards these bits and applies the same strategy recursively to the next 3 bits. If you don't use this trick, the optimal winning probability is indeed increasing with N | |
| Mar 29, 2019 at 20:03 | comment | added | Ryan O'Donnell | How can N=4 be worse than N=3? Can't Alice and Bob ignore their 4th inputs if they want? | |
| Mar 29, 2019 at 20:00 | comment | added | Guillaume Aubrun | For N=4 I convinced myself (but didn't try to use brute force) that the optimum is $89/255$, achieved using the same strategy as for N=3 (what you do when you see 0000 or 1111 or 0101 or 1010 is irrelevant). This is worse than for N=3 (!) | |
| Mar 29, 2019 at 19:57 | comment | added | Guillaume Aubrun | For N=3 one optimal strategy, which gives a probability $22/63$ is: for $f_A$, return the index of the $0$ which is after the block of $1$s, for $f_B$, return the index of the $0$ which is before the block of $1$s (before and after are understood modulo 3, and what you do when you see 000 or 111 is irrelevant) | |
| Mar 29, 2019 at 19:26 | comment | added | Nate Eldredge | For N=2,3,4, it should be feasible to brute force to find the optimal strategy. The results might be suggestive. | |
| Mar 29, 2019 at 16:50 | comment | added | Guillaume Aubrun | Equivalently (by regularity of measure), you can define $p_{opt}$ as the supremum over strategies which depend only on finitely many variables. | |
| Mar 29, 2019 at 14:48 | comment | added | Guillaume Aubrun | I doubt so. I said Borel to make sure that "winning probability" is a well-defined concept. For that at least you want the functions to be measurable. | |
| Mar 29, 2019 at 14:44 | comment | added | Nate Eldredge | If you drop the requirement that $f$ should be Borel, do you get bizarre axiom of choice strategies that win more often, as with hat guessing puzzles? | |
| Mar 29, 2019 at 14:25 | comment | added | Guillaume Aubrun | I used a "genetic" (?) algorithm, i.e. start from arbitrary functions $\{0,1\}^N \to \{1,\cdots,N\}$ and apply random mutations which you keep when beneficial. The value $358/1023$ corresponds to $N=5$ and the function which maps the elements of $\{0,1\}^5$ listed in lexicographic order to (5,5,1,3,3,3,3,3,1,1,1,1,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,4,5,4,5). | |
| Mar 29, 2019 at 14:13 | history | edited | Guillaume Aubrun | CC BY-SA 4.0 |
added 3 characters in body
|
| Mar 29, 2019 at 14:11 | comment | added | user44191 | How did you determine $p_{opt} \geq 358/1023$, and what exactly was the winning strategy? | |
| Mar 29, 2019 at 14:05 | history | asked | Guillaume Aubrun | CC BY-SA 4.0 |