Saturday, December 20, 2014

Rundschack, primtal, och månfärder

Rundschack är en schackform som jag fick idén till här om dagen (nytt eller finns redan?). Man går omkring mellan ett antal bräden och gör ett drag här och ett drag där enligt ett visst schema. Funkar särskilt bra om man är 3, 5, eller 7 spelare (eller 11 eller 13), och ingen behöver ha frirond! Låt oss som exempel ta 7 spelare som får “startnummer” A, B, C, D, E, F, G. Vi ställer upp 7 bräden som vi numrerar 1 till 7. Till att börja med får A ställa sig vid bräde 1, B vid bräde 2 osv. Varje spelare gör drag 1 för vit vid sitt bräde och flyttar därefter 1 steg upp i brädnummer, så att A hamnar vid bräde 2, B vid bräde 3 osv. G som stod vid bräde 7 går till bräde 1. Vi kan tänka oss att brädena står i en cirkel och att alla tar ett steg medsols.

Nu gör var och en drag 1 för svart på sitt nya bräde. Sedan tar de ett steg till medsols, och gör drag 2 för vit. Sedan ytterligare ett steg medsols och gör drag 2 för svart. Då kanske ni tror att ni har förstått systemet, men så här kan det inte fortsätta! Då skulle man få svart när man är tillbaka där man startade, och alla skulle spela omväxlande vit och svart på alla bräden. Men ska det bli spännande vill man ju inte spela mot sig själv!

Så efter drag 2 för svart går man 3 steg medsols. Nu har spelare A hunnit upp till bräde 7, B står vid bräde 1, osv. Nu gör man drag 3 för vit, sedan är det 2 steg motsols, drag 3 för svart, och sedan 3 steg medsols. I det läget har det gjorts 3 drag med vit och 3 drag med svart på varje bräde, och alla spelare är tillbaka där de började. Nu börjar det om igen, så att drag 4-6 spelas exakt som drag 1-3, och så fortsätter det.

Hela schemat kan memoreras med talserien +1, +1, +1, +3, -2, +3. Varje spelare ska alltså gå så att brädnumret ökar med 1, ökar med 1, ökar med 1, ökar med 3, minskar med 2, och ökar med 3. Och då har man gått ett varv. Brädena står cirkulärt så att 8=1, 9=2 osv. Det finurliga med just den här talserien är att var och en spelar 6 olika partier, vit i 3 och svart i 3, och att man får varje annan spelare som lagkamrat i 2 partier och motståndare i 3 partier. Tittar vi på schemat bräde för bräde, ser det ut så här:

1. AFB - GED
2. BGC - AFE
3. CAD - BGF
4. DBE - CAG
5. ECF - DBA
6. FDG - ECB
7. GEA - FDC

Det här betyder att vid bräde 1 till exempel, spelar A, F, och B i det vita laget, och G, E, och D i det svarta. Spelare C har “frirond” och hoppar över det här brädet. De som spelar kommer att göra vart tredje drag med sin färg. A gör drag 1, 4, 7, osv med vit, F gör drag 2, 5, 8, och B gör drag 3, 6, 9.

När alla partierna är färdigspelade, kan man summera poängen för var och en och kora kvällens mästare i rundschack!

Det får nog rekommenderas att man skriver protokoll vid varje bräde, och att spelarna signerar sina drag med någon initial. Då kan man lätt se vems tur det är, så att det blir rätt. När man ska göra ett drag, kollar man att man själv spelade för 3 drag sedan. Man ser också vad som har hänt sedan sist, så att man till exempel vet om man får slå en passant. Det är nog också enklast om alla går på samma sida av brädena (egentligen skulle de behöva stå på något slags Möbiusband), även om det kan kännas lite ovant att stå från vits sida och spela svart.

Slutligen är frågan hur man gör med betänketiden. Ska man ha en maximal betänketid per drag, eller ska det stå en klocka vid varje bräde? Mitt förslag, utan att ha testat detta i praktiken, är både och. Det får stå en klocka vid varje bräde, och den ska vara av gammaldags typ så att man lätt kan stanna båda klockorna. Om nästa spelare redan väntar, trycker man över kläppen som vanligt när man har gjort sitt drag, och annars sätter man den i neutralt läge, och nästa spelare får slå igång sin egen betänketid när de kommer till brädet. För att det ska flyta på kan man också ha en maxtid per drag. Någon får då hålla reda på tiden och ryta till när det är dags att bestämma sig.

Det kan bli svårt att överblicka vad som händer i varje parti under spelets gång. Men har man protokoll, kan man gå igenom ett par partier på demobräde efteråt och skratta åt varandras tabbar och vilka knäppa partier man har åstadkommit tillsammans! 

Det är lätt att konstruera motsvarande schema för 5 spelare med talföljden +1, +2, -1, -2, vilket ger

1. AC - ED
2. BD - AE
3. CE - BA
4. DA - CB
5. EB - DC

För den talteoretiskt intresserade: Om antalet spelare är ett primtal, kan man konstruera schemat genom att låta den spelare som inte spelar på högsta bordet ha vit på bräden med "kvadratiska" nummer (se nedan) och svart på bräden med "icke-kvadratiska" nummer. Sedan bestämmer man hur den spelaren ska röra sig så att det blir vitt vartannat drag och svart vartannat, och så korta steg som möjligt. Hela schemat följer sedan genom att man roterar den spelarens schema.

Kvadratiska tal betyder här tal som är rest av en kvadrat vid division med primtalet i fråga. För 7 spelare är 1, 2, och 4 kvadratiska: $1 = 1^2$, $4 = 2^2$, och 2 är resten av $3^2$ vid division med 7. Talen 3, 5, och 6 är icke-kvadratiska. Nu ska man gå runt och vara varannan gång på 1, 2, 4 och varannan gång på 3, 5, 6. Om man börjar på 2 räcker det med ett steg de tre första förflyttningarna, och det var så schemat konstruerades. För 11 spelare är 1, 3 (=25), 4, 5 (=16), och 9 kvadratiska, och schemat blir (till exempel) +1, +1, +3, -2, +3, -2, +3, +1, +1, +2.

