Newsgroups: rec.puzzles, rec.games.abstract Followup-To: rec.puzzles From: hoey@AIC.NRL.Navy.Mil (Dan Hoey) Date: Mon, 26 Jul 1993 22:34:49 GMT Subject: Matching digits (was Re: A puzzle) [ Note that I am crossposting this to rec.games.abstract. While this game does not fall under the letter of r.g.a's charter (being non- deterministic) it certainly is an abstract game subject to theoretical analysis. Please followup to rec.puzzles, though. ] A little over three weeks ago, r...@att.com (Ramakrishna Kandarpa) posed a problem which I would rephrase: Two players, the chooser and the matcher, each pick a sequence of six decimal digits. If the sequences share a pair of adjacent digits, the matcher wins; if not, the chooser wins. Find optimal strategies and the probability of a match. st...@hal.nta.no (Stein Kulseth) noticed that the problem statement is ambiguous, in that it is not stated whether an adjacent pair matches its reversal, so there are two different games to analyze. Stein correctly notes that if we count reversed matches, the chooser's only pure undominated strategies are to pick any pair as his only pair, by playing either XYXYXY for a heterogeneous pair or XXXXXX for a homogeneous pair. To prevent the matcher from taking advantage of regularities in his play, the chooser should pick his pair uniformly from the 55 possible pairs. The matcher's pure undominated strategies are to pick 5 different pairs. As long as any of the 55 possible pairs is equally likely to be used, he guarantees a 1/11 probability of winning. This analysis generalizes to sequences of any length of digits in any radix. If a heterogeneous pair does not match its reversal, the problem is much harder. Stein's very good analysis of the problem was marred by two errors: a trivial mistake that caused him to get the wrong answer, and a deep mistake that had no effect on the outcome! The trivial mistake was counting 90 pairs of digits (10 homogeneous pairs and 80 heterogeneous pairs) rather than 100 pairs of digits (10 homogeneous, 90 heterogeneous). The deep mistake was to assume independence of events that were correlated, in order to prove an inequality that turns out to be satisfied anyway. It is clear at first that the chooser's only undominated strategies are to pick either six different digits, or a cycle of one to five digits repeated as many times as necessary to fill out the sequence. For if the chooser's sequence contains any digit twice, d[i] d[i+1] ... d[k] d[i] the entire sequence may consist of d[i]...d[k] without any increased exposure to matches. Let us first analyze the game if the chooser's strategy is a combination of the strategies C1=XXXXXX and C2=XYXYXY. The matcher should then avoid any sequence in which a heterogeneous pair and a its reverse both appear. It should be clear that this game is effectively identical to the reverse-matching variant, since the chooser includes the reverse of each pair. The chooser should follow strategy C1 2/11 of the time and strategy C2 9/11 of the time, so that each homogeneous pairs is chosen with the same frequency as each unordered heterogeneous pair. The matcher follows the same frequency, by averaging 10/11 of a heterogeneous pair and 45/11 homogeneous pairs in each sequence. The probability of a match is 1/11. Now suppose the chooser were to use one of strategies C3=XYZXYZ, C4=XYZWXY, C5=XYZVWX, and C6=XYZUVW some fraction of the time. Stein's important insight is to show that these increase the probability of matching heterogeneous pairs above the probability of C2 matching, no matter how many heterogeneous pairs the matcher picks. Suppose the matcher picks N heterogeneous pairs. Stein reasoned that since the probability of one of the chooser's pairs fails to match one of the matcher's is (1-N/90), the probability of three failing to match is (1-N/90)^3, leading to a match probability of 1-(1-N/90)^3. But the chooser's three pairs are not independent, so (1-N/90)^3 is not the correct joint probability of failure to match. I have determined the correct probabilities by computer search, and they are given in the following table. N Stein XYZX XYZW XYX 2 5941/91125~.0652 1/16 =.0625 23/360 ~.0639 2/45~.0444 3 2611/27000~.0967 11/120~.0917 95/1008~.0942 1/15~.0667 4 631/3375 ~.1275 29/240~.1208 313/2520~.1242 4/45~.0889 5 919/5832 ~.1576 3/20 =.15 155/1008~.1538 1/9 ~.1111 The table assumes that the chooser's sequence does not repeat any digit except in homogeneous pairs; this can be done without impairing the chooser's strategy against C1 and C2. The "Stein" column has Stein's incorrect lower bound on the match probability. The "XYZX" column has the correct match probability with strategy C3. The "XYZW" column has the correct match probability with three of the pairs in strategies C4-C6. The "XYX" column has the correct match probability with strategy C2. Note that although Stein's lower bound is not in fact correct, the match probabilities for C3-C6 are still greater than the match probability for C2. Thus a competent chooser will never use C3-C6, and the analysis with the chooser restricted to C1 and C2 applies to the unrestricted game as well. I have done some preliminary investigation of the game with different length of sequence and digits of different radix. For radix 2 and 3 I calculated complete tables of optimal strategies for chooser and matcher in the following table (though I have not thoroughly checked my case analysis). For the chooser's strategy I only list the first cycle. The table ends when the matcher is able to achieve an unavoidable match. Radix 2 Length Chooser Matcher Prob 1 X any 0 2 (1/2)XX+(1/2)XY (1/2)XX+(1/2)XY 1/4 3 XX XXY 1/2 4 any XXYY 1 Radix 3 Len Chooser Matcher Prob 1 X any 0 2 (1/3)XX+(2/3)XYX (1/3)XX+(2/3)XY 1/9 3 (1/2)XX+(1/2)XYX XXY 1/3 4 (1/2)XX+(1/2)XYX (1/2)XXYY+(1/2)XXYZ 1/2 5 (3/8)XX+(3/8)XYX+(1/4)XYZX (3/4)XXYYZ+(1/8)XXYYX+(1/8)XXYZY 5/8 6 (3/8)XX+(3/8)XYX+(1/4)XYZX (1/4)XXYYZZ+(1/4)XXYYZX+(1/2)XXYYZY 3/4 7 (3/8)XX+(3/8)XYX+(1/4)XYZX (1/4)XXYYZZX+(3/8)XXYYZZY+(3/8)XXYYZXZ 7/8 8 any XXYYZZX 1 The regularities in the radix 3 table and the piecewise linear probability are most intriguing, and I wish I had time to construct the radix 4 table. I know only the following portion of that table: Radix 4 Len Chooser Matcher Prob 1 X any 0 2 (1/4)XX+(3/4)XYX (1/4)XX+(3/4)XY 1/16 3 (2/5)XX+(3/5)XYX (4/5)XXY+(1/5)XYZ 1/5 4 (2/5)XX+(3/5)XYX (1/5)XXYY+(4/5)XXYZ 3/10 .. 14 any WWXXWYYZZYXZWZ 1 I would be interested if anyone knows of or would like to investigate further results on this game. Dan Hoey Hoey@AIC.NRL.Navy.Mil