Ekhad–Zeilberger’s most unfair bet conjecture

What Lean checks

Written proof of the extremal bound, with a finite exact comparison of pairs.

Let k≥2k\ge2 and let the letters of a length-nn text be independent and uniform on an alphabet of q≥2q\ge2 symbols. Players choose distinct words A,BA,B of length kk. A player wins when the count of their word exceeds the other count. Overlapping occurrences count. Define the advantage as the coefficient of n−1/2n^{-1/2} 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

qk/22πM,M=∑d=1k−1q−d. \frac{q^{k/2}}{2\sqrt{\pi}}M,\qquad M=\sum_{d=1}^{k-1}q^{-d}.

It is attained by ak−1ba^{k-1}b against aka^k, a≠ba\ne b, or its reversal, up to relabeling and exchange of players. For fixed q,kq,k these pairs also maximize the gap itself for all sufficiently large nn, since there are finitely many pairs and all other leading coefficients are strictly smaller.

The overlap formula

Let θUV\theta_{UV} be the sum of q−dq^{-d} over shifts 1≤d<k1\le d<k for which the length-(k−d)(k-d) suffix of UU equals the prefix of VV of that length. Write x=θBBx=\theta_{BB}, y=θAAy=\theta_{AA}, and order the words so x≥yx\ge y. Put

z=θAB,w=θBA,V=1+x+y−z−w. z=\theta_{AB},\quad w=\theta_{BA},\quad V=1+x+y-z-w.

Theorem 1.1 and (4.19) of Janson, Nica, and Segert give the advantage as qk/2/(2π)q^{k/2}/(2\sqrt{\pi}) times (x−y)/V(x-y)/\sqrt V when x>yx>y. The asymptotic variance per letter of the signed count is 2q−kV2q^{-k}V. If x=yx=y the game is fair by the equal-autocorrelation theorem, including the exceptional binary pairs excluded from the expansion. Thus it suffices to consider x>yx>y. Janson–Nica–Segert · Basdevant and coauthors

Nonconstant words

First suppose BB is nonconstant. Then AA is nonconstant as well, since a constant word has the maximum possible self-overlap MM. Shift one gives no self-overlap for either. In particular

x≤M−q−1<M/q. x\le M-q^{-1}< M/q. \tag{1}

If neither cross-overlap has shift one, then z+w≤2(M−q−1)<1z+w\le2(M-q^{-1})<1. Consequently V>x+yV>x+y and (x−y)2/V≤x<M2(x-y)^2/V\le x<M^2, using M≥1/qM\ge1/q.

Now suppose a cross-overlap has shift one. For k=2k=2 all nonconstant words have zero self-overlap. For k≥3k\ge3, if the two interiors (positions 2 through k−1k-1) are identical, a shift-one overlap forces the common interior to be a run of a single letter cc. Indeed the overlap equates each interior letter to its neighbor and fixes the adjacent end of each word. In the orientation A→BA\to B the words have forms ack−1a c^{k-1} and ck−1bc^{k-1} b. Nonconstancy forces a,b≠ca,b\ne c. Both words are unbordered and x=y=0x=y=0. The reverse orientation exchanges the roles.

It remains to bound VV for words with different interiors. For one window let f=𝟏A−𝟏Bf=\mathbf{1}_A-\mathbf{1}_B. Let PP center in both end letters, i.e. apply (I−𝔼1)(I−𝔼k)(I-\mathbb E_1)(I-\mathbb E_k) where 𝔼i\mathbb E_i averages over the letter at position ii keeping all others fixed. This is an orthogonal projection in L2L^2. For W=w1…wkW=w_1\ldots w_k it gives

P𝟏W=(𝟏X1=w1−q−1)𝟏X2⋯Xk−1=w2⋯wk−1(𝟏Xk=wk−q−1). P\mathbf{1}_W= (\mathbf{1}_{X_1=w_1}-q^{-1}) \mathbf{1}_{X_2\cdots X_{k-1}=w_2\cdots w_{k-1}} (\mathbf{1}_{X_k=w_k}-q^{-1}).