När antalet spelare inte är ett primtal blir det lite mer komplicerat, och man får antagligen ha fler bräden än spelare. Om antalet spelare är jämnt, kan man också tänka sig att man går ett steg hela tiden. Då blir det samma indelning i lag på varje bräde, och alltså en match mellan två lag.

Om man inte gillar det här med att någon lagkamrat ska komma och förstöra ens planer, kan man bryta upp schemat i ronder där man spelar två vanliga partier samtidigt (relaterat: tydligen finns det något som heter baskiskt schack, enda sporten vars utövande kräver kontorsstolar med hjul?). Då blir det bara ett sätt att köra en turnering på udda antal spelare utan frironder. Man sätter sig på något sätt i en ring där man spelar mot sina två grannar. För 7 spelare blir det 3 ronder:

Rond 1:  A - B - C - D - E - F - G - A.

Alltså A har vit mot B som samtidigt har vit mot C osv. Till rond 2 byter man plats så att man hamnar granne med dem vars "startnummer" ligger 2 från ens eget:

Rond 2:  A - C - E - G - B - D - F - A.

Och i rond 3 möter man dem med startnummer 3 ifrån ens eget.

Rond 3:  A - D - G - C - F - B - E - A.

Så vad har detta med månfärder att göra? Jo, vi är några som får gåshud av att se den här bokstavsföljden, och för vårt inre hör Frank Sinatra och Fly Me To The Moon. Men bara för att man har en stark känsla för grundtonen är man ju inte basist!





Wednesday, November 12, 2014

Datorn kommenterar schack-VM

Nu har VM-matchen i schack mellan norrmannen Magnus Carlsen och indiern Viswanathan Anand kommit igång på allvar. Carlsen tog ledningen genom att vinna söndagens parti, men i går eftermiddag lyckades Anand kvittera och ställningen är nu 1.5 - 1.5 efter tre partier (av 12). 


Man kan förstås följa partierna live med expertkommentatorer (till exempel via NRK), och det twittras och diskuteras flitigt.

Eftersom schackprogrammen är så starka numera, riktas stor uppmärksamhet mot den löpande utvärderingen av partiställningarna som presenteras av program som Houdini och Stockfish. Datorns siffror dryftas som om de vore mellantider i skidåkning. Carlsen förväntas få åtminstone +0.15 i spelöppningen om han har vit, och i går tändes ett fåfängt hopp om remi när Anand rockerade och Stockfish plötsligt omvärderade ställningen från omkring +1.0 (i Anands favör) till runt +0.6. 

Vi är många som retar oss lite på det här, och tycker att det tar bort lite av magin runt VM-matcherna. När en spelare gör ett oväntat drag, är det alltid dåligt. De briljanta kombinationerna har publiken redan sett, och skulle de reproduceras på brädet är det bara vad man förväntar sig.

Samtidigt är det förståeligt att den som ska gälla för expertkommentator vill kunna snegla på datorn, eftersom det annars inte finns en chans att i realtid ge lika relevanta kommentarer.

Det är en kliché bland schackspelare att man inte ska lita på datorernas ställningsvärderingar. Bara för att Stockfish säger -0.28 betyder det inte att svart står bra. Siffrorna ska tas med en nypa salt heter det, och motiveringarna brukar vara:

(a) Datorer är bra på taktik men saknar mänskliga toppspelares förståelse av de mer långsiktliga strategiska aspekterna.

(b) Även om en ställning skulle vara bra för Stockfish, innebär det inte att den är bra för en mänsklig spelare. Kanske är ställningen objektivt vinst för svart, men så full av taktiska blindskär att den i praktiken är fördelaktig för vit när människor spelar.

Stämmer det att mänskliga stormästare fortfarande är bättre än datorn på att bedöma ställningar, eller är det bara önsketänkande?

Förklaring (b) rymmer väl ett uns av sanning, medan (a) egentligen är goddag yxskaft. Som schackprogrammen fungerar, väljer de helt enkelt det drag som får bäst poäng. De siffror Houdini och Stockfish presenterar utgör alltså hela underlaget för vilka drag de skulle välja om de själva spelade. De är så att säga “bara så bra som sin ställningsvärdering” (även om begreppet då måste förstås som att variantanalysen är en del av hur programmet värderar en ställning).

Om siffrorna vore uppåt väggarna fel, borde de leda programmen till dåliga beslut. Men eftersom programmen faktiskt spelar mycket bättre än Carlsen och Anand, är deras sätt att värdera ställningar uppenbarligen effektivt.

Vi kan också se att små skillnader är betydelsefulla. Ibland finns ett helt spektrum av drag från de vassaste, som till exempel bedöms ge en fördel på 0.3, via diverse klåpar- och amatördrag på mellan 0 och 0.25, ner till olika tabbar och bortsättningar som ger motståndaren fördel. Nyanser som värderas till några hundradelar av en bonde är många gånger det enda som skiljer superprogrammen från oss vanliga klubbspelare.  

Det ligger nära till hands att dra slutsatsen att datorns siffror ger ett oerhört exakt mått på Carlsens och Anands utsikter i den aktuella ställningen.

Men som alla vet som någon gång har försökt programmera en dator att spela spel (hm, det kanske inte är så många, men ni borde testa, det är kul!), finns en frustrerande brist på korrelation mellan precision i bedömningen av hur bra en ställning är, och å andra sidan resulterande spelstyrka.

För att förstå det här får man tänka på att spelstyrka bara handlar om att jämföra de ställningar som kan nås i ett drag från den aktuella ställningen. Ett program som konsekvent övervärderar eller undervärderar alla ställningar av en viss typ kan därför ändå fatta bra beslut.

Som ett tankeexperiment kan vi föreställa oss ett program som anser att det är till stor fördel för vit om det finns många pjäser kvar på brädet, och omvänt till stor fördel för svart om det finns få pjäser kvar. Om dess sätt att värdera ställningar är bra i övrigt, skulle det ändå kunna spela i världsklass! Pjäserna försvinner ju bara från brädet en i taget, så i varje given ställning är över- eller undervärderingen i stort sett konsekvent. För det mesta väljer programmet därför rätt drag, och gör aldrig några dundertabbar, trots att det vid förfrågan svarar att vit har förkrossande fördel i utgångsställningen, medan svart står överlägset när bara kungarna är kvar.  

