20
$\begingroup$

$A$ and $B$ are attempting to beat the casino again, and the rules are the same:

  1. Each round, $A$, $B$, and the casino simultaneously decide to show a $0$ or a $1$. If all three numbers match, $A$ and $B$ win that round.
  2. $A$ and $B$ are working cooperatively and can communicate before the game begins.
  3. $A$ has a method, just before the game starts, to learn the choices the casino will make over all the rounds. However, after learning this information $A$ cannot communicate with $B$ in any way except by her choices in the game.
  4. $A$ and $B$ are trying to maximize the fraction $p$ of rounds they win in the worst case.

The difference this time is

  1. the game lasts for $n$ rounds.

What is the best possible $p$ that $A$ and $B$ can achieve as $n \to \infty$?

Notes:

  • I don't know the answer, so I will accept the best posted strategy after a reasonable amount of time. I may possibly accept an upper bound instead if there is a very clever one.
  • ffao's solution to the previous problem shows $p \geq 2/3$. This is definitely beatable given the extra rounds at your disposal.
  • The original question and this very generalization appears here, but only gives the answer to the original problem. BTW, I'd be interested in any other history or references on this puzzle.
$\endgroup$
  • 2
    $\begingroup$ 3/4 seems like an intuitive upper bound, but I'm not sure how to prove it. $\endgroup$ – f'' Apr 17 '16 at 7:10
  • $\begingroup$ Does A know that he will receive this information in the future? Can he tell B that this is going to happen and plan accordingly? (I'll probably assume yes unless stated otherwise) $\endgroup$ – ghosts_in_the_code Apr 20 '16 at 6:18
  • $\begingroup$ @ghosts_in_the_code: Yep; during the planning stage A and B both know that A will receive the casino's information. $\endgroup$ – Tyler Seacrest Apr 20 '16 at 9:19
  • $\begingroup$ I doubt that 3/4 is possible, it would require you to be able to get 3 right with only 1 bit of information. $\endgroup$ – waylon531 Apr 22 '16 at 21:23
  • $\begingroup$ @waylon531: I haven't 100% worked out all the details, but I think I have a way to achieve $3/4 - \epsilon$ for any small positive constant $\epsilon$ you care to name. I would not be shocked if $3/4$ is actually achievable outright or even a little higher. $\endgroup$ – Tyler Seacrest Apr 25 '16 at 6:16
4
$\begingroup$

I'm sure we can do even better but to get the ball rolling I will present a sketch of a simple solution that does a hair better than 2/3.

Start with the core strategy from the previous problem: Every time the leader is forced to lose, they signal the majority bit for the next trio of games. After the first loss this wins at least 2/3 of all remaining games, so on a set of 34 games it wins at least 22. I will improve that to 23, which beats 2/3.

The leader looks at the final 6 games. If more than 4 are winnable using just the core strategy then we have 23 with no further work. Otherwise there are 18 possibilities: AAB-AAB, AAB-BBA, etc (where A is the majority bit in the second-to-last trio). There are 18 guaranteed wins that occur before this final 6, so the players assign a numbering to the 18 cases and then the leader purposefully loses the corresponding winnable game. This allows the follower to uniquely identify the final 6, reaping 2 extra wins at the cost of one extra loss.

$\endgroup$
  • $\begingroup$ But at $\infty$ it will still be $\frac{2}{3}$ because there are no "final 6 games". $\endgroup$ – Trenin May 4 '16 at 17:35
  • 1
    $\begingroup$ This strategy wins 22 of the first 34, 22 of the next 34, etc. As the number of games approaches infinity, that's still 22/34. Also, note the difference between n→∞ and n=∞. $\endgroup$ – bmcfluff May 4 '16 at 20:56
  • 1
    $\begingroup$ Got it. Didn't catch on to the fact that you did it in chunks. Although your comment about approaching infinity is not relevant. My point was that if you were doing this over the last 6 games, then which are your last 6? This is relevant to $n \implies \infty$ as well. $\endgroup$ – Trenin May 5 '16 at 12:36
  • $\begingroup$ I'm pretty sure I can refer to the overall last 6 games if I want (though this strategy doesn't) because for any given instance of the game, n is finite. This is the whole point of using limits. $\endgroup$ – bmcfluff May 6 '16 at 5:11
