Which number is hardest to guess?

I finally figured out how to compute the "devil's distribution", a probability distribution that produces a random positive integer that's in a sense the hardest to guess.

I've known for a long time that this thing must exist, but didn't know until recently what it looked like. Here it is:

The setup is not too complicated: Two people, the Selector and the Devil, play a game with a deck of cards. Some cards are item cards and the rest are, well, ordinary cards. If we play with a standard 52-card deck we might decide for instance that the kings, queens and jacks are item cards.

First, the Devil removes 11 cards of their choice from the deck without showing the Selector. Since there were 12 item cards from the start, at least one and at most 12 are still in the game. Now the remaining 41-card deck is shuffled and the cards turned up one by one. The Selector's task is to choose online the last item card. "Online" means that whenever you see an item, you have to decide immediately whether to accept or reject it, and you can't later go back and change your mind.

If the Selector accepts the last item card, they win the game. Otherwise (if they accept an item that turns out not to be the last one, or end up not accepting anything), the Devil wins.

If you are the Selector, your task is basically to guess how many items there are in the deck. If you had to guess from the start you'd have 1 chance in 12 of winning, but it's better than that because the times when the items arrive will give you a clue. If you see many items early on, you can expect there to be more of them, but if you see only a few you might want to accept before it's too late.

But what's a good strategy? And if you play the Devil, how many item cards should you keep in the deck? If you keep many of them, is that generally going to make it harder or easier for the Selector than if there are only a few? Not so obvious!

An interesting thing about it is that if instead we play with a super-mega-giant deck of cards, the game roughly stays the same. We assume then that the Selector knows the size of the deck and that the Devil can put any number of items in it as long as there's at least one.

There is an "infinite deck limit" where instead the Devil chooses an arbitrary positive integer, and that many items arrive at random times in the interval from 0 to 1 (representing the percentage of the deck that we have seen by the time the item card is drawn).

This is where the devil's distribution enters. It represents the optimal way for the Devil to choose the number of items. Of all the ways you might randomize the number of items, this particular one makes the Selector's task hardest.

To me this distribution is special, because it's a mathematical object that I first didn't think would exist. I came to think of this game when I was working on a different problem, the secretary problem on partially ordered sets (that I eventually solved together with Ragnar Freij). At some point I thought I might have a really neat solution to that problem, but in order for it to work, the Selector would have to have a strategy that wins the continuous time Selector-Devil game with probability at least $1/e$, or approximately 36.8%.

Initially it looked promising. The number $1/e$ is what the Selector's winning chances would have been if the game had simply become harder with more items. And there was a perfect analogy, by change of time-scale, to the classical secretary problem where $1/e$ is indeed the Selector's probability of success, and that indeed gets harder with more items. Ah, mathematics is so beautiful!

And so devilish! Because in the middle of a computation, a coefficient in a taylor expansion had the wrong sign. It should have been positive, but it was $-1/2$. Well actually it didn't matter what I thought it should have been. It was negative, and you can't negotiate with the truth.

At first it seemed almost paradoxical to me, because it was clear that it can't be optimal for the Devil to randomize the number of items from a finite list of numbers. They must sometimes choose a large number. At the same time the calculation seemed to show that the Selector's task would get easier with many items.

The only possibility that didn't lead to a contradiction was that the Devil must have a specific optimal strategy consisting of most of the time choosing reasonably small numbers, and then to let the probabilities of larger numbers decay exponentially.

I proved this and described the Selector's optimal policy in a paper published on the arXiv in 2011. But it wasn't until recently that I realized that computing the devil's distribution with any degree of precision was feasible. It seemed at first that errors would propagate and grow to the point where any results obtained in reasonable time would be meaningless. But it turned out it wasn't that hard, and if we start with a precision of say 100 decimals, then ten or so will still be correct in the end.