Stockfish och de andra programmen är skrivna för att göra bra drag, inte korrekta ställningsvärderingar. Även om de senare ligger till grund för de förra, är det på något sätt så att helheten får vara fel, bara detaljerna blir rätt. 

Datorns värderingsfunktion är lite som en världsatlas på bokform. I stora drag stämmer det inte. Flyger man från Stockholm till Los Angeles åker man inte över de brittiska öarna, utan över Grönland. Som är stort, men inte som hela Sydamerika.

Men tittar man på ett enskilt land, är den platta kartan fullt användbar. Eftersom alla orter i Spanien ligger fel på ungefär samma sätt i förhållande till resten av europakartan, kan man dra korrekta och användbara slutsatser om hur man tar sig från en spansk ort till en annan (exempelvis Berlin).

På samma sätt kan ett datorprogram göra helt fel bedömning av utsikterna att vinna ett visst slutspel, och ändå spela grymt bra genom att systematiskt göra samma felbedömning i alla ställningar av den typen.

Man skulle kunna tro att det här isolerar schackprogrammens överlägsenhet till att deras taktiska förmåga kompenserar för brister i planering och långsiktligt manövrerande. Men det finns ytterligare en twist!

Att konsekvent följa en plan (eller åtminstone spela som om man hade en) och inte bara flytta pjäserna fram och tillbaka, verkar inte heller hänga på korrekt ställningsvärdering! Det finns klara skillnader mellan människors och datorers sätt att spela schack, men i just det här avseendet är vi ganska lika. Även vi kan många gånger ha lättare att identifiera en plan och välja rätt drag, än att bedöma våra utsikter att vinna. När slutspelet närmar sig, vet vi att kungen ska centraliseras. Vi vet att den står bättre på f2 än på g1, och ännu bättre på e3, men skulle vi försöka bedöma våra utsikter, kanske vi är helt fel ute i alla tre ställningarna. Precis som Stockfish. Och ändå spelar vi som om vi begriper vad vi gör, och går mot centrum med kungen!

Tuesday, July 22, 2014

Är blattar bättre än svennar på yatzy? Statistikexperiment för sverigedemokrater och andra.

En illustration publicerad av SDU (Sverigedemokratisk ungdom) den 15 juli visar de mest överrepresenterade namnen bland svenska fängelsedömda. Listan toppas av Tomasz följt av Zoran, Marek, Marko, Krzysztof, Igor, Pawel och så vidare.

Jag får en känsla av att vi är överens, jag och redaktionen på SDU, om att det här är vad man hade väntat sig. Men att vi har lite olika uppfattningar om varför listans utseende är som förväntat.

Att runt 95% av internerna är män är ingen hemlighet, och det är nog inte det som är tänkt att vara poängen. Något som tycks vara centralt för SDU är i stället överrepresentationen av invandrare bland fängelsedömda.

Går man till kriminalvårdens webbplats hittar man statistik av vilken det framgår att runt en tredjedel av fängelseinternerna i Sverige är utländska medborgare (jämfört med cirka 7% av hela befolkningen). Någon motsvarande statistik för utomlands födda verkar inte finnas, men det är hur som helst klart att utländsk härkomst är en av de saker som korrelerar med att bli dömd för brott. Liksom en rad andra parametrar som ålder, kön, inkomst, bostad, utbildningsnivå osv.

Vad SDU har tänkt göra för att grupper som exempelvis män ska integreras bättre i samhället framgår inte på deras webbsidor. I stället verkar det vara viktigt att ge en bild av att det främst är polacker, araber och romer som begår brott i Sverige. Eventuellt någon finne.

Facebooksidan Slutpixlat publicerade snabbt ett svar med en illustration av vilka namn som i själva verket dominerar på de svenska fängelserna. Den visar inte “överrepresentation”, utan absoluta tal, och då heter internerna i stället Johansson, Andersson, Mikael och Peter. Så vilken bild är den sanna?

Dags för lite vetenskaplighet. Det framgår inte vilken metod redaktionen på SDU har använt för att få fram sin topplista, men det ligger nära till hands att titta på förhållandet mellan antalet personer som har ett visst namn och antalet domar mot personer med detta namn. Troligen har man sorterat bort alltför ovanliga namn, då topplistan i annat fall skulle ha dominerats av namn som bara en handfull personer har, och där det räcker att en person döms ett par gånger för att “överrepresentationen” ska bli enorm.

En del av det som ibland kallas för ett "vetenskapligt förhållningssätt" är idén att formulera en så kallad nollhypotes, och försöka förstå hur världen skulle se ut om den vore sann. I det här fallet skulle en nollhypotes bestå i att det inte fanns någon korrelation alls mellan namn och fängelsedomar.

För att undersöka hur det då skulle bli, klickade jag fram statistik över de 1000 vanligaste mansnamnen i Sverige. Kanske borde jag ha tagit med både kvinno- och mansnamn, men jag ville fokusera på det här med “svenska” kontra “utländska” namn och få en tydlig jämförelse med SDUs bild.

Listan börjar med Erik, 300974 personer, och nummer tusen är Isa, 562 personer. Summerar man blir det drygt 9 miljoner. Det borde vara runt hälften eftersom det bara är män, så det kan inte vara enbart tilltalsnamn. Å andra sidan finns även dubbelnamn (med och utan bindestreck) som Lars-Åke och “Lars Åke” med i listan. Men jag orkar inte reda ut exakt hur statistiken är gjord, min poäng ska nog framgå ändå.

Grovt räknat sitter en man på tusen i fängelse. För att få något som är helt slumpmässigt och i väldigt runda slängar lika vanligt, simulerar jag att var och en av drygt 9 miljoner personer med namn från listan kastar fem tärningar. Att få “yatzy” (samma utfall på alla fem) motsvarar att sitta i fängelse. Egentligen borde väl “kåk” motsvara kåken, men det är lite för vanligt. Sannolikheten att få yatzy är en på 1296, så av 300000 Erik till exempel, väntar vi oss att runt 230 ska få yatzy.