7
$\begingroup$

Edit -- misread the paper, had to change things a little.

Introduction

It turns out this problem relates to something called covering radius. Long story short, covering radius allow you to achieve a fraction of roughly $77\%$. However, there are some additional advantages in the casino problem that allow you to improve this to at least $80\%$ and perhaps higher.


Covering Radius

The concept of covering radius basically ask this question: Suppose Alice isn't actually playing the game, and instead it is just Bob trying to match the casino guess in each round over the $n$ rounds. Alice still knows all of the casino guesses and can supply Bob with $k$ bits ahead of time. How many rounds can Bob win?

Note that this is usually explained as the minimizing the largest hamming distance from a set of binary vectors to any binary vector outside the set or something like that. But I think my version is equivalent. See this paper for more details.

There is a bound regarding the fewest number of rounds $p$ that Bob can lose called the sphere-covering bound. It basically relates $p$, $n$ and $k$ in the following summation: $$ \sum_{j = 0}^p {n \choose j} \leq 2^{n-k}. $$ For example, if there are $n = 1000$ rounds, and we're aiming to lose $p = 230$, then Alice needs to send $k \approx 227$ bits of information (according to a Mathematica calculation using this formula).

Furthermore, for potentially extremely large values of $n$, it's been proven there are strategies that get arbitrarily close to achieving the sphere covering bound (these strategies are actually probabilistic, meaning no one has an exact description of them, but let's ignore this detail for now).


Back to the original problem

Now lets go back to the version where Alice is in fact guessing along with Bob. A key insight is that Alice can send Bob one bit of information in every round that Bob is going to get wrong anyway.

Fix some $n$, but suppose the game actually lasts much longer than $n$. Suppose Alice starts by communicating $p$ bits in the first $p$ rounds, perhaps losing all of these rounds. Suppose further this allows Alice and Bob to win all but $p$ of the next $n$ rounds. During the $p$ losses, Alice can communicate enough info to win all but $p$ of the next $n$ rounds. They can keep doing this, winning nearly a fraction $(n-p)/n$ of all rounds.

How good could this strategy actually be? Well, the values above with $n = 1000$ and $p = 230$ show that this could achieve a $77\%$ win rate. Note that you might actually need an $n$ larger than $1000$ to achieve a $77\%$ win rate.


Improving the Covering Radius Strategy

We can actually improve this a bit however. Note that in the version of the problem where Alice guesses, she can actually intentionally get rounds wrong that they would otherwise win, and this can in fact pass on a lot of information.

Suppose $n = 1000$ and we want $p = 100$. This means Alice can only send $100$ bits of information, which isn't nearly enough to achieve such a low loss rate. However, if we intentionally miss up to $100$ rounds, we may be able to convey enough information for such a loss rate. In particular, this can communicate to Bob a total of $$ \log_2 \left( \sum_{j = 0}^{100} {900 \choose j} \right) \approx 448 \text{ bits} $$ If we add to this the $100$ bits we can communicate during other losses, then this totals $548$ bits we can communicate to Bob. By the sphere-packing bound, we actually just need $k = 536$ bits to achieve a loss rate of $100$ losses.

So if we take the $100$ losses from our $p$ value plus the $100$ losses that we use to convey the extra information, and every $1000$ rounds only has $200$ losses. Again, we may need a much larger $n$ that $1000$ to actually get the covering radius part to work, but with larger $n$ values these things only get better. So in principle we can achieve a rate of $80 \%$ this way.

Note that this can still be improved. I doubt $100\%$ win rate in the limit is possible, but I'm still not sure how to prove any sort of better upper bound.