The squared norm for one word is q−k(1−q−1)2q^{-k}(1-q^{-1})^2. The two projected words have disjoint interior supports. Hence ∥Pf∥22=2q−k(1−q−1)2\|Pf\|_2^2=2q^{-k}(1-q^{-1})^2. Each translated PfPf is orthogonal to every ff or PfPf on another window, because one of its centered endpoints lies outside that window. On its own window it is orthogonal to f−Pff-Pf. Splitting the signed total into the translated projected terms and their residual therefore bounds its variance below by (n−k+1)∥Pf∥22(n-k+1)\|Pf\|_2^2. Dividing by nn and taking the limit gives

V≥(1−q−1)2. V\ge(1-q^{-1})^2. \tag{2}

Together with (1), this gives (x−y)/V<M/(q−1)≤M(x-y)/\sqrt V<M/(q-1)\le M. All nonconstant losers are strictly suboptimal.

The constant loser and equality

Suppose B=akB=a^k. Let L,RL,R be the lengths of the initial and terminal aa-runs of AA. They sum to at most k−1k-1. Write G(s)=∑j=1sqj−kG(s)=\sum_{j=1}^s q^{j-k}, including G(0)=0G(0)=0. Then z+w=G(L)+G(R)≤G(L+R)≤G(k−1)=Mz+w=G(L)+G(R)\le G(L+R)\le G(k-1)=M, and x=Mx=M. The first inequality is strict if both runs are positive, since the successive summands of GG increase strictly. Thus V≥1+yV\ge1+y and (M−y)/V≤M(M-y)/\sqrt V\le M. Equality requires y=0y=0 and one run of length k−1k-1. 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 q≥3q\ge3 it changes the maximizer. The following gives the full-alphabet result, including the case in which no constant loser is feasible. Ranking code

For 3≤q≤k+13\le q\le k+1, a constant loser requires at least q−1q-1 other letters in AA, so L+R≤k−q+1L+R\le k-q+1. The preceding proof gives the best normalized advantage against this loser as

M1+M−G(k−q+1). \frac{M}{\sqrt{1+M-G(k-q+1)}}.

It is attained by ak−q+1b2⋯bqa^{k-q+1} b_2\cdots b_q against aka^k, with all bib_i distinct and different from aa. This word is unbordered, and concentrating the available run at one end attains the cross-overlap bound. If k=q−1k=q-1, it is just a permutation of the other letters.

For any nonconstant loser with x>yx>y, 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 z+w≤2M−1/qz+w\le2M-1/q and V≥1−2M+1/q≥1/qV\ge1-2M+1/q\ge1/q since M≤1/(q−1)M\le1/(q-1) and q≥3q\ge3. Inequality (1) now bounds the normalized advantage strictly below M/qM/\sqrt q. This is smaller than the displayed constant-loser value, because 1+M<q1+M<q.

For k+1<q≤2kk+1<q\le2k, put d=q−kd=q-k and r=k−dr=k-d. When r=0r=0, all letters in the two words are different and every game is fair. When r>0r>0, an optimal loser BB is the length-kk prefix of repetitions of a block of dd distinct symbols. The winner AA consists of the remaining kk distinct symbols in any order.

To prove this last assertion, there are exactly rr repeats available among the 2k2k positions, in the sense that identifying equal letters reduces 2k2k positions to qq classes. A self-border or cross-overlap of length jj costs at least jj identifications. For a self-border the word has period k−jk-j and uses at most k−jk-j letters. For a cross-overlap each of the jj matching pairs is disjoint from all the others. Hence every overlap length is at most rr. If BB has border length rr, all identifications are used up by its period-dd equalities, so its dd residue classes are distinct, and AA uses kk fresh symbols. This is the claimed form, with y=z=w=0y=z=w=0 and x≥qr−kx\ge q^{r-k}.

If BB has no such border, x≤G(r−1)<qr−k/(q−1)x\le G(r-1)<q^{r-k}/(q-1). Always z+w≤2G(r)z+w\le2G(r), with G(r)<1/(q(q−1))G(r)<1/(q(q-1)) because r≤k−2r\le k-2. Put u=1/(q(q−1))u=1/(q(q-1)). The proposed pair has normalized advantage at least qr−k/1+uq^{r-k}/\sqrt{1+u}. All competitors without a border of length rr have smaller advantage than qr−k/((q−1)1−2u)q^{r-k}/((q-1)\sqrt{1-2u}). For q≥4q\ge4, (q−1)2(1−2u)>1+u(q-1)^2(1-2u)>1+u, proving strict optimality. If q>2kq>2k no pair uses the full alphabet. For length one, distinct letters have symmetric counts and every game is fair.