Mitt datorprogram får sedan räkna ut andelen personer med yatzy för varje namn, och göra en topplista med de mest “överrepresenterade” namnen bland dem som fick yatzy, på samma sätt som SDU gjorde med fängelsestatistiken.

Resultat:

Dino 7.6595745
Enes 6.881416
Mostafa 5.12253
Sabah 5.102362
Janos 4.729927
Sylve 4.5633802
Taha 4.5553603
Maurits 4.3932204
Pavel 4.312812
Kay 4.263158
Abdallah 4.173913
Carl-Magnus 4.0
Mattis 3.9272726
Erich 3.891892
Jan Olof 3.595007
Ante 3.570248

Siffrorna visar “överrepresentationen”. Det betyder att bland dem som heter Dino var antalet yatzy 7.65 gånger det förväntade antalet. Det finns 846 Dino, så det förväntade antalet var 846/1296, ungefär 0.65. Den enorma överrepresentationen beror på att fem av dem råkade få yatzy den här gången. Mitt program skriver ut dem som har en överrepresentation på minst 3.5. Jag tyckte det blev en lagom lång lista då.

Det fina med simuleringar är att man kan köra dem hur många gånger man vill. Nästa gång blir det:

Raul 7.160221
Pavel 6.469218
Damir 6.0750003
Eduard 4.5876107
Francis 4.5526934
Matts 4.4786177
Jesus 4.4536085
Jozsef 4.263158
Ferenc 4.180645
Zoltan 4.0818896
Salman 3.981567
Bengt-Erik 3.97546
Stephen 3.888
Anas 3.84
Aulis 3.795022
Andy 3.7894738
Louis 3.7262795
Claus 3.6870553
Nikolaos 3.6765957
Jan Olof 3.595007

Jesus [xeˈsus] vilka namn, kommer de verkligen från Sverige? Och se upp med de här Pavel och Jan Olof, nu har de varit med två gånger!

Vi tar en till:

Carl-Henrik 4.896725
Zbigniew 4.8660827
Hanna 4.7184467
Taha 4.5553603
Ismet 4.5156794
Halvard 4.3932204
Dawid 4.305648
Walid 4.2306857
Abdallah 4.173913
Wiktor 4.1638556
Ryszard 4.133971
Adem 4.133971
Karl-Axel 4.101266
Anwar 4.037383
Constantin 3.9938369
Salman 3.981567
Janusz 3.9392097
Karl-Gustaf 3.9095023
Johann 3.8533201
Seyed 3.8155053
Aulis 3.795022
Alaa 3.7729259
Laszlo 3.7277086
Gillis 3.7155964
Nikolaos 3.6765957
Melwin 3.6277118
Ronald 3.570248
Jamal 3.5628865

Spela aldrig tärning med utlänningar och folk med dubbelnamn, de fuskar hela tiden!

Efter några körningar blir mönstret tydligt. Det är mycket "invandrarnamn", och här och där något dubbelnamn och någon ovanlig stavning. Varför blir det så? Varför har aldrig Anders, Johan och Mikael samma tur med tärningarna som Abdulrahman, Mateusz och Nils-Åke?

Det är ingen konspiration. Mitt datorprogram vet inte vilka namn som är "svenskklingande" och vilka som är "utländska", utan det som händer är att topplistan domineras av de ovanligare namnen. Namn som är ovanliga i Sverige uppfattas som utländska för att de är, tja, ovanliga i Sverige. Undantagen, de namn som är ganska ovanliga i Sverige och ännu ovanligare utomlands, är främst dubbelnamn och udda stavningar, och för all del ett och annat ålderdomligt namn.

Och varför kommer de ovanliga namnen högre upp? Får man oftare yatzy om man heter något konstigt? Nej det får man inte, men det blir större spridning i statistiken. För att ett namn med 500 eller 1000 bärare ska komma över min godtyckligt satta tröskel på 3.5 krävs bara att ett par-tre av dem råkar få yatzy. Lite sådär osannolikt, men inte extremt. Att däremot något av de 100 vanligaste namnen skulle komma med är praktiskt taget uteslutet. Nummer 100 på listan är Ola med 20778 bärare. Förväntade antalet Ola med yatzy är ungefär 16, så det är för det mesta 10-20 stycken. En liten uträkning visar att sannolikheten att Ola kommer över tröskeln på 3.5*16=56 är runt en på tusen biljoner.

Och Ola var nummer hundra. Att "Erik" skulle kvala in med 800 yatzy i stället för det normala 200-250 är så osannolikt att vi får börja tramsa om att varje partikel i det synliga universum är en dator som kör en miljard simuleringar i sekunden alltsedan Big Bang. Och det händer ändå inte en enda gång.

Så vad betyder det här? Är inte invandrare överrepresenterade i brottsstatistiken? Jo, förmodligen är de det. Men illustrationen på SDUs webbsida ger inget stöd för detta. I stället ser den ut ungefär som man hade väntat sig om det inom gruppen män inte fanns någon korrelation mellan namn och fängelsedomar!












Sunday, June 1, 2014

Heltalsmetoden med valtekniska block: Så funkar ett schysst valsystem!

I en debattartikel på SvD brännpunkt hävdar jag att fyraprocentsspärren till riksdagen bör avskaffas, eftersom den motverkar sitt syfte. Jag ska inte upprepa argumenten här, utan i stället redogöra i lite mer detalj för det system jag antyder i slutet av artikeln.

I dag, det vill säga baserat på valet 2010, har kombinationen M+C+V+MP fler röster bakom sig än de övriga riksdagspartierna S+FP+KD+SD, men trots detta färre riksdagsplatser. Att det inte har blivit mer rabalder om detta beror förstås på att ingen ideologisk skiljelinje går mellan miljö-höger-vänstern och de krist-fascistiska folksocialisterna, och att det ändå inte är aktuellt att de förra bildar regering med de senare i opposition. Men ju fler partier vi får i riksdagen, desto större blir risken att knasigheterna i valsystemet drabbar en regeringsaktuell partikonstellation.