$\endgroup$
  • $\begingroup$ Very interesting. But do you have an actual strategy that achieves anything better than say 3/4? This is information theory, but can you still get this in the worst case, even if the casino knows your strategy and can tailor its bets to have maximum entropy, making it difficult for you to convey the required information? $\endgroup$ – Trenin May 10 '16 at 18:21
  • $\begingroup$ @Trenin: Above is a proof that there is a strategy that really achieves better than $3/4$, even if the casino knows the strategy and makes life as difficult as possible. However, no, I don't actually have a strategy that beats 3/4. Not only have I not worked out the details of how various choices are encoded, but even worse the whole thing relies on probabilistic arguments. I would still be interested in a more concrete, simple strategy that yields 3/4 or better. $\endgroup$ – Tyler Seacrest May 11 '16 at 3:15
  • $\begingroup$ I have one that gets around 70%, but it is soooooooo long. I don't think it would add much value. Also, while it is understandable what the follower should do, it gets very tricky to actually make the bets from the leader to give enough information to the follower. $\endgroup$ – Trenin May 11 '16 at 11:42
  • $\begingroup$ There is smg I don't understand here: During the $p$ losses, Alice can communicate enough info to win all but $p$ of the next $n$ rounds. They can keep doing this, winning nearly a fraction $p/n$ of all rounds. Doesn't this bring a win ratio of only $(n-p)/n$, or even $(n-p)/(n+p)$ if we count the initial $p$ losses ? $\endgroup$ – Evargalo Oct 4 '18 at 12:22
  • 1
    $\begingroup$ @Evargalo: Yes, I seem to be using $(n-p)/n$. Thanks for the comment! You're right that the initial $p$ loses will lower the win ratio a bit, but given many repetitions of this strategy (the game lasts much longer than $n$ in this part of the post), it won't effect things too much. $\endgroup$ – Tyler Seacrest Oct 12 '18 at 17:36
4
$\begingroup$

Here is an overly complicated way to get a whopping 0.2% better than the accepted answer!

Consider a group of 33 bets. With a single bit, you can communicate the majority allowing you to win 17 of those bets. In the 16 losses, you can communicate information. Naively, you could use these 16 bits to win the next 16 bets outright, but then you'd be forced to lose a game to communicate the majority for the next 33 bets. If instead, you purposely lost one, you could communicate an additional 4 bits of information. You can then win the next 3 and save the last bit as the majority for the next 33 bets.

The winning percentage is:

$$\frac{17+15+3}{33+16+3}=\frac{35}{52}=67.3\%$$

That is slightly better than 2/3, but not as good as the accepted answer.

But we can do a little better than that.

Lets look at the first set of 33 bets where we won 17 of them. If Alice intentionally loses one of these, then at the price of a single loss, Alice can communicate 4 more bits. This lets us win an additional 4/4, which brings the percentage to:

$$\frac{16+15+3+4}{33+16+3+4}=\frac{38}{56}=67.8\%$$

More formally, here are the two strategies for Alice and Bob.

Bob

Setup:

  1. Bet anything in the first round. Record what Alice bets as $m$.

Continuing Strategy:

  1. Bet $m$ for the next 33 rounds.
  2. See which bets played by the casino did not match $m$. Record what Alice played for these bets as $a_1, ..., a_{16}$.
  3. Record what Alice played in the remaining bets (i.e. the ones matching $m$) in $b_1, ..., b_{17}$. Determine the value of $e$ for which $b_e \ne m$. Convert $e$ to 4 binary digits $d_1, d_2, d_3, d_4$.
  4. For the next 16 rounds, bet the values $a_1, ..., a_{16}$
  5. Determine the value of $f$ for which $a_f$ ended up being a loss. Convert $f$ to 4 more binary digits $d_5, d_6, d_7, d_8$.
  6. For the next 7 rounds, bet the values $d_1, ..., d_7$.
  7. Set $m=d_8$
  8. Goto step 1.

Alice

Setup:

  1. Look at the rounds numbered 2-34 and determine the majority value $m$. Bet $m$ in round 1.

