Let and let the letters of a length- text be independent and uniform on an alphabet of symbols. Players choose distinct words of length . A player wins when the count of their word exceeds the other count. Overlapping occurrences count. Define the advantage as the coefficient of in the difference of win probabilities, with the more likely winner first. This is the statistic in the sponsor’s rankings. Challenge and sample rankings
Theorem. With unrestricted word choice, the largest advantage is
It is attained by against , , or its reversal, up to relabeling and exchange of players. For fixed these pairs also maximize the gap itself for all sufficiently large , since there are finitely many pairs and all other leading coefficients are strictly smaller.
The overlap formula
Let be the sum of over shifts for which the length- suffix of equals the prefix of of that length. Write , , and order the words so . Put
Theorem 1.1 and (4.19) of Janson, Nica, and Segert give the advantage as times when . The asymptotic variance per letter of the signed count is . If the game is fair by the equal-autocorrelation theorem, including the exceptional binary pairs excluded from the expansion. Thus it suffices to consider . Janson–Nica–Segert · Basdevant and coauthors
Nonconstant words
First suppose is nonconstant. Then is nonconstant as well, since a constant word has the maximum possible self-overlap . Shift one gives no self-overlap for either. In particular
If neither cross-overlap has shift one, then . Consequently and , using .
Now suppose a cross-overlap has shift one. For all nonconstant words have zero self-overlap. For , if the two interiors (positions 2 through ) are identical, a shift-one overlap forces the common interior to be a run of a single letter . Indeed the overlap equates each interior letter to its neighbor and fixes the adjacent end of each word. In the orientation the words have forms and . Nonconstancy forces . Both words are unbordered and . The reverse orientation exchanges the roles.
It remains to bound for words with different interiors. For one window let . Let center in both end letters, i.e. apply where averages over the letter at position keeping all others fixed. This is an orthogonal projection in . For it gives
The squared norm for one word is . The two projected words have disjoint interior supports. Hence . Each translated is orthogonal to every or on another window, because one of its centered endpoints lies outside that window. On its own window it is orthogonal to . Splitting the signed total into the translated projected terms and their residual therefore bounds its variance below by . Dividing by and taking the limit gives
Together with (1), this gives . All nonconstant losers are strictly suboptimal.
The constant loser and equality
Suppose . Let be the lengths of the initial and terminal -runs of . They sum to at most . Write , including . Then , and . The first inequality is strict if both runs are positive, since the successive summands of increase strictly. Thus and . Equality requires and one run of length . These conditions hold precisely for the words stated in the theorem.
When the two words must use the full alphabet
The sponsor’s Maple procedure Mihai retains a pair only when the union of its letters is the full alphabet. This is automatic for distinct binary words. For it changes the maximizer. The following gives the full-alphabet result, including the case in which no constant loser is feasible. Ranking code
For , a constant loser requires at least other letters in , so . The preceding proof gives the best normalized advantage against this loser as
It is attained by against , with all distinct and different from . This word is unbordered, and concentrating the available run at one end attains the cross-overlap bound. If , it is just a permutation of the other letters.
For any nonconstant loser with , at least one cross-overlap misses shift one. Otherwise both words have period two, the two phases of the same alternating word, and have equal self-overlap. It follows that and since and . Inequality (1) now bounds the normalized advantage strictly below . This is smaller than the displayed constant-loser value, because .
For , put and . When , all letters in the two words are different and every game is fair. When , an optimal loser is the length- prefix of repetitions of a block of distinct symbols. The winner consists of the remaining distinct symbols in any order.
To prove this last assertion, there are exactly repeats available among the positions, in the sense that identifying equal letters reduces positions to classes. A self-border or cross-overlap of length costs at least identifications. For a self-border the word has period and uses at most letters. For a cross-overlap each of the matching pairs is disjoint from all the others. Hence every overlap length is at most . If has border length , all identifications are used up by its period- equalities, so its residue classes are distinct, and uses fresh symbols. This is the claimed form, with and .
If has no such border, . Always , with because . Put . The proposed pair has normalized advantage at least . All competitors without a border of length have smaller advantage than . For , , proving strict optimality. If no pair uses the full alphabet. For length one, distinct letters have symmetric counts and every game is fair.