En enkel demokratisk princip, baserad på att maximera handlingskraft med respekt för jämlikhet, är att en politik som stöds av mer än 50% av väljarna ska kunna genomföras. Det ideala vore ett valsystem som har följande egenskap:

Majoritetsprincipen: En grupp av partier som tillsammans får mer än hälften av rösterna ska också ha mer än hälften av riksdagsplatserna.

Den här tanken, som visar sig behäftad med vissa svårigheter, kan ändå betraktas som grunden till idén om proportionalitet. Om varje partis andel av riksdagsplatserna vore exakt lika med dess andel av rösterna, skulle majoritetsprincipen automatiskt vara uppfylld.

Dessvärre är det inte möjligt att konstruera ett system som garanterat uppfyller majoritetsprincipen. Detta inses enklast med ett urartat scenario. Antag att det fanns 700 partier och alla fick lika många röster. Eftersom det bara finns 349 platser i riksdagen, kan högst 349 partier få någon plats överhuvudtaget. Övriga 351, som har en majoritet av väljarna bakom sig, får ingen plats alls. Detta var ett extremt exempel, men det visar i alla fall det lönlösa i att försöka hitta ett system som av matematiska skäl garanterar majoritetsprincipen.

Vi behöver revidera majoritetsprincipen, och man kan då tänka sig att en grupp av partier skulle ha möjlighet att anmäla till valmyndigheten att man bildar ett block, och att man därför vill garantera att om man tillsammans får en majoritet av rösterna, ska man också tillsammans få majoritet i riksdagen. I Sverige idag skulle allianspartierna M+C+FP+KD bilda ett sådant block, medan det förmodligen skulle bli hårdare förhandlingar på vänstersidan. Ett block skulle vara ett svagt valtekniskt samarbete, och samtidigt en signal till väljarna att man kan tänka sig bilda regering tillsammans. Men det skulle inte utgöra något kontrakt, regeringen skulle fortfarande utses av riksdagen.

Platserna i riksdagen skulle sedan fördelas i två steg: I en första runda behandlas alla block som om de vore enskilda partier. I en andra runda fördelas sedan blockens riksdagsplatser mellan partierna inom varje block.

Om ett sådant system ska fungera, måste partierna ges incitament att bilda block. Det får inte vara så att en partigrupp förlorar platser på att bilda ett valtekniskt block jämfört med om de med samma valresultat inte hade bildat ett block. Detta kan vi formulera så här:

Koalitionsprincipen: Valsystemet bör ha egenskapen att om två partier slås ihop till ett (med bibehållet valresultat), får det sammanslagna partiet minst lika många riksdagsplatser som de två ursprungliga partierna hade fått tillsammans.

Koalitionsprincipen (som alltså med dagens system inte är uppfylld) är intressant, därför att den visar sig vara möjlig att uppfylla, och därför att den får långtgående konsekvenser. Till att börja med innebär den att ett parti som får egen majoritet bland väljarna också måste få egen majoritet i riksdagen, i alla fall om antalet platser är udda. De övriga partierna ska ju inte kunna få fler platser genom att dela upp sig.

Men eftersom blocken i första rundan ska behandlas som enskilda partier, innebär den automatiskt att ett block med majoritet av rösterna också får majoritet i riksdagen.

Finns det då något bra valsystem som uppfyller koalitionsprincipen? Ja, det finns det faktiskt. Bland de etablerade proportionella metoderna finns den så kallade heltalsmetoden, en släkting till den metod (uddatalsmetoden) som ingår i det nuvarande valsystemet.

Heltalsmetoden


Heltalsmetoden är den enklaste av de så kallade divisormetoderna, dit även uddatalsmetoden hör. De här metoderna brukar förklaras på ett fantastiskt opedagogiskt sätt som att man ska hålla på och dividera med heltal och udda tal. Jag ska beskriva dem på det vettiga sättet, genom att börja med det färdiga resultatet.



Parti Röster Mandat
M 1 791 766 106
C 390 804 23
FP 420 524 25
KD 333 696 19
S 1 827 497 108
V 334 053 19
MP 437 435 26
SD 339 610 20
PP 38 491 2
FI 24 139 1
SPI 11 078 0

Den här tabellen visar hur mandatfördelningen i riksdagen skulle ha sett ut om den hade baserats på det totala antalet röster i riket (2010) och heltalsmetoden. Och hur kan vi verifiera att detta stämmer? Jo, det fina är att heltalsmetoden bestämmer hur många röster en riksdagsplats kostar. I valet 2010 var det 16800. Eller egentligen vad som helst mellan 16767 och 16820, men säg 16800. Med det priset kan moderaterna med sina 1791766 röster köpa 106 platser. Dessa kostar 106 * 16800 = 1780800, så M får drygt 10000 röster över. Centern kan för sina 390804 röster köpa 23 platser, osv. Har man en miniräknare och får veta priset på ett mandat, är det lätt att kontrollera att det stämmer.

Så hur bestäms priset? Jo, villkoret är helt enkelt att partierna tillsammans ska ha råd att köpa precis 349 platser. I det här fallet visar det sig att om priset sänks till 16766, har S råd att köpa 109 platser, så då blir det 350 totalt, medan om priset höjs till 16821, har FP bara råd med 24, vilket ger totalt 348. Men i intervallet 16767 - 16820 blir totala antalet köpta platser precis 349.

Det här med att man ska dividera med 1,2,3 osv har att göra med hur priset räknas ut från början. Man kan tänka sig att priset först är oändligt stort och sedan successivt sänks, och att vi kontinuerligt håller koll på hur många platser varje parti har råd med. När priset kommer ner till 1827497 har S råd med ett mandat, och om riksdagen bara hade en stol, skulle den bli socialdemokratisk. Strax därefter kommer priset ner till 1791766, och då har även M råd med en plats.