Continuing Strategy:

  1. Assume the set of bets from the current position are numbered $b_1, ..., b_n$. Create the following 4 arrays:
    • $G_1 = [b_1, ..., b_{33}]$ - the first 33 bets
    • $G_2 = [b_{34}, ..., b_{49}]$ - 16 bets
    • $G_3 = [b_{50}, ..., b_{56}]$ - 7 bets
    • $G_4 = [b_{57}, ..., b_{89}]$ - the following 33 bets
  2. Create two more reference arrays:
    • $G^{win}_1 = [ k | G_1[k]=b_k, b_k = m]$ i.e. the indices of all the bets in $G_1$ that we can win
    • $G^{loss}_1 = [ k | G_1[k]=b_k, b_k \ne m]$ i.e. the indices of all the bets in $G_1$ that we will lose
  3. Determine the majority value of the bets in $G_4$. Record this into $d$.
  4. Treat $G_3[1],G_3[2],G_3[3],G_3[4]$ as four binary digits and convert to decimal. Store the value in $e$.
  5. Treat $G_3[5],G_3[6],G_3[7],d$ as four binary digits and convert to decimal. Store the value in $f$.
  6. Let $i=w=l=1$. Until $i==33$, do the following
    • If $G^{win}_1[w] == i$ (i.e. this is a bet we can win) then
      • If $w == e$ play $\overline{m}$ (intentional loss)
      • else play $m$
      • increment $w$
    • else (this is a bet we will lose, so $G^{loss}_1[l]==i$)
      • play $G_2[l]$
      • increment $l$
    • increment $i$
  7. Let $i=1$. Until $i==16$, do the following
    • if $i == f$ play $\overline{G_2[i]}$ (another intentional loss)
    • else play $G_2[i]$
    • increment $i$
  8. Play $G_3[1], ..., G_3[7]$
  9. Set $m=d$
  10. Goto step 1
$\endgroup$
  • $\begingroup$ Thanks for posting -- good to see things actually worked out. Not too sure there exists anything better that is also simple. $\endgroup$ – Tyler Seacrest May 21 '16 at 2:50
  • 1
    $\begingroup$ Nice idea, but I'm afraid you forgot the very first bet, where you communicate majority of 33. Then it is 38/57 = 2/3. $\endgroup$ – klm123 Apr 29 '18 at 7:01
  • $\begingroup$ @klm123 I don't think so. It has been a while since I looked at this, but I believe the first bet is taken into account since it is part of the 33. It is not an extra bet. $\endgroup$ – Trenin May 2 '18 at 14:39
  • 1
    $\begingroup$ @klm123 Actually, you are correct, however for the next round of bets, we already have this majority bit and don't need to repeat it. So we have $\frac{38}{57}$ in the first round, but $\frac{38}{56}$ for all subsequent rounds. We can get arbitrarily close to $\frac{38}{57}$ by having enough rounds. $\endgroup$ – Trenin May 2 '18 at 14:45
  • $\begingroup$ @Trenin, what do you mean by "we have majority bit"? After 57th round we used up all bits. No information about following rounds can be given in the first 57, i.e. we need to start over. $\endgroup$ – klm123 May 9 '18 at 5:37
0
$\begingroup$

At the time of writing none of the answers actually achieve much better than 2/3. OP does give a probabilistic argument that >3/4 is achievable but it does not come with an actual strategy.

I claim that:

3/4 is achievable asymptotically, as conjectured by f''

In fact:

Take any answer (such as mine) to "Sub-puzzle: Master and Slave versus Bob the Violent but Honest Psychopath". Basically:
- There is a strategy which, assuming that it starts "healthy" with at most M mistakes, ends up, after 4 more rounds, "healthy" with at most M+1 mistakes.
"Healthy with at most M mistakes" means:
- They have made M-1 or fewer mistakes, and the Slave has "a Small amount of information"; OR
- They have made M mistakes, and the Slave has "a Large amount of information".

If it's still not clear,

this answer shows how to get 3N/(4N+2). However, (3N+A)/(4N+B) for any constants A and B still approaches 3/4. So, since the Deck has to be finite, only the Main game actually needs to be solved, it is clear that you can get "healthy" after a fixed number of rounds. (The hard version was created for the 9/13 case.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.