Timeline for Guessing each other's coins
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2019 at 21:12 | comment | added | Johan Wästlund | Has the 81/224-result been written down somewhere? | |
| Apr 2, 2019 at 12:31 | comment | added | Édouard Maurel-Segala | In fact there is a paper by Kariv, van Alten and Dmytro Yeroshkin which generalizes this problem to the case of a parameter p for the coin and they get some upper bounds which is also 3/8 for p=1/2. Besides, they claim that someone proved a better bound : which is 81/224 (>0,361...). Source : front.math.ucdavis.edu/1407.4711 | |
| Apr 2, 2019 at 11:13 | comment | added | Édouard Maurel-Segala | Very nice and much more direct than my formulation ! | |
| Apr 2, 2019 at 9:13 | comment | added | Guillaume Aubrun | This is really great, Édouard! Let me rephrase your argument. If switch from $\{0,1\}$ to $\{-1,1\}$, the inequality is equivalent to $\mathbf{E}[A_b B_a] \leq 1/2$. Now denote by $a$ and $a'$ Alice's output when seeing $(A_n)$ and $(-A_n)$, and same for $b$, $b'$. Your observation is that $$\mathbf{E}[A_b B_a] = \mathbf{E}[- A_{b'} B_a] = \mathbf{E}[- A_{b} B_{a'}] = \mathbf{E}[A_{b'} B_{a'}],$$ and therefore $$ 4 \mathbf{E}[A_bB_a] = \mathbf{E}[(A_b-A_{b'})(B_a-B_{a'})] \leq 2 \mathbf{E}[|B_a-B_{a'}|] \leq 2. $$ | |
| Apr 2, 2019 at 8:17 | history | answered | Édouard Maurel-Segala | CC BY-SA 4.0 |