Nästa parti som får råd med en plats är MP, som kommer att få sitt första mandat när priset når ner till 437435. Men dessförinnan kommer både S och M att ha fått sina andra stolar. För att räkna ut var nästa tröskel blir (i det läge då S och M har ett mandat var och inget annat parti ännu har råd med någon plats), kollar vi för varje parti hur långt ner priset måste gå för att partiet ska ha råd med ytterligare en plats utöver vad det redan har. För S och M som redan har en plats, dividerar vi antalet röster med 2, eftersom de kommer att ha råd med en andra plats när priset går ner till halva deras antal röster. För övriga partier är det fortfarande det ursprungliga antalet röster som är nästa tröskel. Det parti vars nästa tröskel är högst är S, med 1827497/2 = 913748.5, och när priset når ner dit får de sitt andra mandat. I nästa steg blir "jämförelsetalet" för S lika med 1827497/3= 609165.666... osv. När priset till slut når ner till 16820.96 och FP har råd med sitt 25:e mandat, har vi fördelat alla 349 riksdagsplatserna. Hade vi fortsatt ett steg till, skulle nästa tröskel ha varit vid 16766.02752, då S får råd med sitt 109:e mandat. Det är alltså i intervaller däremellan som det totala antalet platser blir 349.

Om vi hade tillämpat det här systemet, kunde morgontidningarna ha publicerat ovanstående tabell och talet 16800 så att en mellanstadieunge med miniräknare hade kunnat kontrollera mandatfördelningen. Lägg märke till att det är enklare att verifiera att resultatet är korrekt, än att från början räkna ut det.

Som valsystemet fungerar idag kan man inte ens räkna ut mandatfördelningen utifrån partiernas totala antal röster, eftersom den på ett komplicerat sätt beror av vilka valkretsar rösterna kommer från.

Uddatalsmetoden


Men uddatalsmetoden, hur var det med den då? Jo, även den bygger på att man sätter ett "pris" på riksdagsplatserna. Den ovannämnda heltalsmetoden kan sägas bygga på avrundning neråt. Vänsterpartiets 334053 röster till exempel, räcker med priset 16800 röster/mandat till 19.86 mandat, och de får då 19 platser. Filosofin bakom uddatalsmetoden är att det blir mer rättvist att avrunda till närmaste heltal. Liknelsen med att partierna "köper" platser till ett visst pris stämmer då inte riktigt, men kanske kan vi jämföra med hur min generation som barn köpte smågodis. Man lämnade fram de mynt man hade i fickan, och gubben eller gumman i kiosken plockade ihop godis för det beloppet. Gick det inte jämnt upp, kunde man få en extra chokladbit. Med uddatalsmetoden köper partierna riksdagsplatser, men när det inte går jämnt upp avrundar man till närmaste heltal i stället för neråt. Eftersom det är ett generösare system, men antalet mandat ändå ska bli 349, blir priset per mandat aningen högre med uddatalsmetoden än med heltalsmetoden.

Med valet 2010 som exempel visar det sig att det blir 349 platser köpta om priset ligger i intervallet 17113 till 17130. Vi kompletterar ovanstående tabell med ytterligare en rad:



Parti Röster Heltal (16800) Uddatal (17120)
M 1 791 766 106 105
C 390 804 23 23
FP 420 524 25 25
KD 333 696 19 19
S 1 827 497 108 107
V 334 053 19 20
MP 437 435 26 26
SD 339 610 20 20
PP 38 491 2 2
FI 24 139 1 1
SPI 11 078 0 1

Som synes är det bara enstaka platser som byter ägare. För de stora partierna S och M blir differensen i pris mer relevant än avrundningsregeln, och de får ett mandat mindre till uddatalsmetodens högre pris. För små partier blir det mer relevant hur man avrundar, och SPI som egentligen inte har röster till ett helt mandat får ändå ett med uddatalsmetoden.

Så varför heter det uddatalsmetoden? För att beräkna de "priströsklar" där ett parti får råd med ytterligare ett mandat, ska vi i detta fall dividera antalet röster med 0.5, 1.5, 2.5, 3.5 osv, eftersom det är när man passerar dessa "halvtal" man får ytterligare en plats. Men då blir det enklare att i stället utgå från priset för ett halvt mandat, och dividera med 1, 3, 5, 7 osv.

Uddatalsmetoden uppfyller inte koalitionsprincipen. Till exempel kunde FI ha fått ett extra mandat genom att dela upp sig i två partier, FI1 och FI2, med runt 12000 röster var. Priset på ett mandat hade bara förändrats marginellt, så FI1 och FI2 hade fått varsin riksdagsplats. Det är lite som om vi skulle få mer godis om vi köper för en femma två gånger (och får två snälla avrundningar), än om vi köper för en tia. Uddatalsmetoden uppfyller heller inte majoritetsprincipen. Ett parti kan få egen majoritet av rösterna och ändå inte majoritet i riksdagen.

Det sägs ibland, ofta utan motivering, att uddatalsmetoden har "bättre proportionalitet" än heltalsmetoden. Detta kan ifrågasättas, och det handlar hur som helst om finlir och avrundningar. Det system vi har idag med spärrar, valkretsar och jämkning går avsevärt hårdare åt proportionaliteten.

Heltalsmetoden, koalitionsprincipen, och valtekniska block


Det är ganska enkelt att inse att heltalsmetoden uppfyller koalitionsprincipen (och detta är givetvis inget nytt). Med heltalsmetoden måste man ha det erforderliga antalet röster för att få ett visst antal mandat, det blir ingen snäll avrundning uppåt. Om två partier A och B har röster som räcker till, säg, 10 respektive 15 riksdagsplatser, måste de alltså tillsammans ha det antal röster som krävs för 25 platser. Om man slår ihop dem med bibehållet valresultat, ska det alltså räcka till minst 25 platser. Men vänta nu, priset per riksdagsplats påverkas ju av valresultatet. Kan det inte bli så att priset ökar när partierna slås ihop, så att det sammanslagna partiet inte har röster till 25 platser? Nej, det kan det inte. Om priset ökar, kommer ju övriga partier aldrig att kunna få fler platser!

Så hur hade det gått 2010 om man hade tillämpat det system jag här föreslår? Tittar man på tabellen, ser man att allianspartierna tillsammans får 173 platser med den rena heltalsmetoden. Om de i stället hade bildat ett valtekniskt block, visar det sig att de skulle ha fått 174 platser tillsammans. De hade så att säga kunnat lägga sina överblivna röster i en hög, och högen hade räckt till ytterligare en plats (som MP hade blivit av med). Vi hade fått följande tabell:



Parti / Block Röster Mandat (16878)
Alliansen 2 936 790 174
S 1 827 497 108
V 334 053 19
MP 437 435 25
SD 339 610 20
PP 38 491 2
FI 24 139 1

I en andra runda skulle alliansens 174 platser ha fördelats mellan allianspartierna, åter med heltalsmetoden. Det hade då visat sig att det extra mandatet hade tillfallit moderaterna.

Men blockbildning är givetvis inte förbehållet högeralliansen. Om S+V+MP hade kontrat med att bilda ett rödgrönt block, skulle de ha fått tillbaka sitt förlorade mandat:



Parti / Block Röster Mandat (16975)
Alliansen 2 936 790 173
De Rödgröna 2 598 985 153
SD 339 610 20
PP 38 491 2
FI 24 139 1

Man kan fortsätta att experimentera med att ta med FI i den rödgröna alliansen osv, även om det förstås känns lite inaktuellt att titta på valresultatet 2010. Så för att anknyta till något mer aktuellt, låt oss titta på hur riksdagsplatserna hade fördelats (med heltalsmetoden och block) om valresultatet från EU-valet hade varit ett riksdagsval:



Parti / Block Röster Mandat (10532)
Alliansen 1 337 677 127
De Rödgröna 1 705 937 161
FI 204 005 19
SD 359 248 34
PP 82 763 7
JL 11 629 1

De rödgröna tillsammans med FI hade haft 180 mandat, och majoritet. Hade man inkluderat FI i det rödgröna blocket skulle det i stället fått 181 mandat, och alliansen bara 126 (priset hade ökat till 10552 röster per plats)!

Jag hoppas att detta visar att heltalsmetoden med valtekniska block ger ett lättförståeligt, i grunden proportionerligt system, där avrundningsreglerna (marginellt) favoriserar stora partier och partiallianser på bekostnad av små och splittrade partier. Precis de egenskaper ett schysst system ska ha!


Friday, March 14, 2014

Day $\pi$ wish I happy everybody!

By what factor can you guarantee to increase your bankroll at a roulette table, if somehow you get the information that in the next $2n$ rounds, each of the colors red and black will occur exactly $n$ times?

Clearly you can double your bankroll by watching and waiting until the last of those $2n$ rounds, and betting what you have on the color that has come up only $n-1$ times. But you can do better. If $n=2$, you can increase your bankroll by a factor $8/3$: You don't bet anything in the first round. In the second round, you cleverly bet one third of your bankroll on the color that didn't come up in the first round. If you win, you now have $4/3$ of your initial bankroll, and after passing in the third round, you double up in the fourth. If on the other hand you lose in the second round, you still have $2/3$ of your initial bankroll, and since you now know the color of the next two numbers, you can double your remaining money twice, again ending up with $8/3$ times your initial bankroll.

If $n=3$, you can gain a factor $16/5$, and in general the answer is
\[ \frac21\cdot \frac43\cdot \frac65 \cdots \frac{2n}{2n-1}.\]
The factor you gain is actually the reciprocal of the a priori probability that $2n$ rounds of a roulette wheel without zeros would give $n$ red and $n$ black numbers. For an explanation and a description of the strategy, I recommend the lovely paper Games People Don't Play by Peter Winkler.

The reason I bring this up today, March 14, is that for large $n$, the factor you gain is asymptotically \[\sqrt{\pi\cdot n}.\]
The explanation has to do with the Wallis product formula for $\pi$, discovered around 1655 by John Wallis, and it is a fundamental way in which the number $\pi$ enters probability theory and combinatorics.

Wallis formula is usually written
\[\frac21\cdot \frac23\cdot\frac43\cdot\frac45\cdot\frac65\cdot\frac67\cdots = \frac{\pi}2.\]
If we truncate the product on the left just after the factor $\frac{2n}{2n-1}$, the even numbers $2,4,\dots,2n-2$ will occur twice in the numerator, and $2n$ will occur once, while the odd numbers $3,5,\dots,2n-1$ occur twice in the denominator. Taking square roots, we get
\[\frac{2\cdot 4 \cdot 6\cdots \sqrt{2n}}{3\cdot5\cdot 7 \cdots (2n-1)} \approx \sqrt{\frac{\pi}2},\]
and multiplying both sides by $\sqrt{2n}$, we obtain the asymptotical gain at the roulette table:
\[ \frac21\cdot \frac43\cdot \frac65 \cdots \frac{2n}{2n-1} \approx \sqrt{\pi \cdot n}.\]

It has been said that the Wallis product is a lousy way of computing $\pi$, but this is getting things backward. Yes, Ludolph van Ceulen had already calculated 35 decimals of $\pi$ using the method of Archimedes, and Wallis' formula added nothing in terms of such computations. But you don't use the Wallis product to approximate $\pi$, you use $\pi$ to approximate the Wallis product. And Wallis' product doesn't just occur in roulette games. It describes the asymptotics of the central binomial coefficient, which in turn determines the famous factor $\sqrt{2\pi}$ in the formula for the normal distribution and in Stirling's approximation of $n!$. Not to mention the Gamma function and the volume of the $n$-dimensional sphere.

Ten years ago, in 2004, while trying to come up with a good problem for the Swedish mathematical "olympiad", I happened to discover a proof of Wallis' product formula involving no calculus, just plain algebra and geometry. I thought I must have rediscovered something that was known since long ago, but after failing to find it in the literature, I wrote it down and submitted it to the American Mathematical Monthly. A few years later I was happy to hear from Donald Knuth who was preparing a lecture about my proof. And here is a video of his talk. Happy pi-day everyone!

)



Monday, February 17, 2014

No, $1+2+3+\dots$ isn't equal to $-1/12$. But $1+2+4+8+\dots = -1$.



A while ago the numberphile team released a video (apparently viewed more than 1.5 million times in one month), purporting to give a simple argument for the bizarre equation \[1+2+3+\dots = -1/12.\]