So here are some data: The Selector, using an optimal policy, wins with probability approximately \[0.35291700020719554668690761575691114631783787927644651520731735696011.\] The Devil has a unique probability distribution to choose from that makes the Selector's task this hard. With any other, the Selector can increase their winning chances by adjusting their strategy.
Facts about the distribution: The probability of choosing only one item is about 4.444% (but no, it's not $2/45$). The number most frequently chosen is 5, which occurs with probability a little more than 8%. From then on the probabilities decrease, and for large numbers they decay in each step with a factor of approximately 1.316496. The distribution approximately has mean 8.873 and standard deviation 5.956.

And I can't relate any of these numbers to known mathematical constants. Except 5.

Primtal och siffermönster

Euklides kunde bevisa redan för 2300 år sedan att det finns oändligt många primtal. Med tiden har jag kommit att tycka att det mest fascinerande inte var att han begrep att det finns oändligt många, utan att han argumenterade för det med ett bevis. Vem var det han förklarade för? Hur diskuterade man? Hur såg det samhälle ut där ett stringent logiskt resonemang ansågs värt att skriva ner och föra vidare, när högröstad auktoritet i de flesta tider och kulturer har betraktats som mer trovärdigt?

Bevismetoden är idéhistoria. Om vi till exempel vill visa att det finns ett primtal som är större än en miljon, kan vi tänka på talet \[M = 1\cdot 2\cdot 3\cdot 4\cdot 5 \cdots 1000000 + 1.\] Här har vi multiplicerat ihop alla tal upp till en miljon och adderat 1. Liksom alla heltal större än 1 måste detta tal vara delbart med något primtal, för är det inte delbart med något annat primtal är det självt ett primtal. Men det primtal som talet $M$ är delbart med kan inte vara något av talen upp till en miljon, för $M$ ger rest 1 vid division med vart och ett av dem. Vi ser alltså att det måste ligga myriader av primtal och lura i mörkret bortom en miljon, även om resonemanget inte ger någon ytterligare ledtråd till vilka dessa tal är.

Idén om en formel eller ett mönster som styr primtalen har varit en sorts helig graal för matematiker genom tiderna. På 1600-talet fick Pierre de Fermat idén att starta från 2 och bilda en följd där varje tal är kvadraten av det föregående, alltså $2, 4, 16, 256, 65536, \dots$ Han gissade att om vi adderar 1 till vart och ett av dessa tal, så att vi får \[3, 5, 17, 257, 65537,\dots\] skulle vi få en följd av enbart primtal. Men det sprack när redan nästa tal, 4294967297, visade sig vara delbart med 641. Han hittade inte graalen...

Gör man en lista över primtal upptäcker man att alla utom 2 och 5 slutar på någon av siffrorna 1, 3, 7 eller 9. För ett par-tre år sedan blev det ståhej i matematikvärlden när det påstods att man hade upptäckt "primtalskonspirationer" i form av oväntade mönster i primtalens slutsiffror. Men det visade sig till slut att mönstren skulle vara där och att talen uppför sig som de ska.

Jag tänkte prata lite om att vi faktiskt vet, sedan 1830-talet, att det finns oändligt många primtal med var och en av slutsiffrorna 1, 3, 7 och 9. Det fantastiska beviset av Lejeune Dirichlet är giltigt inte bara modulo 10 utan i varje talbas.

Jag har flera gånger tänkt att det borde finnas en introduktion till Dirichlets teorem som började med att beskriva fallet modulo 10. Förutom att 10 är basen för vårt siffersystem är det också det enklaste fallet där man behöver komplexa tal. Men man behöver ingen komplex analys per se. Koefficienterna i de serier man behöver är bara $\pm 1$ och $\pm i$ och det räcker att titta på det komplexa argumentet av en enda serie.

Det kanske finns något sådant nerskrivet någonstans, men jag har inte hittat det, och ska man få någonting riktigt som man vill ha det, får man ändå göra det själv...

Men vi börjar med att se hur långt vi kan komma genom att modifiera Euklides bevis. Första steget i Dirichlets riktning blir att visa att det finns oändligt många primtal som slutar på 3 eller 7.

Antag att vi multiplicerar ihop alla tal som slutar på 3 eller 7 upp till en viss gräns, till exempel en miljon. Om gränsen är ett jämnt tiotal så att vi har lika många faktorer som slutar på 3 respektive 7, slutar produkten på en etta. Om vi sedan adderar 2, får vi ett tal som slutar på 3 och som inte kan vara delbart med något tal som ingår i produkten:
\[M_3 = 3\cdot 7 \cdot 13\cdot 17 \cdot 23\cdot 27\cdots 999997 + 2.\] Men ett tal som slutar på 3 eller 7 måste ha någon primfaktor som slutar på 3 eller 7, så det måste finnas något sådant primtal större än en miljon.

Med ett resonemang som bygger på så kallade kvadratiska kontra icke-kvadratiska rester (ett nyckelord är kvadratisk reciprocitet) kan vi visa att det också finns oändligt många primtal som slutar med 1 eller 9. Vi kan nämligen titta på vilka primfaktorer ett tal av typen $n^2-5$ kan ha. Om $p$ är ett primtal som delar $n^2-5$, så är $n^2$ kongruent med $5$ modulo $p$. Multiplikation med 5 måste därmed ge vad som i kombinatoriken kallas en jämn permutation av restklasserna modulo $p$. Men det visar sig att om $p$ slutar på siffran 3 eller 7, kommer multiplikation med 5 att ge en udda permutation av restklasserna. Ett tal av typen $n^2-5$ kan därför aldrig ha en primfaktor som slutar på 3 eller 7.

Här finns det massor av intressanta siffermönster. Ett tal som består av en radda med tvåor följt av en radda med ettor, och som har en mer etta än tvåa, kan till exempel bara ha primfaktorer som slutar på 1 eller 9. Talen 211, 22111 och 2221111 är själva primtal, medan \[222211111 = 379 \cdot 586309,\] \[22222111111 = 109\cdot 8221\cdot 24799,\] \[2222221111111 = 20411\cdot 108873701,\] och så vidare. De här talen är inte själva på formen $n^2-5$, men de följer mönstret \[222211111 = \frac{66665^2 - 5}{20}.\] När vi dividerar bort 20, finns bara faktorer som slutar på 1 och 9 kvar.

Ska vi göra ett bevis av Euklidiskt snitt kan vi titta på talet \[M_9 = \left(2\cdot 1\cdot 9\cdot 11\cdot 19 \cdot 21 \cdot 19 \cdots 999999\right)^2 - 5.\] Produkten inom parentes består av alla tal under en miljon som slutar på 1 eller 9, samt en faktor 2 för att garantera att resultatet efter att vi har subtraherat 5 är ett udda tal.

Talet $M_9$ kan inte vara delbart med 2 eller 5, och på grund av den kvadratiska reciprociteten inte heller med något primtal som slutar på 3 eller 7. Alla dess primfaktorer måste alltså sluta på 1 eller 9, men de kan inte ingå i produkten i vänsterledet, så de måste vara större än en miljon.

I själva verket kan vi stärka slutsatsen ytterligare: Talet $M_9$ slutar på siffran 9, så det måste ha en primfaktor som slutar på 9 (om alla slutade på 1 skulle $M_9$ sluta på 1).

Det var förresten den kvadratiska reciprociteten som ställde till "primtalskonspirationerna". Primtalen kunde inte ligga hur som helst utan var tvungna att lyda reciprocitetslagen.

Vi kan även konstruera en följd av tal vars samtliga primfaktorer slutar på siffran 1, och samtidigt ge Pierre de Fermat upprättelse. Vi tittar på tal av typerna \[n^4 + n^3 + n^2 + n + 1 = \frac{n^5-1}{n-1}, \text{ och}\] \[n^4 - n^3 + n^2 - n + 1 = \frac{n^5+1}{n+1}.\] Om primtalet $p$ är en delare i något av dessa tal, måste $n^5$ vara kongruent med $1$ respektive $-1$ modulo $p$. Enligt en sats av Fermat innebär det att $p-1$ måste vara delbart med 5, såvida inte $n$ är kongruent med $1$ eller $-1$. I båda fallen blir slutsatsen att talet 5 kan förekomma som en primfaktor för vissa värden på $n$, men att samtliga övriga primfaktorer måste sluta på siffran 1.

Om vi tar $n=10^{12}$ till exempel, blir $n^4 + n^3 + n^2 + n + 1$ lika med talet \[1000000000001000000000001000000000001000000000001\] med det vackert klingande namnet en oktiljon en sextiljon en kvadriljon en biljon ett och den underbara primfaktoriseringen \[31\cdot 41\cdot 61\cdot 211\cdot 241\cdot 271\cdot 2161\cdot 3541 \cdot 9091\cdot 27961\cdot 2906161\cdot 4188901 \cdot 39526741.\] Även här kan vi à la Euklides tvinga fram primfaktorer bortom varje given gräns genom att låta $n$ vara delbart med alla tal upp till denna gräns.

För att sammanfatta så långt, vet vi alltså att det finns oändligt många primtal som slutar på siffran 1, oändligt många som slutar på 9, och oändligt många som antingen slutar på 3 eller 7. Det här visste nog Fermat, Euler och Gauss, men för att knyta ihop säcken skulle vi vilja ha ett bevis för att det inom den sistnämnda kategorin primtal både finns oändligt många som slutar på 3 och oändligt många som slutar på 7.


Dirichletserier

Den så kallade harmoniska serien \[ 1 + \frac12 + \frac13 + \frac14 + \frac15 + \frac16 + \frac17 + \frac18 + \frac19 + \frac1{10} + \dots\] är divergent. Summan kan alltså bli hur stor som helst bara vi tar med tillräckligt många termer. Den harmoniska serien kan faktoriseras genom av vi delar upp alla nämnare i primtalspotenser och bryter ut ett primtal i taget: \[ \left(1+\frac12 + \frac14 + \frac18+\dots\right)\cdot\left(1+\frac13+\frac19+\frac1{27}+\dots\right)\cdot \left(1+\frac15+\frac1{25}+\dots\right)\] \[ \cdot \left(1+\frac17+\frac1{49}+\dots\right)\cdot \left(1+\frac1{11}+\frac1{121}+\dots\right)\cdot \left(1+\frac1{13}+\frac1{169}+\dots\right)\cdots\] Om vi börjar med att bryta ut faktorn i den första parentesen, får vi termerna med udda nämnare kvar. Efter att vi också har brutit ut den andra faktorn har vi kvar de termer vars nämnare inte är delbara med 2 eller 3, och så vidare.

Varje faktor är en geometrisk serie, så vi kan skriva om hela produkten som \[\frac21\cdot \frac32 \cdot \frac54\cdot \frac76 \cdot \frac{11}{10}\cdot \frac{13}{12}\cdot \frac{17}{16}\cdot \frac{19}{18} \cdots\] Här har vi följden av alla primtal i täljarna. Delprodukterna svarar inte på något enkelt sätt mot delsummor av den ursprungliga serien, men det står ändå klart att även produktformen måste vara divergent, och att \[\prod_{p<N}\frac{p}{p-1} \geq \log N.\] Detta ger oss ett nytt bevis för att det finns oändligt många primtal.

Så här långt hade Leonhard Euler kommit på 1730-talet. Ungefär hundra år senare fick Dirichlet idén att faktorisera andra liknande serier på samma sätt. Till exempel tittade han på serien \[1- \frac13 - \frac17 + \frac19 + \frac1{11} - \frac1{13} - \frac1{17} + \frac1{19} + \frac1{21} + \dots\] Här är bara termer vars nämnare slutar på 1, 3, 7 eller 9 med, och dessutom har vi satt minustecken på dem vars nämnare slutar på 3 eller 7.

Nu blir serien konvergent, det vill säga summan blir ett ändligt tal. Om vi grupperar termerna fyra och fyra efter jämna tiotal kan vi skriva den som \[\sum_{k=0}^\infty \left(\frac1{10k+1}-\frac1{10k+3}-\frac1{10k+7} + \frac1{10k+9}\right)\] \[= 120\cdot \sum_{k=0}^\infty \frac{2k+1}{(10k+1)(10k+3)(10k+7)(10k+9)}\approx 0.64561.\] Skrivet på det sättet blir alla termer positiva och de går snabbt mot noll. Redan den första termen ger $1-1/3-1/7+1/9 = 40/63 \approx 0.63492$.

När vi faktoriserar blir det alternerande tecken för alla primtal som slutar på 3 eller 7, men plustecken rakt igenom för dem som slutar på 1 eller 9 (och inga faktorer för 2 eller 5): \[\left(1-\frac13+\frac19-\frac1{27}+\dots\right)\cdot \left(1-\frac17+\frac1{49}-\dots\right) \cdot \left(1+\frac1{11}+\frac1{121}+\dots\right)\] \[\cdot \left(1-\frac1{13} + \frac1{169}-\dots\right) \cdot \left(1-\frac1{17} + \frac1{289}-\dots\right) \cdot \left(1+\frac1{19} + \frac1{361}+\dots\right) \cdots\] \[ = \frac34 \cdot \frac78\cdot\frac{11}{10}\cdot \frac{13}{14}\cdot \frac{17}{18}\cdot\frac{19}{18}\cdot\frac{23}{24}\cdot\frac{29}{28}\cdot \frac{31}{30} \cdots\] Men i det här fallet har serien både positiva och negativa termer, så relationen mellan delsummor av serien och delprodukter av den oändliga produkten blir inte lika enkel. Faktum är att den här produkten konvergerar mot samma värde som summan, men det är ett väldigt djupt resultat och ingenting som Euler eller Dirichlet kunde reda ut. En nyckelfras här är primtalssatsen för aritmetiska följder.

Som Dirichlet själv påpekade i originalartikeln (som jag själv tycker är lättast att läsa i engelsk översättning), måste ett bevis för konvergens av den här typen av produkt utnyttja att primtalen kommer i en viss ordning, för om vi blandar om faktorerna kan den fås att konvergera mot eller oscillera mellan vilka positiva värden som helst. Så länge ingenting i vårt resonemang beror av att vi bryter ut faktorerna i någon viss ordning, kan vi inte ha tillräckligt med krut för att visa att den här produkten konvergerar.

För att komma runt detta införde Dirichlet en variabel $s$ som vi kan tänka på som ett tal strax ovanför 1, typ $1.01$, och tittade istället på vad vi än idag kallar för $L$-funktioner, i det här fallet \[1- \frac1{3^s} - \frac1{7^s} + \frac1{9^s} + \frac1{11^s} - \frac1{13^s} - \frac1{17^s} + \frac1{19^s} + \dots\] \[ = \left(1-\frac1{3^s} +  \frac1{9^s}-\dots\right)\cdot \left(1-\frac1{7^s}+\frac1{49^s}-\dots\right) \cdot \left(1+\frac1{11^s}+\frac1{121^s}+\dots\right)\cdots\] \[= \frac{3^s}{3^s + 1}\cdot \frac{7^s}{7^s+1}\cdot\frac{11^s}{11^s-1}\cdot\frac{13^s}{13^s+1}\cdot\frac{17^s}{17^s+1}\cdot\frac{19^s}{19^s-1}\cdots.\] Nu är serien absolutkonvergent (för varje fixt $s>1$), så vi kan skyffla om termerna hur som helst. I synnerhet måste den oändliga produkten konvergera mot samma värde som summan. Variabeln $s$ kan vi tänka på som ett smart sätt att trunkera så att vi får samma resultat oavsett om vi tittar på summan eller produkten.

Om vi gör samma sak med den harmoniska serien, får vi vad som sedermera skulle komma att kallas Riemanns zetafunktion: \[ \zeta(s) = 1 + \frac1{2^s} + \frac1{3^s} + \frac1{4^s} + \dots = \frac{2^s}{2^s - 1}\cdot \frac{3^s}{3^s - 1}\cdot\frac{5^s}{5^s-1}\cdot\frac{7^s}{7^s-1}\cdots.\] Även denna serie är absolutkonvergent för varje $s>1$, men den växer mot oändligheten då $s$ minskar mot 1 eftersom den då väsentligen beter sig som den harmoniska serien.

Låt oss först pausa ett ögonblick och begrunda hur långsamt serien för zetafunktionen konvergerar. Vi kan jämföra summan med \[ \int_1^\infty \frac1{x^s}\, dx = \frac1{s-1}.\] För $s=1.01$ till exempel, blir summan lite drygt 100. Men summerar vi de $2^{100}$ första termerna har vi bara kommit halvvägs, och vid $3^{100}$ har vi fortfarande en tredjedel kvar. Tre korrekta decimaler får vi först någonstans kring $10^{500}$!

Men för att jämföra med den förstnämnda $L$-funktionen tittade Dirichlet i stället på en serie med enbart plustecken, men där vi fortfarande bara har med termer som svarar mot tal som slutar på 1, 3, 7, 9. \[1 + \frac1{3^s} + \frac1{7^s} + \frac1{9^s} + \frac1{11^s} + \dots = \frac{3^s}{3^s - 1}\cdot \frac{7^s}{7^s - 1}\cdot\frac{11^s}{11^s-1}\cdot\frac{13^s}{13^s-1}\cdots.\] Vi kan kalla den här serien med bara plustecken för $L_{\bf 1}$ och den med varierande tecken för $L_{\bf -1}$. De kallas som sagt på riktigt för $L$-funktioner, så det är notation som nästan men inte riktigt är standard. I själva verket består $L_{\bf 1}$ av de termer vi får kvar om vi bryter ut faktorerna för 2 och 5 i zeta-serien, dvs \[ \zeta(s) = \frac{2^s}{2^s-1}\cdot \frac{5^s}{5^s-1} \cdot L_{\bf 1}.\] Det betyder att även $L_{\bf 1}$ går mot oändligheten när $s\to 1$, och lite mer precist att \[L_{\bf 1} \approx \frac25\cdot \frac1{s-1}.\] Om vi tittar på produktformerna av $L_{\bf 1}$ och $L_{\bf -1}$  är det förstås intressant att de faktorer som svarar mot primtalen på 1 och 9 är desamma. Det ligger nära till hands att dividera för att kancellera dem och se vad vi kan säga om det som blir kvar. Då får vi \[\frac{L_{\bf 1}}{L_{\bf -1}} = \frac{1+1/3^s+1/7^s+1/9^s+\dots}{ 1-1/3^s-1/7^s+1/9^s+\dots}\] \[= \frac{3^s+1}{3^s-1}\cdot \frac{7^s+1}{7^s-1}\cdot \frac{13^s+1}{13^s-1}\cdot \frac{17^s+1}{17^s-1}\cdot \frac{23^s+1}{23^s-1}\cdot \frac{37^s+1}{37^s-1}\cdots\] Här vet vi från representationerna som serier att $L_{\bf 1}$ går mot oändligheten och $L_{\bf -1}$ mot ungefär $0.64561$ när $s$ närmar sig 1. Kvoten mellan dem går därför också mot oändligheten, och en slutsats av detta är att produkten i högerledet måste ha oändligt många faktorer. Vi får alltså ett nytt bevis för att det finns oändligt många primtal som slutar på 3 eller 7.

Om vi i stället för kvoten tittar på produkten av $L_{\bf 1}$ och $L_{\bf -1}$ blir det primtalen på 3 och 7 vars faktorer (nästan) kancellerar: \[L_{\bf 1}\cdot L_{\bf -1} = \left(\frac{3^{2s}}{3^{2s}-1}\cdot  \frac{7^{2s}}{7^{2s}-1}\cdot  \frac{13^{2s}}{13^{2s}-1}\cdots \right)\] \[\cdot \left(\frac{11^s}{11^s-1}\right)^2\cdot \left(\frac{19^s}{19^s-1}\right)^2\cdot \left(\frac{29^s}{29^s-1}\right)^2\cdot \left(\frac{31^s}{31^s-1}\right)^2 \cdots.\] Här utgörs den första parentesen av "skräp" från primtalen på 3 och 7 och som inte riktigt kancellerar, men som konvergerar mot ett ändligt värde. Ansvaret för det faktum att produkten går mot oändligheten då $s\to 1$ vilar därmed på primtalen på 1 och 9 i de följande faktorerna, som därför måste vara oändligt många.

Om vi vill sortera bort "skräpet" och uttrycka slutsatserna lite mer kvantitativt, kan vi logaritmera alltihop. Eftersom faktorerna ligger nära 1, får vi bara ett begränsat fel om vi använder approximationen $\log x \approx 1+x$ rakt igenom. Då blir slutsatsen av faktoriseringen av $L_{\bf 1}$ att \[ \sum_p \frac1{p^s} = \log\left(\frac1{s-1}\right) + O(1).\] Här uttalar vi oss alltså om vad som händer när $s$ går mot $1$, och termen $O(1)$ står för något som är begränsat som funktion av $s$.

När vi faktoriserar $L_{\bf -1}$ får vi å andra sidan att \[ \sum_{p=11, 19, 29, 31,\dots}\frac1{p^s} - \sum_{p=3, 7, 13, 17,\dots} \frac1{p^s} = O(1),\] dvs differensen mellan de här summorna är begränsad när $s\to 1$. Om vi delar upp primtalen i dem på 1 och 9 kontra dem på 3 och 7, kommer de alltså att bidra med ungefär lika mycket till den totala summan av $1/p^s$. Var och en av summorna i vänsterledet måste alltså vara $1/2\cdot \log(1/(s-1))$ plus något begränsat.

Så här långt var nog egentligen Euler med, och han var ju dessutom en hejare på det här med komplexa tal, men det var först Dirichlet som gick vidare till att titta på faktoriseringar av serier som $L_{\bf 1}$ och $L_{\bf -1}$ men med komplexa koefficienter.

De två lantliga och rejäla serierna $L_{\bf 1}$ och $L_{\bf -1}$ har nämligen två kusiner från den komplexa storstaden, serierna (med fortsatt aningen improviserad notation) \[L_{\bf i} = 1 + \frac{i}{3^s} - \frac{i}{7^s} - \frac{1}{9^s} + \frac1{11^s} + \frac{i}{13^s} - \frac{i}{17^s} - \frac1{19^s} + \dots\] och \[L_{\bf -i} = 1 - \frac{i}{3^s} + \frac{i}{7^s} - \frac{1}{9^s} + \frac1{11^s} - \frac{i}{13^s} + \frac{i}{17^s} - \frac1{19^s} + \dots\] med motsvarande produktrepresentationer \[ L_{\bf i} = \frac{3^s}{3^s-i}\cdot \frac{7^s}{7^s+i}\cdot \frac{11^s}{11^s-1}\cdot \frac{13^s}{13^s-i}\cdot \frac{17^s}{17^s+i}\cdot \frac{19^s}{19^s+1}\cdots\] och \[ L_{\bf -i} = \frac{3^s}{3^s+i}\cdot \frac{7^s}{7^s-i}\cdot \frac{11^s}{11^s-1}\cdot \frac{13^s}{13^s+i}\cdot \frac{17^s}{17^s-i}\cdot \frac{19^s}{19^s+1}\cdots\] som vi kan få fram genom att bryta ut på samma sätt som Euler gjorde med den harmoniska serien.

Med risk för viss historierevisionism vill jag nu börja med att multiplicera ihop de två kusinerna. Då får vi ytterligare en reell serie som vi för tillfället kan kalla $L_{\bf \star}$. Anledningen är att jag först vill se hur långt vi kommer med ren "envarre" (en reell variabel).

På serieform kan vi skriva produkten som \[ L_\star = L_{\bf i}\cdot L_{\bf -i} = \left(1 -\frac1{9^s} +\frac1{11^s} - \frac1{19^s} + \frac1{21^s} - \frac1{29^s}+\dots\right)^2\] \[ + \left(\frac1{3^s} - \frac1{7^s} + \frac1{13^s} - \frac1{17^s} + \frac1{23^s}-\frac1{27^s}+\dots\right)^2.\] Här har vi tagit realdel gånger realdel för sig, och imaginärdel gånger imaginärdel för sig. Eftersom kusinerna är varandras komplexkonjugat, kommer alla termer av typen reell gånger imaginär att kancellera.

I det här fallet kan vi till och med tala om explicit vad gränsvärdet blir när $s\to 1$. Om vi sätter in $s=1$ (detta går ju bra på serieform) blir den första parentesen (realdelen av var och en av kusinerna) lika med \[ \frac{\pi}{10}\cdot \cot\frac{\pi}{10} = \frac{\pi}{10}\cdot \sqrt{5+2\sqrt{5}}\approx 0.96688.\] Varför det blir så är en annan historia, som egentligen börjar med det så kallade Baselproblemet.

Den andra parentesen, imaginärdelen av $L_{\bf i}$, blir \[ \frac{\pi}{10}\cdot \cot\frac{3\pi}{10} = \frac{\pi}{10}\cdot \sqrt{5-2\sqrt{5}}\approx 0.22825.\] Om vi kvadrerar och lägger ihop, får vi \[ \lim_{s\to 1} L_\star = \frac{\pi^2}{10}\approx 0.98696.\] Så länge $s>1$ kan vi även skriva $L_\star$ på produktform genom att multiplicera produkterna för kusinerna. Även produktformen blir helt igenom reell: \[L_\star = \prod_{p=3,7,13,17,\dots} \frac{p^{2s}}{p^{2s}+1} \cdot \prod_{p=11,31,41,\dots} \left(\frac{p^s}{p^s-1}\right)^2 \cdot \prod_{p=19,29,59, \dots} \left(\frac{p^s}{p^s+1}\right)^2.\] Här ligger faktorerna för $p=3, 7, 13, 17, \dots$ så nära 1 att den första produkten går mot ett ändligt värde skilt från noll även när $s$ går mot $1$, medan de följande två grupperna av faktorer har potential att var för sig dra iväg hur långt som helst mot oändligheten respektive ner mot $0$, när $s$ närmar sig $1$.

Om vi jämför detta med produktformen för $L_{\bf 1}\cdot L_{\bf -1}$, blir det igen lockande att dividera det ena med det andra, eftersom faktorerna för primtal som slutar på 1 då kommer att kancellera. Vi får \[ \frac{L_{\bf 1}\cdot L_{\bf -1}}{L_\star} = \prod_{p=3,7,13,17\dots}\frac{p^{2s}+1}{p^{2s}-1} \cdot \prod_{p=19,29,59,\dots}\left(\frac{p^s+1}{p^s-1}\right)^2.\] Vi vet genom serierepresentationerna att $L_{\bf 1}$ går mot oändligheten när $s\to 1$, medan både $L_{\bf -1}$ och $L_\star$ går mot ändliga värden som inte är noll. Hela detta kalas måste alltså gå mot oändligheten när $s\to 1$, vilket bara kan bero på att det finns oändligt många primtal som slutar på 9.

Återigen kan vi multiplicera istället för att dividera, och då är det primtalen på 1 som hamnar i rampljuset: \[L_{\bf 1}\cdot L_{\bf -1}\cdot L_\star = \] \[ \prod_{p=3,7,13,17,\dots}\frac{p^{4s}}{p^{4s}-1} \cdot \prod_{p=19,29,59,\dots}\left(\frac{p^{2s}}{p^{2s}-1}\right)^2 \cdot \prod_{p=11,31,41,\dots} \left(\frac{p^s}{p^s-1}\right)^4.\] Även detta drar iväg mot oändligheten när $s\to 1$, och alla utom primtalen som slutar på 1 har alibi.

Nu har vi använt reella Dirichletserier för att reproducera precis vad vi visste sedan Euklides och Fermat: Det finns oändligt många primtal med slutsiffra 1, oändligt många med slutsiffra 9, och oändligt många med 3 eller 7.

Om vi logaritmerar och taylorapproximerar igen, får vi den något mer precisa informationen att \[ \sum_{p\equiv 1 \text{ (mod 10})} \frac1{p^s} = \frac14\cdot \log\left(\frac1{s-1}\right) + O(1),\] \[ \sum_{p\equiv 9 \text{ (mod 10})} \frac1{p^s} = \frac14\cdot \log\left(\frac1{s-1}\right) + O(1),\] och \[ \sum_{p\equiv 3, 7 \text{ (mod 10})} \frac1{p^s} = \frac12\cdot \log\left(\frac1{s-1}\right) + O(1).\] Men nu kommer det fina med Dirichlets metod: Om vi tar isär parhästarna $L_{\bf i}$ och $L_{\bf -i}$ så att det blir räkning med komplexa tal på riktigt, får vi fram information som skiljer ut primtalen på 3 från dem på 7!

Det ligger nära till hands att titta på kvoten $L_{\bf i}/L_{\bf -i}$ för att kancellera alla primtal på 1 och 9 (och den här gången få omvänt tecken på 3 och 7). Men eftersom vi då får ett tal på den komplexa enhetscirkeln, kokar hela analysen ner till att titta på argumentet för $L_{\bf i}$, alltså vinkeln från den positiva reella axeln.

Som påminnelse: \[L_{\bf i} = 1 + \frac{i}{3^s} - \frac{i}{7^s} - \frac{1}{9^s} + \frac1{11^s} + \frac{i}{13^s} - \frac{i}{17^s} - \frac1{19^s} + \dots\] \[ = \frac{3^s}{3^s-i}\cdot \frac{7^s}{7^s+i}\cdot \frac{11^s}{11^s-1}\cdot \frac{13^s}{13^s-i}\cdot \frac{17^s}{17^s+i}\cdot \frac{19^s}{19^s+1}\cdots\] och \[\lim_{s\to 1} L_{\bf i} = \frac{\pi}{10}\cdot \left(\cot\frac{\pi}{10} + i\cdot \cot\frac{3\pi}{10}\right) \approx 0.96688 + i\cdot 0.22825.\] Från serierepresentationen ser vi att både realdelen och imaginärdelen av $L_{\bf i}$ kommer att vara alternerande serier som uppfyller Leibniz kriterium, så argumentet kommer att ligga i intervallet $[0,\pi/2]$ för alla $s>1$. Vi kan till och med beräkna gränsvärdet av argumentet då $s\to1$ som \[\arctan\left(\frac{\cot(3\pi/10)}{\cot(\pi/10)}\right) = \arctan\left(\sqrt{5}-2\right) = \frac12\,\arctan\frac12.\] Om vi jämför med argumentet för var och en av faktorerna i produktrepresentationen, får vi det märkliga resultatet att \[\arctan\frac1{3^s}-\arctan\frac1{7^s}+\arctan\frac1{13^s}-\arctan\frac1{17^s}+\arctan\frac1{23^s}-\arctan\frac1{37^s}+\dots\] \[ \to \frac12\, \arctan\frac12 \approx 0.23182.\] Här är det plustecken på termerna för primtal som slutar på 3, och minustecken för dem som slutar på 7. Vi måste ha $s>1$, annars vet vi inte (med vårt resonemang här) att vänsterledet konvergerar överhuvudtaget. Men för varje $s>1$ är summan absolutkonvergent, och värdet på denna summa konvergerar sedan i sin tur mot $1/2\cdot\arctan(1/2)$.

Det är frestande att tänka att det ska gå att dra någon slutsats om fallet $s=1$ här, och summerar vi för primtalen upp till en miljon med $s=1$ blir det mycket riktigt ungefär $0.23182$. Man kan fråga sig om det verkligen är möjligt för en summa av den här typen att först ha ett gränsvärde när $s$ närmar sig 1 och sedan bete sig helt annorlunda för $s=1$. Men det är det, för det är som sagt bara att ta termerna i en annan ordning så blir det så. Det betyder att så länge ingenting i vårt resonemang pekar ut ordningen av primtalen efter storlek som det "rätta" sättet att ordna termerna, kan inga generella konvergenssatser hjälpa oss.

Faktum är att summan för $s=1$ ändå konvergerar mot $1/2\cdot\arctan(1/2)$, men det är ett helt annat kapitel av talteorin. Det går att komma åt den typen av summor genom att även låta variabeln $s$ vara komplex, och det var Bernhard Riemann som visade vägen ett par decennier efter Dirichlets artikel, även om inte han heller rodde det i hamn. Även här får vi hänvisa till primtalssatsen för aritmetiska följder.

Det finns en annan utsökt subtilitet i beräkningen av argumentet för $L_{\bf i}$, och det är hur vi vet att summan av argumenten av faktorerna blir just $0.23182$ och inte det talet plus någon multipel av $2\pi$. Det beror egentligen på att vi kan starta med $s$ från oändligheten, då argumentet är nära noll, och sedan kontinuerligt minska $s$ ner till 1. Vi vet från serierepresentationen att $L_{\bf i}$ aldrig kommer att röra sig ut ur den första kvadranten, och värdet kan därför aldrig snurra runt nollan i det komplexa talplanet.

För att återgå till primtalen kan vi göra en linjär approximation av varje term även i ekvationen för argumentet. Om vi använder $\arctan x \approx x$ för varje term, får vi \[\sum_{p=3, 13, 23, 43,\dots}\frac1{p^s} - \sum_{p=7, 17, 37, 47,\dots} \frac1{p^s} = O(1).\] I kombination med vad vi redan visste, blir slutsatsen nu att oavsett vilken av de fyra möjliga slutsiffrorna vi väljer, har vi \[\sum_{p\text{ med fix slutsiffra}} \frac1{p^s} = \frac14\cdot\log\frac1{s-1} + O(1).\] Eftersom högerledet går mot oändligheten när $s\to 1$, vet vi till slut att det finns oändligt många primtal i alla fyra klasserna.

Då har vi ändå bara skrapat på ytan av Dirichlets teorem. I fallet modulo 10 kunde vi konstatera lite ad-hoc att de tre serierna $L_{\bf -1}$, $L_{\bf i}$ och $L_{\bf -i}$ inte kan gå mot noll då $s\to 1$, och vi kunde ganska enkelt se hur argumenten av de komplexa serierna beter sig. Men redan på 1830-talet redde alltså Dirichlet ut vilka $L$-funktioner man får för generellt modulus, varför ingen av dem kan gå mot noll när $s\to 1$, och hur man kombinerar dem för att få en summa som domineras av primtal från en enskild klass. Han kunde alltså bland annat visa att om vi specificerar en sifferkombination hur lång som helst, så finns det alltid oändligt många primtal som slutar med just den sifferkombinationen, förutsatt bara att den allra sista siffran är 1, 3, 7 eller 9.

Kan man föreställa sig tre dimensioner?

Jag som är utbildad matematiker ska väl inte bli förvånad över det här med längdskala, areaskala, och volymskala. En ar är 10 meter i kvadrat, alltså 100 kvadratmeter. En hektar är 100 gånger så mycket, vilket är arean av en kvadrat med sida 100 meter. Det är i sin tur bara en hundradels kvadratkilometer.

Sedan har vi det här med volymer. Zlatan Ibrahimovic har fått guldbollen 11 gånger. Om man verkligen gjorde en boll av allt världens guld, skulle den få en diameter på ungefär 25 meter och i stort sett få plats under den här bollbanan.

I högre dimensioner blir det ännu konstigare. Ett bowlingklot ska visst ha en diameter på 22 cm, och skulle förstås precis få plats i en kubisk låda med inre mått 22 cm. Men hur många klot med diameter 20 cm skulle få plats i en sådan låda, det vill säga om kubens sida är 10% större än klotets diameter? Det kan väl fortfarande inte få plats mer än ett kan man tycka, och i tre dimensioner stämmer det. Men i 100 dimensioner går det in två! Och om antalet rumsdimensioner går över en sorts tröskel vid ungefär 600 kommer man att kunna kasta in inte bara två, utan nästan hur många klot som helst slumpmässigt, och de kommer att studsa runt i lådan och nästan aldrig krocka!

I den kurs i linjär algebra som jag brukar hålla på höstarna brukar jag rita hur jag tänker mig att kuber ser ut i hög dimension. Så här ser det ut i mina gamla anteckningar:

Så länge klotet måste ligga i mitten får det bara plats ett, men så fort man kan peta dem en liten bit in i något av spröten, får man in nästan hur många som helst!

"Kan man föreställa sig 10 dimensioner?" frågar studenterna. "Kan man föreställa sig tre?" frågar jag tillbaka, halvt på skämt.

Men bara halvt. De här sakerna kände jag ju till, och jag visste också hur mycket jorden väger. Ändå blev jag på något sätt lite förvånad när jag i en tidigare bloggpost försökte illustrera hur ofattbart mycket $5 \cdot 10^{21}$ är. Jordens vikt i ton lät liksom inte så mycket.

Jorden är ett klot, ungefär 1273 mil i diameter. Metersystemet baserades för övrigt ursprungligen på att avståndet längs jordytan från ekvatorn till en pol ska vara tusen mil, och diametern är $4/\pi\approx 1.273$ gånger den sträckan.

Den är stor, men ändå inte ofattbart stor, tycker jag. På den här bilden ser man södra Sverige och samtidigt jordens krökning. I höstas körde jag en dag rutten Linköping-Rödeby-Göteborg. Det var väldigt mycket skog som susade förbi, och det tog många timmar, mest på 80-vägar. Men det gick på en dag, och då hann jag med att spela schackmatch i division 1 mot Rödeby (i Blekinge) också. Om man tittar på en jordglob eller föreställer sig att man zoomar ut från den här bilden, inser man att sträckan jag körde är ganska liten jämfört med hela jordklotet. Men den är ändå inte så liten att den inte syns. Om jag pekar på min dotters badboll modell jordglob, kan jag förklara för henne att här är Stockholm, här är Göteborg, och här är Polen där gammelmormor och gammelmorfar bor.  

Avstånden mellan stjärnorna däremot betraktar jag som bortom min direkta fattningsförmåga. Om jag ska föreställa mig det, får jag skala om flera gånger.

Det lär vara möjligt att under ideala förhållanden se Uranus utan hjälpmedel, men Saturnus är det mest avlägsna jag vet med mig att jag har sett som inte lyser av sig självt. Jag har sett den många gånger men minns särskilt en magisk vårvinterkväll för cirka 15 år sedan med sedermera bortgångne schackvännen och amatörastronomen Arno Platau. Han pekade ut Merkurius, Venus, Mars, Jupiter och Saturnus för det lilla sällskap som hade samlats i Landeryd. Vi kunde se alla fem och dessutom månen, samtidigt. Jag vet inte hur ofta det är möjligt, men gissar att det är ganska sällsynt. Jag, min äldsta dotter och de övriga turades om att titta i teleskopet på Jupiters månar, Saturnus ringar, steniga lilla Merkurius, månens kratrar med mera.

Saturnus var den bortre gränsen för det solsystem som var känt under medeltiden.

Saturnus är större än jorden men syns ändå bara som en liten prick om man inte har kikare, så man ser att det måste vara långt. När den är som närmast och vi ser den i söder vid midnatt, är den hundra tusen jorddiametrar bort. I den skala som ges av badbollen blir det flera mil. Låt oss ändra skala igen, till 1:1,000,000,000,000,000, alltså ett till tusen biljoner. Nu är medeltidens universum en liten kula på ett par-tre millimeter i diameter där inte ens solen är stor nog att urskilja. Kulan får behändigt plats i en ruta på papperet som jag ritade den där kuben på.

I den skalan är ett ljusår 10 meter. Trippelstjärnesystemet Alpha Centauri ligger drygt 40 meter bort. Närmast oss just nu Proxima Centauri med minst en planet i sällskap, och ett par meter därifrån dubbelstjärnesystemet Rigil Kentaurus och Toliman.

Vår galax vintergatan är i den här skalan fortfarande i väldigt runda slängar lika stor som hela Sverige. Stjärnorna, var och en med sitt system av planeter, månar och kometer, ligger som mikroskopiska korn utströdda med några tiotals meter mellan varandra. I mörkret mellan dem driver säkert oräkneliga "rogue planets" och en del svarta hål omkring, men mest är det tomt. Vårt solsystem har virvlat omkring här i miljarder år utan att någonsin passera så nära någon annan tung himlakropp att planetbanorna de där millimetrarna närmast solen har störts. Enstaka klippblock har fallit ner och styrt om kursen för livet på jorden, men inte slagit ut det.

Inte kan det vara särskilt dammigt där ute heller. Om vi tittar upp en klar natt ser vi stjärnorna, men är det lite dimma gör vi inte det. Stjärnljuset kan färdas i tusentals år i rymden för att sedan stoppas upp av några vattendroppar i jordatmosfären.

Ska jag föreställa mig vintergatan, måste jag skala om och skala om och skala om. Annars förblir den bara obegripligt stor. Men jordklotet tycker jag mig kunna fatta. Fast gör jag egentligen det?

Från nordpolen till ekvatorn är det tusen mil. Jordens volym blir då i princip \[\frac{32}{3\pi^2} \approx 1.08\] gånger volymen hos en kub som har tusen mil som sida. Det är nära nog. Låt oss tänka oss att vi delar upp den volymen i kubikmetrar och lägger ut de meterstora kuberna i en lång rad i stället. Hur långt räcker den raden?

Tusen mil är 10 miljoner meter, och kubikmetrarna längs en kant på kuben blir förstås just 1000 mil, nästan en jorddiameter. Tar vi ett "lager" av meterkuber, en kvadratisk sida på tusenmilakuben, blir det 10 miljoner jorddiametrar, 100 gånger så stort som medeltidens universum ut till Saturnus. Det blir en decimeter i skalan 1 till tusen biljoner som jag pratade om nyss. En hundradel av ett ljusår. Men det var bara ett lager, och det finns 10 miljoner sådana lager. Lägger vi ut alla kubikmetrarna efter varandra, räcker de hundra tusen ljusår, tvärs över den hisnande vintergatan!

Jag sa att jag behövde skala om och skala om och skala om för att förstå hur stor vintergatan är. Tre ordentliga omskalningar blir det hur jag än gör. Och det är väl inte så konstigt då egentligen att det blir jordklotet i kubikmetrar. En omskalning gör jorden till en badboll, och det är tre dimensioner. Tio upphöjt till sju, och detta i sin tur upphöjt till tre, blir $10^{21}$.

Men ändå tycker jag det är slående. Och vi kan gå längre, för en kubikmeter är ju inte det minsta vi kan tänka oss. Om vi delar upp jorden i kubikdecimetrar, räcker de 100 gånger så långt (areaskala!). Då är vi långt bortanför Andromedagalaxen. Och med kubikcentimetrar kommer vi en miljard ljusår bort.

Slutligen kan vi föreställa oss att jordklotet skulle vara ett nystan gjort av en enda lång fiberoptisk kabel. Inte bara den tunna tråden alltså, utan hela knippet med hölje och allt, grov nog att hantera men ändå så att den skulle gå genom en av rutorna på mitt rutade papper. Vi tänker oss att det gick en signal från den ena änden av kabeln då jorden bildades, för över 4 miljarder år sedan. Signalen har susat fram i ofattbara ljusets hastighet, 30 gånger sidan på tusenmilakuben varje sekund, alltmedan kontinenter har flyttat sig, vågor slipat ner berg, och fiskarnas ättlingar fått ben och vandrat upp på land. Och den är fortfarande inte framme vid andra änden av kabeln!
 

Card play with a unicellular brain

In an earlier blog post I described the simplest shedding game I can think of. I called it Shed and it's perhaps more of a mathematical simplification than a real card game. But go ahead and try it with 6 or 7 cards, you might have a brain meltdown when you realize you're playing a game simpler than tic-tac-toe and you still can't get it right...

Quick recap of the rules: Two players take turns playing cards numbered 1,..., N to a pile. The card you play must be higher than all the cards currently in the pile. If you can't or don't want to play, you can (must) instead pick up the whole pile. The goal is to force the opponent to pick up all the cards. At the start of the game, the cards are in an open talon available to both players.

It's possible to play the game with a standard deck with different suits (see the blog post), but it seems challenging already with just one suit.

I first thought of this game around the same time that I wrote about simple models of whist, almost 20 years ago. Already at that time I had a short program in C that computed the outcome under optimal play for N up to about 13, and with a rewritten hack on my current laptop I now pushed that to N = 15.

Since each card can be in 4 different locations (in the hand of the player about to move, in the hand of the player who just moved, in the pile, or in the talon), there are (at most) $4^N$ positions to consider. The program creates a "table-base" by repeatedly looping through those $4^N$ positions, checking if it can determine their value under optimal play using values already stored. As soon as there is a full iteration without any more values being assigned, it concludes that the remaining positions are drawn and stops the search.

It can be done much more efficiently, but for N = 15 my program requires something like 30 iterations through most of the approximately 1,000,000,000 positions, and more on a minority of them.

Since at any time only a limited number of moves can be played before someone picks up the pile (in theory N but often much fewer), we can trade space for time by only storing the values of the $3^N$ quiet positions - those where the pile is empty. That's what my program does, but for N = 15 that's still more than 14 million values.

We can simplify even more by first considering only endgames - those positions where the talon is empty (and will therefore remain empty for the rest of the game). If we focus on quiet endgame positions we are down to $2^N$ - about 32,000 in the case of 15 cards.

I wanted to see if it's possible to play optimally using much less data by somehow assigning a point-value to each card and summing those values. For instance, the values of the 32 quiet endgame positions for N = 5 can be compactly described by giving the cards 1, 2, 3, 4, 5 the point-values $-2, -1, 0, 1, 2$ respectively. To figure out if we're winning or not, we sum the values of our own cards, subtract the total value of our opponent's cards, and finally add or subtract 1 point for having or not having the move respectively. If the final score is positive we have a winning strategy, and if it's negative, we're losing.

For N = 6 this sort of thing still works, but we have to tinker a bit to get the point-values right. One solution is to set them to $-7, -5, -2, 3, 6$, and $8$, with a correction of $\pm 4$ for having or not having the move. Technical remark to ensure reproducibility of my results: The position where the player to move has all cards on their hand is regarded as winning for that player (since they can play their cards from the bottom up and force the opponent to pick up). But that position is impossible to reach.  

So how do we find a set of point-values that makes this work, and can we do it for more than 6 cards?

To cast this in the terminology of machine-learning, let's not call it the point-value of a card, but instead the weight. So we want to find weights $w_1, w_2, \dots, w_N$ for the cards, and also a suitable bias $b$. That's what we now call the correction term for having or not having the move.

Since I tend to want to see things from the perspective of the player who just moved, I insist that the bias $b$ should be added when we're not making the next move and subtracted when we are, which means $b$ will have to be negative if having the move is an advantage.

In order to find the weights for the case N = 6, I used (buckle up, here are some buzz words of AI) gradient descent and a sigmoid neuron. There's also something called Support Vector Machines, but let's go with the sigmoid neuron here. The picture (well, for N = 7) looks like this:

There are N input nodes (labeled 1,..., 7 in the picture) that we can call $c_1,\dots, c_N$ (c for card) and that take the value $+1$ if we (who made the last move) have that card, and $-1$ if the other player has it. Each input is multiplied with the corresponding weight $w_i$, and the bias $b$ is added to the sum. The result is then passed to the sigmoid neuron, which computes the function
\[\sigma(x) = \frac1{1+e^{-x}}.\] The sigmoid function outputs a number between 0 and 1 which is close to 0 if the input is clearly negative and close to 1 if the input is clearly positive, with a smooth transition for inputs around 0. In our case we can think of the output as a tentative answer to how likely it is that the player who just moved is winning. Ideally, the answer should be 1 if that player actually has a forced win, and 0 otherwise (there exist drawn positions, but they are quite rare, so let's for the moment go with just classifying positions into winning or not winning).

The output will never be exactly 0 or 1, but we'd like to correctly classify each card distribution in the sense of having an output larger than 1/2 if the player who just moved is winning, and smaller than 1/2 otherwise. Since $\sigma(0) = 1/2$, this puts the threshold at zero, so what we're asking for is that the point-score (which is sent as input to the sigmoid function) should be positive if we're winning and negative if we're losing.

We can start by setting all the weights and the bias to 0 (or whatever, really). Then we use the table-base of known values to train the system (using known values like this is what's called supervised learning). We feed the system an input vector (a card distribution) and calculate the output. Then we make small adjustments to $w_1,\dots, w_N$ and $b$ that all push the output a little bit in the direction of making it more correct.  

Here it actually makes sense to adjust the bias $b$ by
\[ b := b + 0.1 \cdot \left(\text{correct value} - \text{actual output}\right).\] This pushes $b$ in the right direction (increasing it if we want a larger output, decreasing it if we want smaller), but looks a bit too simple. But in case you like partial derivatives of error functions and stuff, there's actually a theoretical justification for updating $b$ in this particular way, and a key word is cross entropy error. The learning rate $0.1$ is admittedly a bit arbitrary though.

The weights $w_i$ are updated in the same way, except that the sign of the correction is determined by $c_i$ (the input vector, which is $\pm 1$ depending on who has the i:th card):
\[ w_i := w_i + 0.1 \cdot c_i \cdot \left(\text{correct value} - \text{actual output}\right).\] In the case N = 6 this works like a charm, and already after one epoch of training (going through each of the 64 input vectors once and then making the total adjustments), the system finds the weights $-1.3, -0.9, -0.3, 0.5, 1.1, 1.5$ and the bias $-0.7$, which correctly classify each of the 64 card distributions. These decimal numbers give the integer point-values that I suggested earlier if we multiply everything by 5 and round away from 0.

But when we try the same thing for N = 7, we run into a bit of trouble. Our single neuron brilliantly classifies 124 out of the 128 quiet endgame positions, but has difficulty with the remaining four. With a bit of improvised notation again, those four positions are
\[\left(\text{7-6-5-4-3-2-1}^+ \,\, \square \,\, - \right) \, \mapsto \, 0,\] \[\left(\text{5}^+ \,\, \square \,\, \text{7-6-4-3-2-1}\right) \, \mapsto 0,\] \[\left(\text{7-5-3-2}^+ \,\, \square \,\, \text{6-4-1}\right) \, \mapsto 1, \text{ and}\] \[\left(\text{6-5-4-1}^+ \,\, \square \,\, \text{7-3-2}\right) \, \mapsto 1.\] Here the hands are written with a little square table between them as in bridge diagrams. The whole position (within parentheses) is then mapped by the ideal value to 1 (left player winning) or 0 (right player winning). The plus-signs indicate that a certain player just added cards to their hand (and the other is about to play).

We can now see that it's impossible for a single neuron to correctly classify these positions: If we sum the weights (and biases) involved for the first two positions, we get $2w_5 + 2b$ (the card 5 is on "our" hand in both of them, and all other cards have changed places). If we do the same thing for the last two, we get the same result: $2w_5 + 2b$. Demanding a negative point-score for the first two positions and at the same time a positive point-score for the last two is clearly asking too much: The sum of two negative numbers can't be the same as the sum of two positive ones.

It's true that the first of the four difficult positions is the final position of the game, where the left player has already lost, and that if we remove that position from the training data, the system will learn to correctly classify the remaining 127.

We could argue more generally that the problem is that we ask the system to compare hands with different number of cards in them. It makes sense therefore to try with one set of weights for each pattern, so that for instance we would have a specific set of weights for the pattern 4-3 obtained by training only on positions where the player who just picked up has 4 cards and the other player has 3. This works fine for quiet endgames of 7 cards, and it would be a feasible design also for much larger $N$, since even if we count the patterns of quiet but non-endgame positions, there would only be around $N^2/2$ of them.

But this approach too has its limitations, even for quiet endgames. For 10 cards there are drawn endgames, but even if those positions are removed from the training data, it turns out to be impossible for a single neuron to classify the remaining ones.

For the pattern 6-4 there are 210 positions of which 4 are drawn. When trained on the remaining 206 positions, the system keeps misclassifying two of them. It turns out that the values assigned to the remaining positions show clearly where the problem lies. If after 100 training epochs we list those positions that are assigned a value more than 0.3 away from the correct value, we get the following:
\[\left(\text{10-9-6-5-2-1}^+ \,\, \square \,\, \text{8-7-4-3} \right) \, \mapsto \, 0 \quad \neq 0.49,\] \[\left(\text{10-8-6-5-3-1}^+ \,\, \square \,\, \text{9-7-4-2}\right) \, \mapsto 0 \quad \neq 0.38,\] \[\left(\text{9-7-6-5-4-2}^+ \,\, \square \,\, \text{10-8-3-1}\right) \, \mapsto 0 \quad \neq 0.46,\] \[\left(\text{8-7-6-5-4-3}^+ \,\, \square \,\, \text{10-9-2-1}\right) \, \mapsto 0 \quad \neq 0.36,\] \[\left(\text{10-7-6-5-3-2}^+ \,\, \square \,\, \text{9-8-4-1}\right) \, \mapsto 1 \quad \neq 0.42,\] \[\left(\text{9-8-6-5-4-1}^+ \,\, \square \,\, \text{10-7-3-2}\right) \, \mapsto 1 \quad \neq 0.42.\] The numbers to the right are the outputs of the system. Here we can see that the average point-score of the first four (losing) positions will always be the same as that of the last two (winning) ones, namely $w_6+w_5 + b$. And the average of a list of positive numbers can't equal the average of a list of negative ones.

If we keep training, the system will provide values converging correctly to 0 or 1 for all other positions, while adapting the best it can to the impossible constraints given by the 6 positions listed by giving each of them a value (in the limit) of 1/3.

This isn't really a failure of the approach. We can't possibly expect a small set of linear functions to flawlessly tell winning positions from losing, any more than we expect point-values for chess pieces to solve the riddle of chess, or high-card points to provide a perfect bidding system in bridge.

It's interesting that the single-neuron system discovers these examples, and it actually gets weirder. Once we have set up the "architecture" of the system, we can train it also on non-endgame positions. We can choose to let an input value of $c_i = 0$ represent that the i:th card is still in the talon, and again train the system on a fixed pattern $(m, n)$, meaning that the player who just picked up has $m$ cards and the other player has $n$ cards.  

When we get to N = 6 and the pattern 2-0, we find something strange: In a few rounds the system learns to correctly classify all 15 positions, but it insists that $w_2$ must be smaller than $w_1$! And indeed the only time (for this particular pattern) it matters whether you have the 1 or the 2 is if the other card is the 5, and in that case it's better to have the 1 than to have the 2!  

For N = 7 and the pattern 2-2, again the single neuron fails to correctly classify all positions, and among the difficult positions we find \[\left(\text{7-2}^+ \,\, \square \,\, \text{6-3} \right) \, \mapsto \, 1.\] Here the left player is winning, but if we replace the 3 on the right hand by the 1, left is losing, and if moreover we replace the 2 on the left hand with the 3 that we removed from the right hand, left is still losing: \[\left(\text{7-3}^+ \,\, \square \,\, \text{6-1} \right) \, \mapsto \, 0.\]
Alright, that's all for now!

Devil’s Roulette – Maximum Surprise Expected!

"Here is the wisdom. Let him that hath understanding count the number of the wild beast: for it is the number of a game; and its number is three-score and six."

Suppose you're in a casino playing roulette, and that you can only bet on Black or Red. The roulette wheel has 18 red numbers, 18 black ones, and a green zero. If you bet on a color and a number of that color comes up, you win the size of your bet, but if another number comes up, you lose your bet. You can't bet on zero, so whenever the zero comes up, the casino wins everything.

Once you start playing, you're bound to lose on average. You can design clever systems that either give you a good chance of winning a small amount at a small risk of complete disaster (double your bet until you win), or the other way around (double until you lose). But the presence of the zero tilts the whole thing a tiny bit in the casino's favour so that you always lose in the long run.

Now into the casino walks the devil himself and gives you an offer. If you lend him your soul, you may ask for the exact number of red numbers, black numbers, and zeros in the next $N$ rounds, for any one number $N$. The devil will then look into the future and tell you the answer.

But there's a catch (what did you expect, bargaining with the devil?). Once you know those three numbers, it will turn out that whatever you do in the following $N$ rounds, the roulette ball will bounce in a way that gives you maximal bad luck. 

Suppose for instance that you ask for seven rounds and the devil tells you there will be three red numbers, three black, and one zero. If you wait for the last of those seven rounds, hoping to then double your stack when you know the outcome, then that's going to be when the zero comes up. But if you start betting on one color, then sure enough the other color will come up (and the zero will still be left).

Notice though that "bad luck" doesn't necessarily mean you lose in the current round. It means that the outcome will be what's worst for you overall. If you bet 10 out of 100 chips on black when there's a black number and a zero left, you will win (because otherwise you would double your stack in the last round).   

Let's decide what the rules are and what we're trying to optimize. We start the game with a bankroll that we can think of as a large stack of chips, say a million. We assume that at any time we can bet any fraction of what we have, like one third of our stack, even though a million isn't divisible by 3. We can't buy more chips during the game, so the amount we have at each round is a limit on how much we can bet. We're trying to finish with as much as possible after the $N$ rounds, and the payoff of the game is our final bankroll measured in units of the initial stack.

We can choose the number $N$ as we please, and the number of red, black, and zeros in the next $N$ rounds will be determined by the randomness of the roulette wheel with no supernatural intervention by the devil. If there are $N$ zeros, we can't win anything (so the payoff is 1 as we never make a bet), and if there are $N$ red or $N$ black numbers, we can double our stack $N$ times ending up on $2^N$, so it's not that interesting to ask about best- or worst-case scenarios for this stage.

Next, knowing $N$ and the number of red, black, and zeros, we are assuming a worst-case (also known as adversarial) scenario. We can imagine that the croupier gives the devil a set of $N$ cards of the colors red, black and green with the given distribution, and that we play against the devil. In each of $N$ rounds we make a bet, after which the devil plays one of the cards to decide the outcome. That card is then removed, and we play until the cards are exhausted. This stage of the game involves no probability. It's a two-person game of perfect information like chess.  

How to bet

A first observation is that unless there are only zeros, we can always win something. Suppose for instance that $N=6$ and that there are five zeros and one red. That's a pretty bad outcome, but still, if we have a stack of 63 chips, we can make that 64 by the double-until-you-win strategy: First we bet 1 chip on Red. If we win we're done and there are only zeros left, so suppose we lose. The devil has now spent one of the zeros, and in the next round we bet 2 on Red. Again if we win we're done, so assume we lose. Then we bet 4 in the next round and so on. In the penultimate round we have 48 chips and bet 16. If we lose again, the devil has spent the last zero and we must win in the last round.

Here's a challenge that you might want to try before reading on: Suppose $N=5$ and you're told that there will be 3 red and 2 black numbers. If you start out with 100 chips, how can you make sure to get more than 300? And if instead there are 3 red numbers and 2 zeros, how can you double your stack?

Spoiler alert, I'm about to tell you how to bet optimally! First let's change the game in a way that doesn't actually matter, but that simplifies the analysis. Instead of green cards for the zeros, let's make them wild cards (wild beasts?) that are red on one side and black on the other, so that when playing such a card, the devil can choose between counting it as red or as black.

As long as we only bet on one color, that's going to be just as good for the devil, since he can choose the other color. And it doesn't make much sense in the original setting for us to place a bet on red and another bet on black, since it will be at least as good to cancel chips bet on red against chips bet on black and only bet the difference on one of the colors. But with the red/black wild cards instead of the green ones, we can assume that we always bet everything we have, and that we only choose how much of our current bankroll to bet on red and how much to bet on black. 

Now we can use a method described by Peter Winkler (in a red/black setting without zeros) in his wonderful paper Games People Don't Play. His attempt to trace that problem to its origin seems to have reached the so-called grapevine (Update: It's actually discussed on pages 6-7 of these notes by Thomas Cover from 1974, which are cited in a different section of Peter Winkler's paper!). Suppose for instance that $N=10$ and that you learn that there's going to be 5 red, 3 black, and 2 zeros. Using the red/black wild cards, this means that whatever the devil does, in the end there will be 10 cards on the table of which 5, 6, or 7 will have a red side face up, and 3, 4, or 5 will be black. The total number of sequences of red/black that satisfy that constraint, like for instance R-B-B-B-R-R-B-R-R-R and B-B-R-R-R-R-B-R-R-R, turns out to be (using binomial coefficients)

\[\binom{10}3 + \binom{10}4 + \binom{10}5 = 120 + 210 + 252 = 582.\]

So we hire 582 gnomes to do the betting for us. Each gnome is assigned one of the R-B-sequences and a bag of money. Their task is to bet everything they have in each round on their own particular sequence. Clearly one of them will win whatever the devil does, and the one who wins will double their money 10 times, resulting in a payoff of 1024 times what they started with. If we distribute our initial bankroll evenly between the 582 gnomes, that means we can guarantee a final payoff of \[ \frac{1024}{582} \approx 1.759.\]
To see how to actually bet (in the first round say), let's find out how many gnomes will bet on red in the first round and how many will bet on black. It turns out (again summing some binomial coefficients) that of the 582 valid R-B-sequences, 336 start with an R and 246 start with a B. Consequently, 336 of our gnomes will bet on Red in the first round and 246 will bet on Black. To emulate this in the original game, we cancel the 246 bets on Black against equally many bets on Red, and in the end place $336 - 246 = 90$ out of every 582 chips on Red. So your first move is to bet a fraction of \[\frac{90}{582} = \frac{15}{97} \approx 0.155\] of your bankroll on Red.

After the first round, all the losing gnomes are out of the game, and we make the same calculation again for the second round, now using only the remaining gnomes/R-B-sequences.

Not only does this guarantee a payoff of, in this case, 1024/582, but it's also best possible. It turns out that whatever strategy we use can be emulated by a set of gnomes, and that the only thing we can vary is how we distribute our chips between them from the beginning. The devil will always let the poorest of our gnomes win, so the best we can do is to give them the same amount. 

Payoff as a surprise

The payoff of $1024/582$ in our example can be interpreted as the inverse of a probability. The number 582 was the number of ways we can have 3, 4, or 5 Black in a sequence of Red-Black of length 10, so the probability of that happening if the sequence was decided by fair coin flips (or a roulette without zero) is \[\frac{582}{1024}.\]
In general, our payoff with $r$ red numbers, $b$ black numbers, and $z$ zeros is the inverse of the probability that a sequence of length $r+b+z$ of Red/Black generated by a roulette without zeros (let's call that a fair roulette) has at least $r$ Red and at least $b$ Black. The inverse of the probability is what we might call the surprise of an event - it's larger the more unexpected that event is (I'm not sure if there's an established name for the reciprocal of a probability, but it's sort of the same thing as the so-called odds). So our payoff is always the surprise of the hypothetical event that a fair roulette played for the same number of rounds would yield an outcome (in terms of number of red/black) consistent with the one we have (in the sense that the devil could use his wild cards to get the same red/black distribution as the fair roulette).

Let's look at another example: Suppose we give the devil a standard pack of 26 red cards, 26 black, and two jokers (to use as wild cards). What's our payoff going to be?

We can compute that as the surprise of the event that a fair roulette, played 54 times, would yield somewhere from 26 to 28 red numbers (a red/black distribution of 26-28, 27-27 or 28-26). Again the binomial coefficients give us the answer: The payoff is going to be
\[\frac{2^{54}}{\binom{54}{26}+\binom{54}{27}+\binom{54}{28}} \approx 3.159,\] reflecting the fact that the probability of 26, 27 or 28 red is roughly one in 3.159.


By the way, the Chernoff bound

By the way (that's how in academia we signal that we're about to say something important), the connection also goes the other way: We can use the devil's roulette to establish that certain events are extremely unlikely. Suppose for instance that you flip a coin a million times and the outcome is heads a little more than 505,000 times and tails not even 495,000 times. Is that normal? Or imagine that we're looking at whatever statistical data and asking whether deviations from what we expect can be explained by good-old 50-50 randomness or not. Even though the "expected" number of heads with a fair coin would be 500,000, surely we don't expect exactly that number. Should we be suspicious because we're off by 0.5%?

Let's play Devil's Roulette and give the devil 505,000 red and 495,000 wild cards. Since the wild cards can represent both red and black, this distribution represents every outcome with 505,000 or more Red. And let's consistently bet, throughout the game, 1% of our current bankroll on Red. This isn't the optimal strategy, but it's good enough.

If the devil plays sensibly, we'll win 505,000 times and lose 495,000 times. Every time we win, our bankroll increases by a factor $1.01$, and every time we lose, it decreases by a factor $0.99$. No matter in which order this happens, we end up with a payoff of
\[ 1.01^{505,000} \cdot 0.99^{495,000} \geq 5\cdot 10^{21}.\] We didn't even play optimally, and yet we secured a payoff of fifty round trips to Alpha Centauri measured in millimeters, or almost the weight of the earth in tonnes (wait, the latter somehow feels less impressive than the former!?).

This means that the probability of getting 505,000 or more heads in a sequence of a million fair coin flips is at most 1 in $5\cdot 10^{21}$. So yes, we should probably be suspicious.

This sort of inequality is known in probability theory by various combinations of the names Bernstein, Chernoff, Hoeffding, and Azuma. I dare say that thinking about it in terms of roulette is a slight improvement on the standard proofs. There's a parameter that needs to be optimized, but in our setting that's just what fraction to bet in every round.

As a sanity check on the method, if instead we give the devil 500,500 red and 499,500 wild cards, the best we can do with a strategy of betting a constant fraction turns out to be around 1.65 times the money. This gives no new information, since we already know that the probability of more Red than Black is at most 50%. And indeed, being off by 500 from the mean here is not very unlikely.


How to choose $N$: Maximum expected surprise

If it wasn't for the zero, the analysis would be simple: The larger the value of $N$, the more we would tend to win. If $N=100$ for example, we would end up with on average 101 times our initial bankroll. It seems that the analysis would be quite complicated, since if the devil gets 58 red cards and 42 black ones, say, then our payoff is the inverse of the probability of 58 red and 42 black in 100 rounds of roulette-without-zero, and that's just one term in an enormous sum. But the probability of this scenario exactly cancels what we win, so in the end we're summing 101 terms, each of which is equal to 1!

This insight can be summarized in the following theorem:

The expected surprise of any random variable is its number of possible outcomes.

The surprise of an event is also equal to the expected number of times you have to try again until the same thing happens. For instance, if you repeatedly flip a coin, the expected number of times until you get the same outcome again as the first time is 2, even if the coin is biased. Or maybe it's 3...?

Anyway, when there are zeros, it turns out we shouldn't pick $N$ too large. If $N$ is large, then most likely the number of red, black, and zeros will be relatively close to their expected values of $\frac{18N}{37}$, $\frac{18N}{37}$ and $\frac{N}{37}$ respectively.

The probability that $N$ rounds of a roulette wheel without a zero would yield at least $\frac{18N}{37}$ red numbers and at the same time at least $\frac{18N}{37}$ black ones is going to be very close to 100% when $N$ is large. Since our payoff is the reciprocal of this, we will most likely finish with only a microscopic amount more than what we started with.

It's true that we might win a fortune if we're lucky, so to establish rigorously that the average payoff tends to 1 as $N$ tends to infinity will require a careful argument and some calculation. So let's not do that here.

The expected payoff for a given $N$ is, in a sense, how surprised we expect to be by the outcome of $N$ rounds of roulette (well, by a fair roulette being consistent with it in terms of the wild cards). If there are too few rounds, too few things can happen for anything to be surprising, but if there are too many, then most of the time each color will appear with about its expected frequency.

It's fairly easy to let the computer calculate the average payoff for various values of $N$.
\[
\begin{array}{cc}
N & \text{Payoff} \\
1 & 1.97 \\
2 & 2.91 \\
3 & 3.81 \\
4 & 4.69  \\
5 & 5.52 \\
6 & 6.33  \\
7  & 7.11 \\
8 & 7.85 \\
9  & 8.58 \\
10  & 9.27 \\
\end{array}
\]
So far so good. I said before that if there aren't any zeros, the average payoff is $N+1$, and these numbers seem to reflect that, being a little smaller due to the possibility of zeros.

And when we take the calculation a little further, we reach a peak average payoff at $N=66$, after which it decreases. At $N=311$, it's again down to less than 10 times the initial bankroll.
\[
\begin{array}{cc}
N & \text{Payoff} \\
\vdots & \vdots \\
61 & 22.6204 \\
62 & 22.6403 \\
63 & 22.6558 \\
64 & 22.6668  \\
65 & 22.6737 \\
66 & 22.6765  \\
67 & 22.6755 \\
68 & 22.6707 \\
69 & 22.6624 \\
70 & 22.6506 \\
\vdots & \vdots \\
311 & 9.977 \\
\vdots & \vdots \\
\end{array}
\]

Number of the beast

The number 666 is mentioned in the Bible (Revelation 13:18) and is traditionally associated with the devil, but also with roulette. The sum of all the numbers on the roulette wheel is 666, and its inventor François Blanc is said to have made a deal with the devil to obtain the secrets of the game. There is (of course!) a Numberphile video about this!

So 666 has to do with Antichrist and gambling and sin. But the number 66 is pretty badass too in a more modern way. It's associated with the Wild West and getting kicks from jazz music. Dangerous stuff.

And whenever you play roulette with the devil, play exactly 66 times!

Shed: Another card game

Here's another card game I sort of invented. I say sort of, because it's really just a simplified and pure form of a game that already exists.

There's a whole family of shedding type or beating games where the players take turns playing to a pile with the goal of getting rid of their cards. There are various constraints on the cards played, requiring you to somehow beat or match the previous card. If you can't play (or don't want to), you have to pick up cards, either from the pile or from a talon. Games of this type include Crazy Eights, Uno, Cheat, Bluffstopp (those last two are different games by the way), Vändtia (Turning Tens), Silltunna (Herring Barrel) and many more.

If you have my type of curiosity, you'll wonder how simple such a game can be and still be nontrivial.

So let's remove the special cards, forget about the different suits, and just have two people play with a deck of cards numbered from 1 to some number N. When it's your turn, you either play a higher card than the previous one, or pick up the whole pile. That's basically it. There is no talon and therefore perfect information. Your opponent has precisely the cards that are not in your hand or in the pile.

In traditional shedding games you normally win as soon as you get rid of your last card, but let's change that slightly in order to continue the game to its logical conclusion: Let's say you win only when your opponent picks up everything so that they have all the cards on their hand. That sort of makes it a misère game, since you win when it's your turn and you can't play.

We'll introduce another twist to the game in a moment, but let's start from just these rules and assume that the cards are somehow dealt randomly. Since this is the simplest shedding game I can think of, it seems fitting to call it Shed. Actually what we're discussing now is what I will eventually call Shed Endgames, the part coming before the endgame having to do with that twist.

But first things first. Here's an example showing that you sometimes want to pick up the pile even if you have a card that's high enough to play.

Suppose N = 5 and you deal the cards 1, 3, 4 to your opponent and 2, 5 to yourself. Your opponent starts with the 3. By the way, a note to the mathematicians out there who may otherwise be confused: You cannot pick up the pile if it's empty. In that case you have to play a card, but you can play any card you like (and if your own hand is empty too, that means you already won!).

Anyway, now it's your turn, and you can play the 5 or pick up the 3. It's not hard to see that you lose if you play, but win if you pick up. If you play the 5, your opponent picks up the 3 and the 5, and you play your last card, the 2. Then your opponent plays the 3, you pick up the 2 and the 3, and your opponent plays the following cards in the order 1, 4, 5 no matter what you do.

If on the other hand you pick up the 3 in the first place, play might go (with a notation I just invented, X meaning pick up):

3 - X, 1 - 2, 4 - 5, X - 3, 4 - X, 1 - 3, 5 - X, 2 - 3, X - 1, 2 - 4, X - 5, and you win.

If you try this game a few times with a small number of cards (say up to 13, one suit of a standard pack), you'll notice that most of the time the game is an easy win for the player who happens to have the better cards. If you have good enough cards, they will almost automatically get better. You will enter a good spiral where your opponent can only choose between picking up your bad cards or giving you their good ones. There are relatively few card distributions that are "balanced" enough for the game to be interesting.

We'll return to this issue in a moment, but before we continue, let's formulate some mathematical questions about this game:

Q1. Are there card distributions where the game is drawn under optimal play? In other words, are there hands where none of the players can force a win? The answer, as revealed by a small computer hack, is yes, but the smallest N for which this is possible is 10. It will happen for instance if you deal 1, 2, 6, 7, 8 to your opponent and 3, 4, 5, 9, 10 to yourself (following the convention that the person who didn't deal plays first).

An example of optimal play from these hands is  1 - 3, 6 - 9, X - 4, 6 - X, 1 - 4, 7 - X, 2 - 4, 8 - X, 3 - 4, 9 - 10, X - 5, X, and we are back to the original position but with the roles of the players reversed: You now have the hand 1, 2, 6, 7, 8, and it's your turn.

Q2. What are the asymptotical probabilities of dealer winning, draw, and first hand winning respectively? I'm assuming here that the cards are distributed with equal probabilities on all the 2 to the power of N different possibilities (By the way, how can you achieve this in practice with an Uno deck? Answer: you riffle-shuffle and then distribute the cards based on their orientation, which you can see even for the symmetric digits by looking at the "shadow"). One hypothesis is that the drawn positions are rare, of asymptotic probability zero. Another is that the advantage of playing first is getting smaller as the number of cards increases, and that asymptotically 50% of the times the dealer wins, and 50% of the times the first hand wins. But I have no idea how to try to prove any of this.

One thing I can prove though is that a player holding the four highest cards (that we may call the ace, king, queen and jack) can force a win. To demonstrate this, it suffices to show that a player holding only the fifth highest card (the ten) and playing first will lose. This can be checked for some reasonable values of N like 10 and 11, and one will see that the method is the same and works for arbitrary N. If you have the four highest cards and any other combination, you can pick up everything until your opponent has only one card left, and in the worst case that's the 10.

This means that the probability of a certain player winning a random deal is at least 1/16. So in any case the probability of a drawn position is at most 7/8, and in particular does not tend to 100%.

On the other hand I cannot even construct an infinite family of drawn positions. There are draws when N = 10 and when N = 12, but for all I know, drawn positions might not exist for any larger N.

Q3. How many moves can it take, at most, to force a win in the N-card game (as a function of N)? What do the hardest hands look like? And is there a simple mathematical solution to the game after all? Again I have no idea.

The twist: an open talon

As I mentioned earlier, there is a tendency for moderately good hands to almost automatically get better, quickly reaching a point where they "play themselves". The game will not be very exciting if nine times out of ten you can tell from a glance at your cards who is winning. Therefore we'd like to modify the game by introducing some other mechanism like a talon (maybe you can draw a card from the talon instead of playing) or some protocol of the type I-split-you-choose.

An idea that comes to mind is to start the game with all cards face up in an open talon. When it's your turn, you can play a card of your choice either from your hand or from the talon. The winning condition is still that your opponent should have all the cards on their own hand. You don't want to play the strong cards from the talon too early, because your opponent will get an advantage by simply picking them up. So it seems the game should now have a natural tendency to lead to the balanced and interesting positions. At the same time it removes the random element, since there is now a natural starting position.

From now on, this is the game that we call Shed, and the final phase when (if) the talon is exhausted is the endgame.

Perhaps surprisingly, Shed seems to be quite sharp and complicated. One might a-priori expect there to be a simple strategy that draws or that wins for a particular player (first or second), or perhaps that the outcome would depend on the parity of the number of cards. But there seems to be no such simple pattern. Shed with an N-card deck is a first-player win for N = 1, 4, 7, 10, 11, 13, 14 and 15, and a second-player win for N = 2, 3, 5, 6, 8, 9 and 12. The number of moves that it takes (counting the moves of the winning player) to force a win for N = 1,...,15 is 1, 2, 6, 8, 14, 16, 20, 30, 36, 45, 49, 58, 74, 68 and 91.

By the way, with a talon there are drawn positions already for N = 6 (though the starting position is not one of them). The second player wins under optimal play, but if the game starts 1 - 4 (correct), X - 2?, we reach a drawn position (the second player should have played the 3 instead in the second move). With optimal play from this point on, the game continues 5 - X, 1 - 6, X - 2, 4 - X, 1 - 4, X - 2, 4 - X, and so on. All those moves are unique, anything else loses, and the 3 stays in the talon forever.

There are some patterns in the data: It seems at first that when N is divisible by 3, the game is a second-player win. Moreover it appears that the second player should pick up the first card if the first player starts with a card in the top two thirds, but play something higher if the first card is in the lower third. This is true for N = 3, 6, 9 and 12. But the pattern is broken for N = 15, when the first player wins by starting with the 5 and then picking up even if the second player just plays the 6.

When N = 3k+1, the game seems to be a first-player win with the unique winning first move of playing the card k+1 from the talon (so that there remain exactly twice as many higher cards as lower cards). But it's hard to see a clear pattern in the following strategy, so maybe this too is just a red herring.

An intriguing observation is that there always seems to be a well-defined threshold at around N/3 with at most one card that wins as a first move for the first player, and all cards above the threshold losing because the second player picks them up. It seems clear that if the second player wins by picking up a certain card in the first move, they would also have won by picking up any higher card. It also seems very reasonable that the first player should never start with a card on the upper half, say, because the second player immediately gets an advantage by picking it up. But I don't see a reason why the first player could never win by playing a small card like the 1.

Some more questions: Are there infinitely many N for which Shed is a first-player win, and infinitely many for which it's a second-player win? Is there some N for which it's a draw? Is there a simple pattern to this, say periodic, after all? And is there some constant c between 0 and 1 such that the "threshold" for picking up in the first move is asymptotically at c times N? Is c = 1/3?

Multi-suit Shed, strict and relaxed

Can we play Shed with an ordinary deck with several different suits? Let's say that, just as in traditional card games, a card only counts as higher than another if it's higher in rank and in the same suit. So if you play first to the pile you can play any card you like, but all the following cards in that pile will have to be in the same suit as the first one.

Again the game seems to be complicated, and sometimes a first-player win, sometimes a second-player win, sometimes drawn. It seems to become drawish if there are many suits and few cards in each suit, and otherwise most often a first-player win. For instance 4-3-3-2 seems easy to draw, but 5-3-2-2 is a first-player win in 99 moves.

The game also seems to make sense with a joker or excuse which is lower than all other cards and may only be played first in a pile. For instance, 5-3-3 with a low joker is a tricky second-player win, but would be drawn without the joker. If on the other hand the joker is regarded as higher than the other cards (a wild-card that can be played anytime forcing the opponent to pick up the pile), the game seems to become completely drawish.

We can even play under the rule that one of the suits, say spades, is lower than all the others, so that a spade can be beaten by a higher spade or by a card of any other suit, while cards other than spades can only be beaten by higher cards in their own suit. For instance, the game 5-3-1-(3), where the ordinary suits have 5, 3, and 1 card respectively and the spade suit has 3 cards, is drawn under optimal play. You can draw by starting with the spade 1 or spade 3 (or with the smallest card in the suit of length 5), but if you start with the spade 2, your opponent has a forced win in 106 moves.

In principle, Shed can be played with an arbitrary partial order imposed on the cards. The rule that each card must beat the previous one might be called the Strict rule. But there is also another natural generalization of Shed to partially ordered decks: The rule can just as well be that a card can be played to the pile as long as it's not lower than any card already in the pile. This might be called the Relaxed rule. In Relaxed Shed, if you play the 9 of hearts, I can still play the 4 of clubs. You can then play any spade or diamond, and any heart higher than the 9 or club higher than the 4. Under the relaxed rule it seems that we must have a high wild-card or a trump-suit for the game to make sense, because unless there's a card that's higher than all others, the game is normally an easy draw.

Relaxed Shed might be played with cards from a tarot deck. In a tarot deck there is a designated trump suit of cards numbered from 1 to 21 (that's what I used in the second picture above) as well as the ordinary four suits.

Yet an example: In Relaxed Shed with suits of 4-3-2 and a trump suit of 3, first-hand has a forced win in 66 moves. The unique winning first move is to play the 3 of the suit of 4, and in the line I looked at, the first 13 moves, and 45 out of the first 50, where "unique" in the sense that any other move would have lost. Amazing stuff.

 Why should we care?

I guess for now, Shed will have to be just another artificial card game that you probably won't play unless you just want to see how weirdly difficult a game can be with just ten or so cards face up. But I might explain in some later blog post that it has certain features that makes it interesting to experiment with. In particular it seems to be a complex and razor sharp game that has "board-feel" and scales easily. There are difficult positions, but also easy ones. The level of difficulty might be varied in a rather controlled way. Maybe someone can see where this is going.