Strategy to beat the casino over the long haul

Question

$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

5. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.)