Ekhad–Zeilberger’s most unfair bet conjecture

What Lean checks

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

In Litt’s game two players count overlapping occurrences of their chosen length-kk words in the same sequence of fair coin tosses. Ekhad and Zeilberger asked which pair maximizes the leading asymptotic difference between the players’ win probabilities. Their predicted pair is Hk−1TH^{k-1}T against HkH^k. We prove it for every k≥2k\ge2, including uniqueness up to reversal, letter relabeling and player order. The maximum coefficient of n−1/2n^{-1/2} is 2k/2(1−21−k)/(2π)2^{k/2}(1-2^{1-k})/(2\sqrt{\pi}). Sponsor’s $100 OEIS donation challenge · Proof

The proof also gives the maximizing pair over every finite alphabet. When the two words must jointly contain every letter, as in the sponsor’s ranking code, the ternary maximizer is 1k−2231^{k-2}23 against 1k1^k. The proof covers all feasible alphabet sizes. Sponsor’s Maple package, procedure Mihai · Exact enumeration check

Prior work and bounty status

The extremal conjecture is the second $100 challenge on the sponsor’s page. The first challenge concerned the asymptotic formula for an individual contest and was paid. Janson, Nica, and Segert proved the general formula for a fixed pair. Basdevant, Hénard, Maurel-Segala, and Singh proved exact fairness for words with the same autocorrelation. Segert’s May 2024 paper treats HT against HH, the original length-two game. We use the first two results and optimize the asymptotic coefficient over all pairs. A November 21, 2026 search of the sponsor’s page, these articles and references, arXiv, exact-phrase searches, and the repository found no prior published extremal proof. Independent review and adjudication of this new claim are pending. Janson, Nica, and Segert · Fairness theorem · Segert’s length-two result · Research issue

Run the supplementary check with python verify.py. All comparisons in the script use integer arithmetic.