Obviously something fishy is going on here, because an infinite sum of larger and larger positive terms can't really have a finite value, let alone negative. Still, Tony Padilla and Ed Copeland claim in the video that the equation makes sense and is important for string theory in 26-dimensional space and what not.

In the discussions on the web, the video has been more or less burned at the stake. Mathematicians have criticized it for being misleading and for failing to properly discuss the concept of sum of a divergent series. Several commenters have dismissed it on the grounds that the whole thing is obviously nonsense. Among the critics are Blake Stacey and Evelyn Lamb. Quoting the blogger Skulls in the stars,

"a depressingly large portion of the population automatically assumes that mathematics is some nonintuitive, bizarre wizardry that only the super-intelligent can possibly fathom. Showing such a crazy result without qualification only reinforces that view, and in my opinion does a disservice to mathematics."

To some extent I agree with this. But if the wizardry is something a school kid can try and show to their friends, it might do a great service to mathematics even if it seems crazy and nonintuitive. The real problem with the video is

If kids try this at home, it won't work.

And this goes for kids of all ages and levels of education. Including myself. I know that $\zeta(-1)=-1/12$ but I still can't make sense of the derivation in the video.

So let's debunk it. Suppose \[1+2+3+4+\dots = S.\] Then, using the same type of calculation as in the video, we can shift the series by adding one or more zeros in front: \[S = 0+1+2+3+\dots = 0+0+1+2+3+\dots.\]
Now let's take the original series, subtract two copies of it shifted one step, and then add a copy shifted two steps:
\[
\begin{eqnarray}
S =& 1+2+3+4+5+\dots \\
-S =& 0-1-2-3-4-\dots\\
-S =& 0-1-2-3-4-\dots\\
+S =& 0+0+1+2+3+\dots
\end{eqnarray}
\]
Adding up columnwise, we get
\[ 0 = 1+0+0+0+\dots = 1.\]

That's not just weird, that's a contradiction. So the series can't sum to $-1/12$ or to any other number.

My main misgiving about contradictions isn't that they are wrong or anything. It's that they are boring. If somebody plays around on their own with this and similar series, perhaps trying to sum all even or all odd numbers, or all squares, they will just end up with a mess. If they ask about it in school, all the poor teacher can say is "you can't manipulate infinite sums the way you do with finite sums because you run into contradictions". And the gap between school mathematics and where the fun is will just appear larger.

But the thing is you can manipulate infinite sums, even divergent ones, in a lot of fun ways without running into contradictions. It's just that zeta regularization and Ramanujan summation is a bad first example. (For those who want to learn about that stuff, I recommend the excellent Wikipedia article 1+2+3+4+…).

So here's what I suggest instead:

Listen to the teacher's warning, and obey the following simple rules: (1) When you play with an infinite series, you can apply all the ordinary rules of arithmetic, as long as you only mess with a finite number of terms. (2) You can add (or subtract) two infinite series term by term. You may also multiply all the terms of a series by a fixed number, and the sum will be multiplied by the same number. And keep in mind that not all series have sums. By the way, rule (1) is called stability in the theory of divergent series.

With these rules, it is easy to sum a geometric series. For example, let $A=1+1/2+1/4+1/8+\dots$. Then
\[
\begin{eqnarray}
2A =& 2+1+1/2+1/4+1/8+\dots \\
-A =& 0-1-1/2-1/4-1/8-\dots\\
\end{eqnarray}
\]
Adding up, we get
\[ A = 2.\]
Amazing, and a little weird if you haven't seen it before. Now lets sum the powers of 2. Yes, positive powers. Let $B=1+2+4+8+16+\dots$. With the same trick,
\[
\begin{eqnarray}
2B =& 0+2+4+8+16+\dots \\
-B =& -1-2-4-8-16-\dots\\
\end{eqnarray}
\]
And adding up, $B = -1$.

How weird, the sum of a series of larger and larger positive numbers is negative! Well, strictly speaking we have only demonstrated that if the series can be assigned a value, that value has to be $-1$. But in fact assigning it this value is consistent with the rules I gave you.

I will not try to defend the pedagogical merits of summing divergent series. But at least it might serve to start a discussion of why it is okay to say that $A=2$, and whether it could somehow make sense that $B=-1$.

And what about the derivation in the video? First, Grandi's series (called $S_1$ in the video) must have the value $1/2$, because
\[
\begin{eqnarray}
S_1 =& 1-1+1-1+\dots \\
S_1 =& 0+1-1+1-\dots\\
\end{eqnarray}
\]
So $2S_1 = 1$.

Then let $S_2 = 1-2+3-4+\dots$, and just as in the video,
\[
\begin{eqnarray}
S_2 =& 1-2+3-4+5-\dots \\
S_2 =& 0+1-2+3-4+\dots\\
\end{eqnarray}
\]
So $2S_2 = S_1 = 1/2$, and therefore $S_2 = 1/4$. So far so good. Then they let $S=1+2+3+4+\dots$, and compute $S-S_2$:
\[
\begin{eqnarray}
S =& 1+2+3+4+5+6+\dots \\
-S_2 =& -1+2-3+4-5+6-\dots\\
\end{eqnarray}
\]
So $S-S_2 = 0+4+0+8+0+12+\dots$. But this is NOT the same thing as $4S$ (as is claimed in the video). To get from $0+4+0+8+0+12+\dots$ to $4+8+12+\dots$, you would have to delete an infinite number of zeros, and there is no rule that allows you to do that. That's where they go wrong. Up to that point, what they did was actually consistent.

I haven't mentioned Cesàro summation or Abel summation, and I haven't discussed the theory of stable, regular and linear summation methods. The point is that while equations like $1+2+4+8+\dots = -1$ may be bizarre and unintuitive, at least they are bizarre and unintuitive in a consistent way, and that gives a hint that there is something real going on behind the scenes. You don't have to sit passively and watch somebody pull rabbits out of a hat, you can actually try it yourself.

Which brings us finally to a little exercise. The Fibonacci numbers start 1, 1, and after that, each number in the sequence is the sum of the two previous numbers. So it goes $1,1,2,3,5,8,13,\dots$. Now compute
\[ F = 1+1+2+3+5+8+13+\dots!\]