Extension to the coin flipping puzzle

Question

This is an extension to this great puzzle: Coin Flipping Puzzle. The main difference is we now have ternary sequences instead of binary sequences.

Two criminals $A$ and $B$, were recently captured and brought to prison. They were then locked in two separate rooms. Known for being exceedingly smart, the prison warden sets a test for them. The Warden throws a 3-sided dice an infinite number of times and tells the outcomes to the criminals: $\{a_i\}$ are the outcomes told to $A$ and $\{b_i\}$ are the outcomes told to $B$.

Now $A$ and $B$ are separately told to pick a trial whose outcome they don't know, i.e., $A$ picks some outcome $b_j$, while $B$ picks some outcome $a_k$. If the outcomes of the trials picked are the same, the prison warden will release them. If they are different, they will spend their life in jail. $A$ and $B$ don't know each other's guesses.

The criminals are allowed to agree upon a common strategy in advance, but after that they cannot communicate. What is the best strategy for the prisoners that maximizes their chance of winning?

Answer 1

There is a simple strategy that is pretty good:

Find the first time a $1$ is thrown in your sequence, and choose the corresponding throw in the other player's sequence.

Probability calculation:

The probability of the two players skipping over the same number of non-$1$ outcomes is given by: $$ r = \frac13\cdot\frac13 + \frac23\cdot\frac23 \cdot r$$ where the first term represents both players throwing a $1$ and so not skipping, and the second term represents both players skipping a non-$1$ throw and then needing to skip the same number of further throws. This gives $r=\frac15$.

If they skip the same number of throws, they will both choose a $1$ from the other player's sequence and win. If they skip a different number of throws, they have a probability of $\frac13$ of their independent throws matching. The winning probability is therefore $$p=r\cdot 1 + (1-r)\cdot\frac13=\frac15 + \frac4{15} = \frac7{15} \approx 0.46667$$

There is however a better strategy in which outcomes are grouped together in triplets.

Group the outcomes in triplets. Skip any triplets of all equal outcomes, so you either get a triplet with one unique outcome and one pair, or a triplet with three different outcomes.
In a triplet that contains a single 1, if it is in the left position choose that, otherwise choose whichever of the other positions is not the 1. (This applies also to triplets with three distinct outcomes.)
In a triplet that contains a single 2, if it is in the middle position choose that, otherwise choose whichever of the other positions is not the 2.
In a triplet that contains a single 3, if it is in the right position choose that, otherwise choose whichever of the other positions is not the 3.

I won't include the 24x24 table of all possible combinations, but it turns out that with this strategy, 294 of the 576 combinations result in a match.

The probability of the two players skipping over the same number of triplets is given by: $$ r = \frac89\cdot\frac89 + \frac19\cdot\frac19 \cdot r$$ This gives $r=\frac45$.

The total winning probability is therefore $$p=r\cdot q + (1-r)\cdot\frac13 = \frac45\cdot \frac{294}{576} + \frac15\cdot\frac13 = \frac{19}{40} = 0.475$$

Answer 2

While I haven't managed to beat @Jaap's result I think I gained some good intuition on the problem that is worth while sharing:

MAIN IDEA

The centre piece of the advanced strategies we have seen is the following neat little trick:

Assume for the sake of argument that the events each player can see form a fixed recurrent sequence and only the phase is random. We could, equivalently, stipulate that they spin a wheel. Now let's further assume that the order of events for player A is upside down compared to the order of events for player B. Then they can win 100% by agreeing on a reference element a and both simply reporting the position of that element:

Two examples which should make the principle clear: Because of the opposite order of the patterns the difference in offsets simply cancels.

IMPLEMENTATION IN PRINCIPLE

The advanced strategy @Jaap has described (for both the three way and the two way flips) can be viewed as transferring as much as possible of this simple scheme to the fully random situation: Choose a period (Jaap chose 3 with some success) get rid of monochromatic sequences, and group the remaining ones together if they are equal up to rotation. And now comes the tricky bit: Choose representatives for each class such that they are as similar as possible. This is necessary since after coordinating general strategies we have no means to communicate, so we need to settle for a single anchor point before we know which patterns we are going to work with.

A CONCRETE EXAMPLE

Let's carry this out for the three letters three positions example. There are eight ($\frac{3^3-3} 3$) patterns up to rotation aligning them as best as we can they are (But keep in mind that one of the players needs to use the mirror image of this):

a b c
a b a
a b b
a c c
a a c
a c b
b b c
c b c

A USEFUL FORMULA

If we histogram the columns we get 6 x a , 1 x b , 1 x c ;; 5 x b , 2 x c , 1 x a ;; 5 x c , 2 x b , 1 x a

One can check that the number of wins can be calculated from these bin counts simply by taking squares, multiplying by group size and summing: $3 \times (6^2 + 1 + 1 + 5^2 + 2^2 + 1 + 5^2 + 2^2 + 1) = 294$ out of $24 \times 24 = 576$ pairs of outcomes total

(If the frame length isn't a prime and there are therefore classes with different period lengths it becomes only very slightly more compliated.)

This formula offers a cheap method for brute force approaches, but also suggests some pretty successful heuristic strategies: The more uneven the distribution the better, ideally a single dominant letter per column: which translates to the simple but effective algorithm choose one reference pattern (a b c) and align everything else as closely as possible.

We can now also begin to understand why three seems to be a sweet spot. There clearly is a trade off between longer chain length which would allow us to cover as much of the probability space as possible in the first and most efficient iteration of the strategy and shorter patterns which are much easier to align.

A FEW BRUTE FORCE RESULTS

My brute forcing capability runs out at 2 letters and perhaps 6 positions or 3 letters and 4 positions:

        cycle length      2         3         4         5          6
                      
alphabet size

      2                  2/3       0.7     0.69841    0.696078    0.68181

      3                  4/9      0.475    0.474696