« juli 2005 | Main | september 2005 »

augusti 30, 2005

Nu även med Skype

Till dem det berör:

Häromdagen inköpte jag en mikrofon för att kunna leka med Google Talk, och nu är jag även med Skype.

Kontaktinformation:
Skypenamn: hakankj
Google Talk: hakank@gmail.com

Så nu vet ni det.

(Hopplöst ute att starta med vissa saker, men inte full så hopplöst ute med andra...)


Uppdatering
Av lite olika skäl handlar kommentarerna i denna blogganteckning om John Ioannidis forskning kring vetenskapliga studier Why Most Published Research Findings Are False.

Posted by hakank at 07:13 EM Posted to Diverse | Comments (4)

augusti 29, 2005

Påminnelse: Septembers skånska bloggträff 4:e september

Åsa på Åsas anteckningar håller i september månads skånska bloggträff. Det blir på restaurang Ankara i Malmö, nästa söndag (4 september) klockan 13:00. Hon beskriver partikulärerna här och vill att du meddelar henne om du är intresserad av att komma.

Rapport från den förra träffen finns att läsa i Sammanfattning Skånska bloggareträffen 14 augusti 2005 (Malmö).


(Uppdatering: Tack David för korrigeringen av datum.)

Posted by hakank at 07:55 EM Posted to Blogging | Comments (1)

Kortsamlarproblemet (coupon collector problem) i mindre och isolerade nätverk med fullständigt utbyte av kort

Introduktion

När jag var liten samlade jag en hel del på samlarkort, t.ex. flaggor, ishockey-/fotbollsspelare etc. Det var alltså sådana kort där man köpte osett, ett eller flera kort i en påse (med eventuellt medföljande tuggummi eller annat godis) och sedan antingen köpte man nya eller bytte man till sig de kort man inte hade. Den stora poängen var naturligtvis att få hela serien komplett. (Det fanns säkert en fin social poäng i att träffas och byta sådana kort, men sådana finesser uppfattade man nog inte i denna ålder, typ kring 10+ år.)

Speciellt för flaggorna kommer jag ihåg att det fanns vissa kort som var väldigt svåra att få tag på (var det Mexiko med nummer 104, eller kanske var det Kenya?). Om jag nu kommer ihåg detta korrekt var det några få lyckostar som fått detta kort och vi andra dräglade djupt över dessa rara kort.


Kortsamlarproblemet (coupon collector problem)
Det finns ett klassiskt problem inom statistiken/sannolikhetsläran som handlar om detta: kortsamlarproblemet (coupon collector problem, dvs kupongsamlarproblemet) där man studerar hur många kort man behöver köpa i genomsnitt (eller för en viss säkerhetsgrad) på att få samtliga kort i en sådan samlarserie. Det visar sig att det är ointuitivt många: För att få tag i samtliga kort i en serie av 100 kort behöver man i medeltal köpa 519 kort. (Enkel formel för detta : 100*sum(1/(1:100)) ~ 519, där 100 i formeln är just antal unika kort i samlarserien.)

Men detta antal fluktuerar naturligtvis: för att vara säker till 95% att få tag i samtliga kort krävs 791 inköpta kort. Se även min Simuleringssida för lite mer om detta; sök på "samlarkortproblemet ".

Man kan notera att ovanstående beräkningar endast gäller för en person som ensam inhandlar kort. Om man tillåter byte av kort är det en annan sak, och det är precis det som det följande kommer att handla om.


Samlarkortproblemet i ett isolerat nätverk med fullständigt utbyte
För ett tag sedan hade jag en diskussion med en kompis om detta. Denne - som vi kan kalla för E - hävdade att företagen troligen inte tillverkar lika många av varje kort, just för att få oss att köpa fler kort för att få tag i samtliga.

Denna konspirationsteori är möjligen korrekt, men jag började undra om denna effekt kunde uppstå även om företaget tillverkade lika många exemplar av alla kort, och att det vi råkat ut för var en "klustereffekt", dvs att de kort som vi i vårt lilla nätverk var en slumpmässigt urval med de traditionella egenskaperna hos sådana urval.

E antog att företagen som skapar korten alltså tillverkar vissa kort i färre upplagor, säg att de färsta (sic!) är en tiondel av de som tillverkas mest. Min utgångspunkt var att denna effekt skulle kunna vara subjektiv enligt "regeln" att om man slumpmässigt drar ett antal olikfärgade kulor från en påse med lika fördelning så är det mycket stor sannolikhet att något antal är färre än de övriga och att det finns en färg som dras fler gånger.

Detta är något man kan testa med en simulering. Vilket har gjorts.


Sammanfattning
Som vi kommer att se uppstår faktiskt denna typ av effekt (E-effekt) om det totalt köps in ett mindre antal samlarkort. För 700 inköpta kort blir förhållandet mellan minst antal kort och flest antal kort rätt exakt 1/10.

Här nedan kommer även andra saker att visas, t.ex. denna effekt hos Lotto-dragna nummer, där samma förhållande är 1/2, vilket även uppstår i en simulering. Kanske inte remarkabelt men intressant.


Lokalt nätverk med fullständigt utbyte av samlarkort
Först en sak om nätverket. Den modell som vi här arbetar med innebär att det finns en mindre grupp, säg ett 10-tal personer, som har fritt utbyte av samlarkort inom gruppen men inte har något som helst kort-utbyte med några externa personer eller andra nätverk. Denna fullständiga isolering av inköpen gör modellen enkel att simulera.

(Man skulle även kunna studera komplexa nätverks-effekter kring detta, dvs att någon i Husieskolans krets känner någon i Stockholm och byter till sig de i Husie-kretsens ovanliga kort. Ju fler sådana svaga länkar mellan olika (inte helt isolerade) nätverk det finns, desto större blir naturligtvis den totala kretsen vilket leder till att denna lokala nätverkseffekt vi talar om här blir mindre.)


Modell och simulering
Tänk nu följande som översättning av samlarkortproblemet i ett lokalt nätverk till slumpmässig dragning av heltal i ett intervall.

En grundläggande förutsättning är att det faktiskt skapas exakt lika många kort, och att man globalt har lika stor chans att köpa alla kort, men vi studerar endast en mindre krets (nätverk) av personer som får tillgång till ett urval av dessa, t.ex. där tobakaffärens och den där kioskens urval.

Låt oss för enkelhetens skull anta att samlarkortserien har 100 olika kort. Dessa 100 olika korten motsvaras i simuleringen då av de första 100 positiva heltalen (1..100 alltså). Ett inköp av ett kort motsvarar att man slumpmässigt drar ett tal inom detta intervall, där alla tal har lika stor chans att dras. Detta görs s.a.s. med återläggning, så att ett tal har möjlighet att dragas igen.

Man drar slumpmässigt n stycken sådana tal, vilket alltså motsvarar inköp av n stycken samlarkort.

Efter det beslutade antalet "kort" (tal) är dragna, kontrolleras fördelningen bland dessa kort. Här jämför man antalet kort som kommit upp med minst antal och de som kommit med flest antal. Om ss är listan över de dragna talens fördelning är det sökta värdet alltså: min(ss)/max(ss), det som nedan kallas för min/max-förhållandet.

Vi behöver inte förutsätta något om hur stor gruppen är eller hur många kort en specifik deltagare införskaffar. Vi kommer senare se hur många fullständiga serier ett visst antal inköpta kort tenderar att generera, och man kan alltså anpassa antalet kort som (i medeltal) behöver köpas in för att få fullständiga serier.


Frågeställningen och hypotesen
Låt oss alltså se hur fördelningen mellan minimi-antalet kort och maximi-antalet kort utvecklas med det totala antal kort som inköpes.

Frågeställningen: Vad är förhållandet mellan min/max om det totalt köps in num.bought stycken kort av num.cards möjliga?

Hypotes: Om man slumpmässigt kommer fram till sådana min/max-förhållande på säg 1/10 eller något liknande har vi inget statistiskt stöd för E:s konspirationsteori.

Här följer R-koden som använts för simuleringen, som helt enkelt drar num.bought stycken tal ur intervallet 1..num.cards och returnerar fördelningen av de dragna talen (dvs hur många 1:or som dragits, hur många 2:or etc). Man kan här också notera hur enkelt denna simulering är. Det beror på att vi gjort det enkelt för oss och förutsatt att det fullständigt och fritt utbyte i detta isolerade nätverk.


collector.group.sim <- function(num.cards=100, num.bought=10000) {
ss <- rep(0,num.cards);
for (i in 1:num.bought) {
s <- sample(1:num.cards,1);
ss[s] <- ss[s] + 1;
}
ss
}


Exempel:
Om vi nu antar att det är 100 olika kort och 10 personer som samlar, samt att dessa vardera köper respektive 200 kort, inalles 10*200 = 2000 kort. En sådan simulering ser ut så här (sorterad lista eftersom vi inte behöver bry oss om de specifika talen/korten som dragits):


> ss<-collector.group.sim(100, 10*200);sort(ss);min(ss);max(ss);min(ss)/max(ss)
[1] 10 11 12 12 12 13 14 14 14 15 15 15 16 16 16 16 16 16 17 17 17 17 17 17 17
[26] 17 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20
[51] 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 22 22 22 22
[76] 22 22 23 23 23 23 24 24 25 25 25 25 25 25 26 26 26 27 27 27 27 28 28 33 33
[1] 10
[1] 33
[1] 0.3030303
> 10*200
[1] 2000

Här kan vi alltså se att det minsta antalet dragna tal/kort är 10, dvs min(ss), och max är 33. Förhållandet mellan dessa min(ss)/max(ss) är 10/33 ~ 0.3. Redan enna enkla simulering (detta nätverk) ger en känsla av att vissa kort är ovanligare än varandra, och förhållandet mellan de ovanligaste och de vanligaste är 10 på 33.

Personligen tycker jag detta är emot intuitionen: efter en slumpmässig dragning har vi ett min/max-förhållande på så stort som 0.3.


Om vi istället säger att man tillsammans endast köper 519 kort (dvs så många som det i genomsnitt krävs för att en person ska få en komplett serie) får vi några intressanta resultat. Notera att även här är det endast en enda körning, för att få en känsla för datan.


> ss<-collector.group.sim(100, 519);sort(ss);min(ss);max(ss);min(ss)/max(ss)
[1] 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4
[26] 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5
[51] 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6
[76] 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 9 9 10 10 11 12 13
[1] 1
[1] 13
[1] 0.07692308

Här kan till exempel följande noteras:

* min/max-förhållandet är värre än E:s föreslags 1/10, nämligen 1/13 (0.077)

* det minsta talet är 1 vilket innebär att det finns kort för en fullständig serie. (Fullständiga serier kommer att studeras mer här nedan.)


Vi gör nu en mer statistisk korrekt simulering med 100 sådana här simuleringar och tar medelvärdet för min/max-förhållandet:

> mean(replicate(1000,{ss<-collector.group.sim(100, 519);min(ss)/max(ss)}))
[1] 0.05141527

min/max-talet 0.05 (~ 1/20) stödjer ovanstående känsla att det är värre min/max-förhålllande än E:s 1/10.

Men det är kanske inte så realistiskt att en grupp tillsammans köper endast 519 kort? Låt oss nu titta på hur min/max-förhållandet påverkas av antalet inköpta kort.


Tabell över (medelvärde) av min/max-förhållandet för olika antal kortinköp
Om vi nu studerar medelvärdet av min/max för olika antal kortinköp får man följande tabell.

Från 100 inköp till 3000

> sapply(1:30, function(n) rbind(n*100, mean(replicate(100,{ss<-collector.group.sim(100, n*100);min(ss)/max(ss)})) ))
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 100 200 300 400.00000000 500.00000000 600.00000000 700.0000000
[2,] 0 0 0 0.01154701 0.04447036 0.07848971 0.1029102

[,8] [,9] [,10] [,11] [,12]
[1,] 800.0000000 900.0000000 1000.0000000 1100.0000000 1200.0000000
[2,] 0.1298539 0.1475774 0.1695608 0.1864951 0.1996583

[,13] [,14] [,15] [,16] [,17]
[1,] 1300.0000000 1400.0000000 1500.0000000 1600.0000000 1700.0000000
[2,] 0.2132364 0.2434604 0.2501553 0.2677531 0.2798811

[,18] [,19] [,20] [,21] [,22]
[1,] 1800.0000000 1900.0000000 2000.0000000 2100.0000000 2200.0000000
[2,] 0.2819174 0.2909844 0.3101849 0.3119899 0.3260513

[,23] [,24] [,25] [,26] [,27]
[1,] 2300.0000000 2400.0000000 2500.0000000 2600.0000000 2700.0000000
[2,] 0.3373065 0.3520848 0.3504074 0.3622678 0.3721507

[,28] [,29] [,30]
[1,] 2800.0000000 2900.0000000 3000.00000
[2,] 0.3841707 0.3844286 0.38901

Här kan man se att gränsen för 1/10 i förhållande mellan min och max är cirka 700 inköp. Detta motsvarar en liten grupp på 7 personer som köper vardera 100 kort, eller 4 personer som köper 175 kort osv. Jag tycker att det låter rätt lite, men å andra sidan var E:s 1/10 taget ur luften.

Om vi tar lite större steg: mellan 1000 till 30000 inköp:

> sapply(1:30, function(n) rbind(n*1000, mean(replicate(100,{ss<-collector.group.sim(100, n*1000);min(ss)/max(ss)})) ))
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1000.0000000 2000.0000000 3000.0000000 4000.0000000 5000.0000000 6000.0000000
[2,] 0.1684101 0.3033053 0.3869192 0.4466518 0.4883167 0.5158891
[,7] [,8] [,9] [,10] [,11] [,12]
[1,] 7000.0000000 8000.0000000 9000.0000000 10000.0000000 11000.0000000 12000.0000000
[2,] 0.5387887 0.5611546 0.5857873 0.6023973 0.6199602 0.6338816
[,13] [,14] [,15] [,16] [,17]
[1,] 13000.0000000 14000.0000000 15000.0000000 16000.000000 17000.0000000
[2,] 0.6371665 0.6508695 0.6613642 0.665185 0.6797338
[,18] [,19] [,20] [,21] [,22]
[1,] 18000.0000000 19000.0000000 20000.0000000 21000.0000000 22000.0000000
[2,] 0.6845181 0.6965812 0.6978221 0.7095483 0.7138271
[,23] [,24] [,25] [,26] [,27]
[1,] 23000.0000000 24000.0000000 25000.0000000 26000.000000 27000.0000000
[2,] 0.7187094 0.7274481 0.7267149 0.733775 0.7309658
[,28] [,29] [,30]
[1,] 28000.0000000 29000.0000000 30000.0000000
[2,] 0.7380007 0.7450008 0.7422353


Exempel: I vårt lilla samlarkortnätverk var vi väl 10 stycken och köpte kanske 150
kort per person, dvs total 10*150 = 1500 inhandlade kort. I tabellen ser man att
förhållandet mellan antalet färst kort och antalet flest kort är 0.25 (1/4), vilket
troligen skulle kunna uppfattas som den E-effekt vi talade om i början.

Ännu större inköp som tar riktigt lång tid att simulera: för 100000 inköpta kort blir medelvärdet av min/max cirka 0.85 (0.8506242). För en miljon inköp är det 0.9512054.

Vi ser alltså att min/max-förhållandet tenderar att utjämnas då antalet inköp ökar, vilket är vad man kan förvänta sig enligt de stora talens lag.


Fullständiga serier i nätverket
Ser man på minimivärderna för dessa får man antalet (genomsnittligt uppkomna) fullständiga serier i nätverket. Detta förutsätter alltså att alla i nätverket byter rakt av och inte är snikna eller har orealistiska byt-krav.


> sapply(1:30, function(n) rbind(n*1000, mean(replicate(100,{ss<-collector.group.sim(100, n*1000);min(ss)})) ))
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 1000.00 2000.00 3000.00 4000.00 5000.0 6000.0 7000.00 8000.00 9000.00
[2,] 3.08 9.71 17.08 24.98 33.2 41.2 49.87 59.03 66.67

[,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17]
[1,] 10000.00 11000.00 12000 13000.00 14000.00 15000.00 16000.00 17000.00
[2,] 76.01 84.79 94 102.37 111.52 120.41 128.45 138.62

[,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25]
[1,] 18000.00 19000.00 20000.00 21000.00 22000.0 23000.00 24000.00 25000.00
[2,] 147.44 156.05 165.46 173.09 184.5 192.92 202.72 212.33

[,26] [,27] [,28] [,29] [,30]
[1,] 26000.00 27000.00 28000.00 29000.00 30000.00
[2,] 220.74 229.74 238.11 248.47 257.23

Dvs om 3 (3.08 i tabellen ovan) personer tillsammans köper 1000 kort får de (i medelvärde) alla får en fullständig serie. På samma sätt om 9 (9.71) personer köper 2000 kort, 17 (17.08) köper 3000 kort så bör de i genomsnitt få fullständiga serier. Osv.

Fokuserar här in på 100 .. 3000 kortinköp:

> sapply(1:30, function(n) rbind(n*100, mean(replicate(100,{ss<-collector.group.sim(100, n*100);min(ss)})) ))
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,] 100 200 300 400.00 500.00 600.00 700.00 800.00 900.0 1000.00 1100.00
[2,] 0 0 0 0.13 0.57 1.05 1.48 1.97 2.5 3.17 3.69

[,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
[1,] 1200.00 1300.00 1400.00 1500.0 1600.0 1700.00 1800.0 1900 2000.00 2100.00
[2,] 4.44 4.99 5.63 6.1 7.3 7.97 8.3 9 9.91 10.41

[,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29] [,30]
[1,] 2200.00 2300.00 2400.00 2500.00 2600.00 2700.00 2800.00 2900.00 3000.00
[2,] 11.17 11.95 12.79 13.53 13.93 15.09 15.85 16.16 17.21

Här ser vi också en-person-problemet: för 600 inköp är det drygt en person som får en full serie, det "exakta" väntevärdet är alltså 519.


Några noteringar
Lite av det vi set ovan:

* Om det är få inköps (säg < 700) får man alltså den 1/10-effekt som både E och jag upplevde i våra respektive barndomar. Det behövs alltså inte någon konspirationsteori för att förklara detta. (Naturligtvis kan detta kombineras med att kort-företaget faktiskt gjorde denna 1/10-tillverkning, men dessa experiment stödjer alltså inte detta.)

* Nätverkets storlek, dvs antalet personer som ingår i det, är inte viktig i denna modell, utan det som är avgörande är hur många kort man tillsammans köper. Det kan vara en person som köper 10000 och de andra 100 stycken, och tillsammans har de alltså 10000+ 10*(N-1) kort vilka sedan kan bytas hur som helst.

Samt en sista notering:

För 519 inköp i ett utbytesnätverk blir det igenomsnitt så här många fullständiga serier:

> table(replicate(1000,{ss<-collector.group.sim(100, 519);min(ss)}))/1000

0 1 2
0.409 0.563 0.028

Vilket är intressant eftersom det i 2.8% av fallen faktiskt skapas 2 stycken fullständiga serier (trist nog befann man sig aldrig i dessa nätverk :). 519 inköpta kort är, som sagt, det magiska medeltalet för att en person skulle få en fullständig serie.


Jämförelse: min/max-analys av svenska Lottodragningar
Här görs en motsvarande min/max-analys av svenska Lottodragningar. I går inhämtades fördelningen av senaste halvårets lottodragningar. (Värdena hämtas från Svenska Spel: klicka på den gröna Lotto-bilden/knappen, och i den uppkomna popuppen klicka på den gröna "Statistik"-knappen.)

Fördelningen av de 35 Lotto-talen är att det minst dragna talet har endast dragits 22 gånger (faktiskt två tal), och det mest dragna talet har dragits 44 gånger. En sorterad fördelning av talen ser ut så här:

> lotto2<-read.table("svensk_lotto2.dat",head=T, sep=",")
> sort(lotto2$dragna)
[1] 22 22 23 24 27 28 28 29 30 30 30 31 31 31 31 32 32 32 32 33 34 35 35 35 35
[26] 36 37 37 38 38 39 40 40 43 44

> sum(lotto2$dragna)
[1] 1144

> min(lotto2$dragna);max(lotto2$dragna)
[1] 22
[1] 44

> min(lotto2$dragna)/max(lotto2$dragna)
[1] 0.5

Det ger alltså ett min/max-förhållande på 22/44 = 0.5. Är det något lurt här? Låt oss ser hur en simulering beter sig. Det är alltså totalt 1144 dragna tal de senaste halvåret och det finns 35 tal, vilket - för att prata i samlarkortproblemets terminologi - motsvarar 35 "kort" och 1144 "inköpta kort"

En exempelkörning:

> sort(ss<-collector.group.sim(35, 1144))
[1] 22 22 22 24 24 26 27 27 28 29 29 29 31 31 32 32 32 33 33 33 33 34 34 35 36
[26] 37 39 39 39 40 41 42 43 43 43

> min(ss)
[1] 22
> max(ss)
[1] 43
> min(ss)/max(ss)
[1] 0.5116279


Medelvärdet för 100 sådana min/max-simuleringar är cirka 0.47, vilket är tillräckligt nära Lotto:s min/max-värde på 0.5 för att vi ska känna oss trygga att Lotto-dragningar inte är påtagligt konstiga.


> mean(replicate(100, {ss<-collector.group.sim(35, 1144);min(ss)/max(ss)}))
[1] 0.466839


Slutkomihåg
I en samling slumpmässiga dragningar som Lotto eller samlarkort är det alltid någon eller några bollar/kort/tal som slumpmässigt dras fler gånger än de övriga, liksom det är alltid någon eller några som dras färre gånger än de övriga.

Man kan förledas att tro att det är något signifikant (speciellt, konstigt, magiskt) med dessa olika extremvärdena, speciellt om det är ett mindre antal dragningar som studerats. Sådana felslut kallas för "The extreme value fallacy" (se nedan).


Se även
Extremvärdesanalys av webbesök, speciellt länken till Number Watch: The extreme value fallacy.

Födelsedagsparadoxen/födelsedagsproblemet: Se t.ex. Sammanträffanden - anteckningar vid läsning av Diaconis och Mosteller 'Methods for Studying Coincidences' (teknisk, men länkar i slutet till andra sidor) samt .

Födelsedagsproblemet kan kanske ses som ett komplement till samlarkortproblemet: I födeledagsproblemet studerar man hur många personer det minst måste vara för att två (eller fler) ska ha samma födelsedag. I samlarkortproblemet är det frågan om hur många personer det måste vara för att alla dagar på ett år ska ha åtminstone en person som har födelsedag på denna person: Enligt det klassiska samlarkortproblemet (för en person som själv samlar kort) är det 365*sum(1/(1:365)) ~ 2365.

En Java-simulering: Coupon Collector Problem, från den trevliga sajten Probability by Surprise.

Posted by hakank at 07:27 EM Posted to Matematik | Sammanträffanden | Statistik/data-analys | Comments (2)

augusti 27, 2005

base_conv: Konvertering av ord till tal till ord

Som hjälp för Mats Anderssons födelsedagsgratulationshälsningshuvudbry samt ledtråd till en av gåtorna i Augusti-pyssel publiceras nu ett litet program: base_conv: Yet another word to number to word conversion.

Principen är enkel: Man utgår endera från ett "ord" eller från ett decimaltal varpå programmet konverterar till ett decimaltal respektive "ord" för så många baser som möjligt, från bas 2 till bas 68.


Exempel
T.ex. konverteras "ordet" blogg till decimaltalet 4640416 om blogg ses i bas 25. Bas 25 är för övrigt den minsta basen som kan representera detta "ord" eftersom "o" kräver åtminstone denna bas.

På samma sätt converteras "ordet" Håkan Kjellerstrand (utan mellanslag) i bas 68.till decimaltalet 661332330234565441547965347086985. Äsch, ni kan se hela listan här.


Språk, giltiga tecken
Det finns val för två olika språk med lite olika teckenuppsättning:
* engelska: 0..9 a-z A-Z
* svenska: 0..9 a-zåäö A-ZÅÄÖ

VI kan här se att både de små bokstäverna finns representerade och är väldigt olika. T.ex. "ordet" "åtgärdsförslag" (bas 45: 113728508327740105458241) är inte samma som "ÅTGÅRDSFÖRSLAG" som faktiskt inte ens går att representera i bas 45, eftersom "Ö" kräver bas 68, men det motsvarar decimaltalet 43778068670461409051480041 (sett i bas 68).


Ord, förresten
Konverteringen från decimaltal till "ord" skapar sällan ett "ord" utan är nästan alltid och för de högre baserna en blandning av siffror och bokstäver (förutom då man använder ett tal som konverterats från ett "ord", vill säga), och än mer sällan ett korrekt ord i respektive språk.


Mellanslag och andra lustiga tecken
Programmet tillåter alltså bara ovanstående tecken. Om andra tecken finns i ordet kommer ett felmeddelande. Mellanslag tas dock sonika bort.


En undring
Genom denna typ av konvertering kanske dubbeltydligheten i "tal" fått en praktisk mening. Möjligen kommer "riksdagstal" och 2672678331353573021 (bas 50) att användas omvartannat i framtiden?


Eventuell framtida utveckling
Jag har en liten idé om att göra någon form av "ordfaktorisering", med ungefär följande idéräcka:
* ett ord konverteras till decimaltal (för någon bas)
* decimalet faktoriseras
* faktorerna konvereras tillbaka till "ord" (i någon bas)
* om ett sådant "ord" finns i en ordlista ... vore det skoj.

Ta t.ex. "riksdagstal" (bas 50) = 2672678331353573021. Decimaltalets faktorer är:
174696276315679 samt 15299.

Visst skulle det vara lite skoj om "qqaicähbA" (bas 40 = 174696276315679) vore ett ord i svenskan. 15299 motsvarar en del kortare "ord": t.ex. "obo" (bas 25), "mgb" (bas 26), "kqh" (bas 27), "jeb" (bas 28).

Får se om det blir något med detta.


Programspråk
Programspråket som används för denna utilitet är Ruby (speciellt skoj när man vill rota i klasserna Integer och String.)

Posted by hakank at 10:32 FM Posted to Matematik | Program | Språk

augusti 26, 2005

Detta är en test på MT 3.2

Detta är alltså en test av uppgraderingen till Movable Type 3.2. Och det ser ut att funka.

Ursäkta att det en stund kom en liten loginruta under tiden. Det stod det inget om i skrifterna (eller så hittade jag det inte). Men en total ombyggnad av bloggen fixade det.

Funna lustigheter
* i adminlistan över kommentarerna så visas inte de allra senaste kommentarerna. Den senaste är från 2005.08.16, men det har kommit flera sedan dess (inte många, men några). De finns - tack och lov - på sajten. OK, något att hålla koll på. Därför kommer det att testläggas en kommentar på denna anteckning snart.

* Kommer jag ihåg fel, men har man inte skiftat plats på "Save" och "Preview" i "Create New Entry". Jag har för mig att Preview var till vänster, men nu är den till höger. Det kommer säkert att ställa till problem någon gång.


Uppdatering
* En riktigt trevlig sak är att det nu - om det funkar vill säga - finns möjlighet att moderera TrackBacks. Det har slagits på, men kommer att tas bort om det missbrukas av elakingar.

* Glömde ju att länka intern för att se om intern trackback funkar (som jag tror att den ska fungera), något jag efterlyste i Movable Type: automatisk intern TrackBack (framåtreferenser i efterhand).

* Previewn för kommentarerna är fortfarande konstig och formatterar inte korrekt.

* Som jag skrev i kommentarerna fungerar inte "Subscribe to this Comment" riktigt korrekt. Tar nog bort det vid tillfälle.

Posted by hakank at 09:14 EM Posted to Blogging | Comments (7)

augusti 25, 2005

Juyong Park, M. E. J. Newman:: A network-based ranking system for American college football

Juyong Park, M. E. J. Newman: A network-based ranking system for American college football (PDF)



American college football faces a conflict created by the desire to stage national championship games between the best teams of a season when there is no conventional playoff system to decide which those teams are. Instead, ranking of teams is based on their record of wins and losses during the season, but each team plays only a small fraction of eligible opponents, making the system underdetermined or contradictory or both. It is an interesting challenge to create a ranking system that at once is mathematically well-founded, gives results in general accord with received wisdom concerning the relative strengths of the teams, and is based upon intuitive principles, allowing it to be accepted readily by fans and experts alike. Here we introduce a one-parameter ranking method that satisfies all of these requirements and is based on a network representation of college football schedules.


En inte särskilt seriös jämförelse är Herbert Wilf Searching the web with eigenvectors (PDF) som använder rankning i en fotbollsturnering för att förklara googles metod att räkna ut PageRank. (Förgäves har jag försökt att få in detta trevliga paper i tidigare blogganteckningar. :)


Enligt Gustav Holmberg och andra har arxiv.org nu blivit med trackbacks. Får se om/hur det funkar.

Posted by hakank at 10:46 EM Posted to Social Network Analysis/Complex Networks | Comments (1)

Prenumeration på google-grupper och lite andra googlesaker

Något som (tydligen) inte så väldigt många känner till är att man numera har möjlighet att prenumerera (till ett mailkonto) på googlegrupper, t.ex. de kära usenetgrupperna, men även de nya specialvarianterna. Varje mail består av cirka 30 inlägg för en grupp, så för riktigt aktiva grupper kan det bli en himla massa mail.

Gå till groups.google.com och välj Nya användare: Delta (eng: New users: Join) och skapa ett konto. Via detta konto kan man sedan prenumerera. Nifty.


Mer saker från google: Google Alerts är en sökresultatbevakning där man förutom News och Web numera även kan sökordsbevaka grupper. (OBS. Denna tjänst ska inte förväxlas med en i för sig trevlig liknande tjänst Google Alert, men som i gratisversionen har en lite trist begränsning på max 150-sökträffar som man kan fördela lite hur man vill. Troligen har jag detta kvar endast av nostalgiskäl.)


F.ö. har jag under kvällningens gång pratat med två illustra svenska IT-personligheter via googles nya påhitt: Google Talk. Även det är riktigt trevligt. Roger på Prylfeber har skrivit om Google Talk lite mer.

Posted by hakank at 09:57 EM Posted to Sökmotorer

Talklockor: Något om primtal och sammansatta tal


[Not: Ett primtal är ett tal som endast går jämnt ut vid division med sig själv och 1. Alla andra tal är sammansatta. Både 0 och 1 är lite lustiga i sammanhanget: tekniskt sett uppfyller talet 1 villkoret för primtal, men av hävd anses det inte vara ett sådant. Så 2 är det första primtalet, sedan 3, 5, 7, 11 osv. 0 är ännu mer speciellt eftersom man inte får/kan dela med 0.]


Introduktion
Jag började nyss bläddra i boken Dr Riemann's Zeros som handlar om Riemannhypotesen, ett av de få kvarvarande klassiska matematiska problemen). Målgruppen för boken är icke-matematiker, och saker förklaras verkligen från grunden. T.ex. finns det appendix för ett flertal olika begrepp. Klart lovvärt.


Modeller för primtal och sammansatta tal
Ett av bokens sätt (modell) att beskriva primtalen och de sammansatta talen är att primtalen motsvarar atomer (är odelbara) medan de övriga talen - de sammansatta - motsvarar molekyler som byggs upp av primtalen.

Även om det egentligen inte är något fel på denna bild (förutom att atomer inte är odelbara) så är jag inte riktigt nöjd med den, främst eftersom det - enligt min mening - komplicerar bilden av talen, och gör det kanske svårare än vad det behöver vara. (Det är en annan sak att primtal/sammansatta tal även har denna atomära/sammansatta egenskap.)

Någon gång på 80-talet satt jag med en enkel miniräknare och anteckningsblock och funderade på denna typ av tal och hittade då en annan bild som jag tycker är naturligare för hur talen "fungerar". Till skillnad från atom/molekylmodellen såg jag inte primtalen som de primära utan de blev mer som en logisk (kon)sekvens av en annan egenskap (som förklaras nedan).

Jag ska här visa två metoder att se primtalen och de sammansatta talen som gör att det kanske inte blir så konstigt, utan att det faktiskt hänger ihop på ett trevligt sätt. Det som följer är i någon mening självklart för en matematisk insatt, och för inte matematiken framåt. T.ex. kan man med detta inte lösa Riemann-problemet eller faktorisera större primtal. Men eventuellt kan det avhjälpa vissa icke-matematikers rädslor för primtal och andra matematiska djur. (För säkerhets skull bör nämnas att jag inte är matematiker, men det var länge sedan jag förlorade min matematiska oskuld...)


"Talklockor"
Det sätt jag nu ibland ser talen är att de är uppbyggda av "klockor" som snurrar runt, runt med "ett tick per tal" (ett klockslag per tal). Det speciella med dessa klockor är att de alla har olika storlek, olika urtavlor. De första talen, från 0 till 5 har urtavlorna:

0: har urtavlan (0, dvs alltid 0)
1: har urtavlan (1, dvs alltid 1)
2: har urtavlan (0,1),
3: har urtavlan (0,1,2),
4: har urtavlan (0,1,2,3)
5: har urtavlan (0,1,2,3,4)
...

Generellt har talet n urtavlan (0,1,2,3,...n-2, n-1). Precis som för en vanlig klocka så börjar man om igen från 0 när det behövs, så att för 5-klockan gäller 4 + 1 = 0. 5-klockan skapar alltså av följande sekvens: 0,1,2,3,4,0,1,2,3,4,0,.....

(Både 0 och 1 är som ovan sagt lite konstiga varelser och är med för fullständighets skull både här och nedan.)


Modulo-operatorn
Det finns faktiskt något som ibland kallas för "klockmatematik" och som fungerar precis enligt denna princip: i stället för att fortsätta en sekvens i all oändlighet börjar man om från början när man kommer till urtavlans topp igen. Den matematiska operation kallas bl.a. för modulo-operation (förkortad mod här) och dess resultat är resten vid en division av ett tal med ett annat.

Exempel: mod(10,3) = 3 och 1 i rest. mod(10,5) = 0, eftersom 10 delat med 5 går jämnt ut (ingen rest).

Så här ser hela 10-klockan ut för modulo-operationen (för talen mindre än 10).

10 mod 1 = 0
10 mod 2 = 0
10 mod 3 = 1
10 mod 4 = 2
10 mod 5 = 0
10 mod 6 = 4
10 mod 7 = 3
10 mod 8 = 2
10 mod 9 = 1
10 mod 10 = 0

Not: För mod(m, n) och n > m så är resultatet m, t.ex. mod(10,21) är 10.

Ser man mod(10)-sekvensen, 0,0,1,2,0,4,3,2,1, verkar det inte vara så mycket till struktur i talen. (Det finns naturligtvis en struktur, men mer om detta en annan regnig dag. Här är dock en ledtråd: de sista 5 talen är alltid en fallande serie av tal, ... 4,3,2,1,0 . Talen som kommer före beter sig lite mer intrikat.)


Modulo-tabellen
Det blir mer överskådligt om man gör en tabell för modulo-operationen, med mod(radtal, kolumntal). Talet 0 innebär att det inte finns någon rest vid division, står det 1 innebär det att resten var 1 vid divisionen etc.

Exempel: mod(10,3) = 1. Här ser man 1 där 10-raden och 6-kolumnen korsas. Och mod(12, 6) = 0, som sig bör (eftersom 12 / 6 är 2 och ingen rest). De fetade raderna motsvarar primtalen, och som vi kommer till mycket snart.


___1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0
1: 0 1
2: 0 0 2
3: 0 1 0 3
4: 0 0 1 0 4
5: 0 1 2 1 0 5
6: 0 0 0 2 1 0 6
7: 0 1 1 3 2 1 0 7
8: 0 0 2 0 3 2 1 0 8
9: 0 1 0 1 4 3 2 1 0 9
10: 0 0 1 2 0 4 3 2 1 0 10
11: 0 1 2 3 1 5 4 3 2 1 0 11
12: 0 0 0 0 2 0 5 4 3 2 1 0 12
13: 0 1 1 1 3 1 6 5 4 3 2 1 0 13
14: 0 0 2 2 4 2 0 6 5 4 3 2 1 0 14
15: 0 1 0 3 0 3 1 7 6 5 4 3 2 1 0 15
16: 0 0 1 0 1 4 2 0 7 6 5 4 3 2 1 0 16
17: 0 1 2 1 2 5 3 1 8 7 6 5 4 3 2 1 0 17
18: 0 0 0 2 3 0 4 2 0 8 7 6 5 4 3 2 1 0 18
19: 0 1 1 3 4 1 5 3 1 9 8 7 6 5 4 3 2 1 0 19
20: 0 0 2 0 0 2 6 4 2 0 9 8 7 6 5 4 3 2 1 0 20

Kolumnerna är alltså klocksekvenserna: Kolumnen för 6 ger klocktalen för 6, dvs 0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,..: en evigt snurrande klocka.


Primtalen i en modulo-tabell
Nu kan vi äntligen börja prata om primtal.

Ett tal är ett primtal om talets rad "råkar" vara så beskaffad att alla klockorna (kolumner) är något annat än 0 för kolumnerna som motsvarar mindre tal än radtalet, förutom för 1-kolumnen och talets egen kolumn. Det sistnämnda är helt som det ska eftersom definitionen av ett primtal är att det endast är jämt delbart med sig själv och 1.

Sammanfattning: Ett tal är ett primtal då dess rad endast består endast av 0:or förutom för 1-kolumnen och talets egen kolumn (för kolumntal mindre än detta tal).

Ser man primtalen endast var för sig och utan sina sammasatta kompisar kan strukturen bli svår att överblicka. Ser man dem däremot inbakade på ovanstående sätt - i dessa eviga klockor som snurrar - känns det (tycker i alla fall jag) betydligt mer naturligt.


En annan klock-tabell: jämna divisioner
Här är en annan tabell som inte är lika naturlig, men som bygger på en liknande klock-princip. Här använder vi jämna divisioner enligt principen att om ett tal (raden) är jämt delbart med ett kolumntal skrivs resultatet av divisionen ut annars skrivs 0.

T.ex. division med 2 ger följande:

1 delat med 2 går inte jämt ut => 0
2 delat med 2 är 1 => 1
3 delat med 2 går inte jämt => 0
4 delat med 2 ger 2 => 2
5 delat med 2 går inte jämt => 0
6 delat med 2 ger 3 => 3
osv

Återigen ser vi en "klockeffekt" i kolumnerna:
För kolumnen 1 är det 1, 2, 3, 4, 5
För kolumnen 2 är det 0, 1, 0, 2, 0, 3
För 3 är det 0, 0, 1, 0, 0, 2, 0, 0, 3
...

Kolumnstrukturen för ett tal t: först kommer t-1 0:or sedan ett tal i konsekutivt i serien 1, 2, 3, sedan t-1 0:or, sedan nästa konsekutiva heltal etc.

Primtalen (återigen sett radvis) får vi då det endast finns 0:or på rad, förutom för kolumnerna 1 respektive t-kolumnen (dvs talets egen kolumn). Primtalen är de fetmarkerade i nedanstående tabell.


___1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2: 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3: 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4: 4 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5: 5 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6: 6 3 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7: 7 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8: 8 4 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9: 9 0 3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10: 10 5 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11: 11 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12: 12 6 4 3 0 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13: 13 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14: 14 7 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15: 15 0 5 0 3 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16: 16 8 0 4 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17: 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
18: 18 9 6 0 0 3 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
19: 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
20: 20 10 0 5 4 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
21: 21 0 7 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
22: 22 11 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
23: 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
24: 24 12 8 6 0 4 0 3 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
25: 25 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
26: 26 13 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
27: 27 0 9 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
28: 28 14 0 7 0 0 4 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
29: 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
30: 30 15 10 0 6 5 0 0 0 3 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Jag har för övrigt tidigare skrivit lite om diagonalerna i denna typ av tabell, se vidare
Diagonalserier.


Slutord
Återigen: Ovanstående är inget som helst matematiskt genombrott, men kanske kan det skapa något bättre förståelse kring talen.

Posted by hakank at 08:59 EM Posted to Matematik

augusti 22, 2005

IT Conversations: Stephen Wolfram

IT Conversations: Stephen Wolfram

For three centuries scientists have looked to mathematics to understand how nature works -- and to create the foundations for technology. But based on his surprising discoveries about simple computer programs, Wolfram, creator of Mathematica and author of A New Kind of Science, has developed a radically new approach. Stephen Wolfram not only addresses many fundamental questions about science and the universe, but also suggests major new directions for technology.
...

Se även
Stephen Wolfram
A New Kind of Science (Bokus, ISBN: 1579550088), som jag köpte för nästan exakt två år sedan, men har ännu inte läst hela
A New Kind of Science Online
Andra böcker av Wolfram (Bokus-länk)
Mathematica.


P.S. IT Conversations har ett gäng RSS-flöden.

Posted by hakank at 05:11 EM Posted to Komplexitet/emergens | Matematik | Systemutveckling | Comments (3)

augusti 21, 2005

Ännu mer om Persi Diaconis

"Ännu mer" i titeln hänvisar till tidigare skrivningar om Persi Diaconis. För övrigt verkar det som om det nu har länkats till lite fler av Diaconis papers på Publications.


Artikeln Maths isn't just for textbooks:

The progress of mathematics abounds in tall tales and unlikely stories. And they don't come much more improbable than this. Outside, the July sun of the Aegean is hammering down on a coastal hotel in Mykonos. Inside, America's most charismatic statistician addresses a gathering that can boast several of the world's top mathematicians as well as a motley assortment of science writers, novelists, historians and theatre people. And what is he doing? He's performing a card trick.

...

How does he do it [i.e. the card trick]? Diaconis quips that "magicians aren't allowed to explain their secrets and mathematicians can't explain their secrets". But he tries. The root of card-recognition tricks lies in the De Bruijn Sequences, a branch of what's called "combinatorics" - a discipline with a long history that stretches from the counting patterns used in Indian classical music to the coded instructions for robots used today. The mathematicians grasp the theory easily enough, but the mind-boggling mental speed of the practice still confounds them, and me.

Artikeln skriver sedan mer om hur det (roligt nog) blivit mer populärt med populärmatematik.


För övrigt 2: Di däringa De Bruijn-sekvenserna som nämns i citatet ovan kan man leka med här (som Java Applet).


(Nej, tyvärr har jag missat vartenda avsnitt av Numb3ers som nu tydligen går på svensk TV.)

Posted by hakank at 11:18 FM Posted to Matematik

ADIOS: System för att generera texter utifrån exempeltexter

Erik Starck skrev härförleden en kort notis Computers learn a new language om ADIOS, ett system som kunde skapa texter utifrån exempeltexter. Men han (och flera andra) länkade endast till New Scientist-notisen Computers learn a new language, som inte förklarar så mycket.

I Plus Magazine-artikeln Machine prose beskrivs däremot systemet mer:

Given a piece of text in any language, the program called ADIOS - automatic distillation of structure - searches for patterns and structures which it then generalises to produce new and meaningful sentences. The ADIOS algorithm is based on statistical and algebraic methods performed on one of the most basic and versatile objects of mathematics - the graph.
...


ADIOS-projektets sajt beskrivs systemet på följande sätt:


The ADIOS project addresses the problem, fundamental to linguistics, bioinformatics and certain other disciplines, of using corpora of raw symbolic sequential data to infer underlying rules that govern their production. Given a corpus of strings (such as text, transcribed speech, nucleotide base pairs, amino acid sequence data, musical notation, etc.), our unsupervised algorithm recursively distills from it hierarchically structured patterns. The ADIOS (Automatic DIstillation of Structure) algorithm relies on a statistical method for pattern extraction (The MEX algorithm) and on structured generalization, two processes that have been implicated in language acquisition. It has been evaluated on artificial context-free grammars with thousands of rules, on natural languages as diverse as English and Chinese, on coding regions in DNA sequences, and on protein data correlating sequence with function. This is the first time an unsupervised algorithm is shown capable of learning complex syntax, generating grammatical novel sentences, scoring well in standard language proficiency tests, and proving useful in other fields that call for structure discovery from raw data, such as bioinformatics.


Man kan även ladda ner en Lite-version (t.ex. en Linux-version som jag tyvärr inte fått att fungera). Mer akademisk litteratur finns här.

Det hänvisas även till en avhandling av Zach Solan. Det verkar vara den han beskriver som "The Syntax of Nature" - "The Nature of Syntax": a study of the hidden structures in human language and in other raw sequential data such as music, proteins, DNA and more..., vilket låter väldigt spännande men någon avhandling kan i alla fall inte jag se (han är väl inte klar ännu, stackarn).

Posted by hakank at 10:48 FM Posted to Språk | Comments (3)

Gruppteori: Konsten att fundera över hur många olika sätt man kan vända en madrass

Brian Hayes skriver i Group Theory in the Bedroom - An insomniac's guide to the curious mathematics of mattress flipping (PDF, som innehåller bilderna något mer lättåskådliga) en trevlig introducerande artikel till den matematiska disciplinen gruppteori (wikipedialänk).


En bok som täcker mer inom samma område (gruppteoretisk nöjesmatematik/nöjematematisk gruppteori) är David Joyner Adventures In Group Theory - Rubik's Cube, Merlin's Machine and Other Mathematical Toys (Bokus, ISBN: 0801869471). Ett tidigt utkast av boken finns via författarens Books-sida: SM485c lecture notes, Mathematics of the Rubik's cube (PDF).


För den som får en nyfilen eller blodad tand inom området rekommenderas det fria programpaketet GAP: GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra.

Posted by hakank at 09:51 FM Posted to Matematik

Spin (kortfilm)

Spin är en intressant kortfilm (8 minuter): "A mysterious DJ is sent to a city block to mend a series of chain reactions that occur in our every day life."

Jag vet inte mycket om filmen eller dess upphovsman. Den presenteras lite mer här (klicka på "Spin") och diskuteras här. Tydligen är det en teaser (eller tröst) inför väntan på filmen "11:59".


Posted by hakank at 08:59 FM Posted to Filmer | Comments (1)

augusti 16, 2005

Analogi mellan skrivandet av Harry Potter och utveckling av programspråk

Guido van Rossum, grundaren av det trevliga programspråket Python, gör en kort och kärnfull analogi mellan utveckling av programspråk och skrivandet av Harry Potter. (Egentligen gäller detta vilka bok-/film/TV-serier som helst, men Harry Potter är ett namn som slår just nu.)

Från The Harry Potter Theory of Programming Language Design

I'm sure that when J.K. Rowling wrote the first Harry Potter book (planning it as the first of a series of seven) she had developed a fairly good idea of what kind of things might eventually happen in the series, but she didn't have the complete plot lines for the remaining books worked out, nor did she have every detail decided of how magic works in her world. ... Just like the successive Harry Potter books are required to have "continuity" (we can't have Dumbledore's taste in sweets change drastically in book 3), successive versions of Python are constrained by pretty serious backwards compatibility requirements.

Sometimes it's easy to go back and generalize a feature; for example, the transformation of built-in conversion functions like int(), str() and list() into built-in classes feels like a stroke of genius (if I may say so myself :-). On the other hand, the recent discussion on python-dev of the exception hierarchy, summarized in PEP 348, shows that early choices sometimes are less than ideal, even if they're not fatally flawed. The mismatch of naming conventions and API quality in the standard library is another example.

Posted by hakank at 05:56 EM Posted to Systemutveckling

augusti 15, 2005

Sammanfattning Skånska bloggareträffen 14 augusti 2005 (Malmö)

Här är en sammanfattning av delar av det som behandlades på Skånsk bloggaremiddag 14 august 2005, 13.00, Kin Long, Malmö.


Deltagarna denna soliga sommardag var:

Erik Starck (Framtidstanken)
Håkan Kjellerstrand (hakank.blogg, tillika sammankallande)
Åsa (Åsas Anteckningar)


Åsa har redan hunnit kommentera spektaklet, vilken se. Här nedan kommenteras inte mer än om det finns något mer att säga eller kommentera.


Deltagarantalet var tre (3), och detta relativt låga antalet skyller vi väder, vind och semester (alternativt att semestern tog slut denna dag) på. Identiskt samma låga antal personer samlades även den 8 maj 2005.


Nästa träff är Åsa sammankallande för: Hennes förslag är 4:e september klockan 13.00. Se hit för mer information. Obs! Det är Åsa som äger denna information så gå till hennes blogg för att få alldeles rykande färsk information. (Jag kommer alltså inte uppdatera denna anteckning skulle det bli någon förändring. You have been warned.)


Sammanfattningen

- Se alltså Åsas lista och kommentarerna kring denna.


- Tiden från början till slut var 13.00 - 16.13 (eller så). Kort och intenstivt, alltså. Maten var god, som vanligt.

- Semestern tog slut för 2/3 av de deltagarna.

- Malmöfestivalen (onsdag/torsdag)
Det föreslogs också att vi skulle vi skulle försöka att träffas "inofficiellt" på Malmöfestivalen, dvs i nästa vecka. Typ kring onsdag eller torsdag. Vi håller kontakten kring detta.

- Åsa nämnde något om kreativa övningar i samband med Daniel Pinks bok "A Whole New Mind".

Det hela började så här: hakank frågade av någon anledning om Eriks då senaste blogganteckning som var en kontemplation om Wikis (speciellt susning.nu respektive den svenska wikipedia) tagit över de där fan-sidorna som fullkomligt svämmade över nätet i början.

Vilket ju är en intressant tanke. Det diskuterades även alternativa förklaringsmodeller, t.ex. att man numera skapar blogg, forum etc. Men något konsensus i frågan kom inte frams till.

Erik pratade sedan en stund varmt om boken, t.ex. att bokens tes om de viktiga framtida megatrenderna var samma som han själv vurmar för: globalisering, automatisering och individualiseringen. Hans orsaksbegrepp verkade dock något skevs eftersom Erik i sitt tema-val troligen var påverkad av Pinks tidigare böcker (bok?).

Det noterades också att den googlesökning som var grund för betraktelsen, nämligen att Framtidstanken var på 12:e (dvs rätt bra) googleträff, var utan fnuttar: "the pinks" (utan fnuttar). Sökräffen av "pinks" gällde inte alls populärkulturens "The Pinks" utan genitivformen av den ovan nämnda författares efternamn. Så kan det gå.

Erik nämnde då också att det fanns 7 (9?) mindre trender (minitrender?), t.ex. empati och kreativitet.

Och det var så vi kom fram till kreativiteten. En kreativ övning som fanns i denna bok gick ut på att man skulle skriva en historia på exakt (alternativt max) 50 ord. Andra kreativa begränsningsprojekt (creative constraints) nämndes då, t.ex. NaNoWriMo (National Novel Writing Month), där man ska skriva ett visst antal ord per dag, och som åtminstone Peter Lindberg och Mats Andersson påbörjade. En sökning visar att det var flera användare av det svenska språket som ägnade sig åt detta.

Erik kom därmed på att man borde ha en blogg med endast sådana där 50-ord-texterna. Varpå hakank avslöjade sin ett tag seriösa fundering att skapa en blogg som endast innehöll (nya) Shaggy Dog-historier (sök på "SHAGGY DOG OCH VITSAR"; detta är riktigt gamla saker. Vi pratar alltså tidigt 80-tal eller så.) Naturligtvis skulle samlingsstället hela Shaggy Blog.

hakank glömde i hastigheten bort att nämna den trevliga bloggen MadInkBeard i detta sammanhang, vilket nu åtgärdas. Bloggen behandlar ofta sådana creative constraints, såsom personerna i OuLiPo och andra så tankeväckande och galant utfört exellerar i.


- nyligen, intressant.se, den nya bloggportalen och andra samtlingstjänster för de svenska bloggarna.

Vad gäller bloggportalen framfördes några åsikter:
* att kunna se när senaste inlägget gjordes
* Det är ett lovvärt och rätt imponerande projekt, "men hur ska han hinna med allting"
* Det är tråkigt om de bloggar som inte uppdateras alls (one-night-stand-bloggar?) kommer att ligga där och skvalpa.

Vissa - visade det sig efter en rundfrågning - hade inte läst något av Sigge Eklund (dvs han som driver bloggportalen.se) tidigare, medan åtminstone en har påbörjat en sådan studie (varpå man förstod att det var till viss del inspirerat av dennes uppmärksamhet i både traditionell och hitills inte fullt så traditionell media).


- hakank visade förtjust sin apparat: en Texas Instrument TI-92 plus. Den presenteras som "grafisk miniräknare", men är snarare en ganska avancerad bordsmatematikmaskin. (Det motsvarar ungefär det där CAS - Computer Algrebra System - som han köpte 1990: Derive. Och något av en slump är det Derive som ligger bakom TI:s CAS-motor.) hakank är imponerad även om han har flera datorprogram (dvs på riktiga datorer) som är mycket mer avancerade. Tänk att kunna ligga i sängen och räkna! Han inser att det är hans version av en speldator.

Och så den obligatoriska kommentaren för att unvika framtida kommentarer: Ja, HP:s senare modell, hp 49g+, är säkert till viss del bättre rent funktionsmässigt än denna rätt gamla räknare från cirka 1999 (men denna är nu uppdaterad till motsvarande funktionsnivå som de nyare TI-89 Titanium respektive TI Voyage 200, dock fortfarande med något mindre Flash-minne). Den riktig stora fördelen - som hakank ser det - är att den har ett QWERTY-tangentbord och en stor skärmyta. Han är också fortfarande imponerad av att man kan göra rätt avancerade differentialekvationer inklusive en smidigt koppling till plottning av desamma.

[I går upptäckte han - alltså fortfarande hakank - att det även finns en LLL-funktion, t.ex. för att räkna "integer relations" (vad detta nu heter på modern svensk matematiska: heltalsrelationer?). En viss del av söndagkvällen gick åt att leka med detta och liknande program. Programmet kan f.ö. laddas ned här. Det saknas nu en implementation av PSLQ för TI:n. En sådan finns för den senaste HP:n. Hrmph...]


Som ett proof-of-concept användes naturligtvis denna fantastiska matematikmaskin för att räkna ut notan när det blev så dags.


Åsa kommenterade hos sig att det verkar vara en tradition att visa nya apparater på dessa de skånska bloggareträffarna. Det stämmer, även om traditionen nog är rätt ny. Förra gången var det Torgny som förevisade sin mobiltelefon för en förtjust(?) publik. Linnea bytte plats med Åsa för att kunna se apparaten bättre. Exakt vad som avhandlades då vet i alla fall inte jag, eftersom jag satt kvar på min plats, trots att Torgny ursprungligen satt bredvid mig. Ah, det klarnar. Ett visst nyligen till-viss-del-förbjudet behov orsakade Torgnys bytande av plats. Det var också någonstans i denna veva som de - Torgny och Linnea - började diskutera bl.a. politik med en icke-bloggare.


- Senaste nya svenska bloggarna: Som vanligt hade Åsa bra koll (fast hon inte riktigt vill erkänna det) på vad som händer ute bland de svenska bloggarna. Vi försökte komma på vilken som var den senaste svenska bloggen som vi började bevaka. [För min del var det nog Principia Mathematica.]

Men som sagt flera gånger tidigare: Det är svårt att hitta nya intressanta. Inte för att de inte finns utan för att det är så många nya.

Ett av problemen är att man blir mer kräsen av sig efter ett tag samt att det tar helt enkelt tid för en blogg att bli en favorit. Vi skisserade på en variant av ett tidigare bloggaremiddagsförslag genom att de politiska bloggarna borde ha ha sin politiska hemvist i bloggnamnet. Och det borde även de icke-fullt-så-politiska bloggarna också ha, liksom all annan information som gör att det klart framgår vilken typ av blogg respektive skribent det är. Ett absolut minimum borde vara information om det är en bra/intressant blogg eller inte.

Ett förslag till ett sådant bloggnamn: "hakank.blogg.officiellt.politisk.synnerligen.obunden...intressant.blogg.tycker.i.alla.fall.hans.föräldrar.och.några.få.av.hans.vänner".
Och här fick vi även med antalet läsare av bloggen, vilket alldeles osökt för oss till nästa punkt i dagordningen, nämligen:


- Det diskuterades hur många besökare man har och vad man kan göra med denna information. Kort kan sägas att ingendera har någon väldigt välbesökt blogg. Dock nämnde hakank att han de då gångna dygnet fått 21000 träffar, men det var stackars google-botten som sprang unt runt runt i detta ekorrhjul.


- En viss debatt utfördes om vad som egentligen menas med frågan (och dess svar): Kommer bloggarna påverka valet 2006 (eller påverka X överhuvudtaget)?

Ett problem är det inte bara är bloggen i sig som påverkar utan även bloggarens tidigare konktaktnät, influens och före bloggen uppsamlade förtroende: Om bloggaren X avslöjar något uppseendeväckande, Y, är det i egenskap av bloggare, sin roll som A (t.ex. kändis).

Självklart är bloggen till sin nätverkssamlande natur en utmärkt förstärkare och accelerator av spridningen av saker och ting (inom en viss krets), såsom nyheter, skvaller eller bloggnära riter.

Som vanligt blev det en del diskussion om förtroende som vissa bloggar(e) har respektive inte har, och hur man vinner respektive förlorar sådant förtroende. (Men det som sades var inte så mycket att skriva hem om, speciellt eftersom det som sades har sagts tidigare och det var inte speciellt mycket denna gång.)


- Som uppfyllande av en special request ska nu beskrivas hur man kontrollerar hur många som prenumererar på en bloggs RSS/Atom/etc-flöde via Bloglines. Låt oss ta Åsas blogg som exempel.

a) Gå till Bloglines

b) Leta reda på den blogg (dvs bloggens RSS-flöde) som sökningen avser.

Några alternativ hur detta kan göras kommer här nedan. Åtminstone de två första varianterna kan göras även om man inte har ett Bloglines-konto. (Ett sådant rekommenderas naturligtvis, tycker en Bloglinesberoende.)


b.1) genom att skriva bloggens namn i Search-fältet

Hmm, söker man på "åsas anteckningar" framkommer ett tomt sökresultat. Inte så bra, och det beror just i detta fall på att sökningen inte klarar av "å" (vilket är trist). Testade även med "håkan" och de resultat som kom var på "kan".

Välj "Preview" för att se hur bevakningssidan ("flödessidan"?) ser ut.

b.2) den alfabetiska listningen. I denna lista visas antalet prenumeranter till höger. Klicka på den rad som ser intressant ut.

b.3) Följande fungerar endast om man har ett konto.
+ Leta reda på RSS-flödet på bloggen. Det brukar finnas någon ikon med RSS/Atom eller något liknande, där man kopierar URL-en till detta.
+ Gå sedan till Bloglines-fliken "My feeds"
+ Klicka på "Add"
+ Klistra in den ovan kopierade URL-en i fältet "Blog or Feed URL"
+ Klicka på "Subscribe". Var lugn, man prenumererar inte ännu. Det är några steg dit.
+ Klicka på "Preview this feed"
+ Det kommer då upp en sida med själva flödet (eller snarare en fin presentation av detta).

b.3b) En variant som kan fungera är att i fältet "Blog or Feed URL" klistra in bloggens URL i stället för flödets URL. Bloglines brukar kunna lista ut de olika flöden som bloggen har. Klicka på "Preview" för det som ser mest intressant ut.

Idiotiskt nog (i alla fall för mig just nu) funkar inte denna metod om man redan prenumererar på något av bloggens RSS/Atom-flöde. Då kommer meddelandet You are already subscribed to that blog.


c) Så, alla dessa varianter är syftade att komma till den sida som visar informationen i RSS-flödet. T.ex. ett av Åsas flöden: här.

Denna sida visar längst upp (strax under sökfältet) antal prenumeranter. Om man nu klickar på denna länk (e.g. "25 subscribers") kommer man till en mer utförlig sida där det även visas vilka (publika) prenumeranter som prenumererar på detta flöde.

Ett trevligt tips är att nu klicka runt bland kontonamnen för att se vilka bloggar de i sin tur också prenumererar på.

Frågor?


- Lotto och andra dåliga former av spel.

Nej, hakank har inte kollat om hans förutsägelse till finska Lotto var korrekt.

Det berättades om några rätt stora (19000 respektive 9000 SEK) vinster på (Svenska) Lotto för ett antal år sedan, varvid någon ekononomisk medveten person frågade om hur mycket man skulle tjänat om man istället satt in motsvarande pengar på banken. Varpå följande blixtsnabba svar kom till sällskapets munterhet: Inga då heller.

- I samband med något nämnde vi bloggen (av några lundensare) Diagnos.


- De sedvanliga bashningarna av journalister-skriver-av-sig-"bloggar" gjordes.

Man nämde även den starka kommentaren om Linda Skugges kommande Sylvia Plath-biografi.


- Någonstans blev det också en diskussion om hur man ska skriva för att undvika självklara och onödiga kommentarer, t.ex. om man skriver om ett Windows/Linux-program så är det rätt stor chans/risk att någon kommenterar att Linux/Windows/Mac är bättre. Någon - bl.a. undertecknad - brys sig emellanåt för att försöka "hedga" sådana kommentarer. Förutom att de sällan tillför något nytt till en diskussion är de nästan alltid (se där en "hedgning") tråkiga att läsa och gör att eventuella huvuddiskussioner drunknar.


- Hur lång tid det tar att skriva blogganteckningar. Vissa typer av anteckningar tar ganska kort tid, säg 10-20 minuter, andra tar betydligt längre tid. Som exempel nämnes hakanks ovan nämnda anteckning om finska lottorader som påbörjades cirka 10.00 och var klar kring 16-snåret, utan avbrott för lunch eller så. (Tiden inkluderar tiden att söka reda på Lotto-rader, skriva programkod, buggrättning, nya finesser, ännu fler saker att testa, samt skrivande av blogganteckning. Samt visst te-drickande.)


- Fördelar/nackdelar med separata länk-/notisbloggar. Henrik Torstensson & Co.:s variant med "Dagens länkar" (exempel) nämndes som ett föredöme, och är troligen bättre än att ha en speciellt länkblogg. (Någon trodde att anteckningen var rubricerad med "Dagens länkar" eller något liknande men det är kanske hos någon annan?)


- Fascinationer över hur produktiva en del bloggare är. Det diskuterades även (det möjligen moraliska problemet) i att läsa men framförallt skriva bloggar på jobbet. Vad gäller läsandet skulle man kunna hävda att det ingår i en omvärldsbevakning.

Lyssnande på radio, var alla överens om, var en form av omvärldsbevakning som de flesta nog anser som moralisk försvarbar. Gäller detta månne även podcasting och annan form av modernt ljudstrålande?


- Fika och -diskussioner (riktiga, på jobb alltså, inte de vi har på bloggarna) togs upp. Det är bra med fikarast om de verkligen gör att man kopplar av, och inte störs t.ex. av (subjektivt ansett) inskränkta eller ointressanta diskussioner eller att det endast är jobb man pratar. (En annan sak är att det kan vara trevligt - tycker i alla fall vissa av de på bloggaremiddagen deltagande deltagarna - med ingående s.k. nörddiskussioner med likasinnade över en kopp te eller kaffe eller juice eller vatten och kanske en fralla.)


- Vi, noterades det i privat kammare efteråt, diskuterade inte vidare den svenska stats-telivisionens vara och/eller form. Nästa gång kanske?

- Hundar och hur man ska förhålla sig till en (till synes ilsken) hund som springer efter en när man cyklar. Troligen är det bästa att bara pinna på och hoppas att hunden tröttnar.

Det berättades i samband härmed också en sedärande historia från Ribersborg där det finns en hundrastplats strax innan man kommer till själva badplatsen. En hundägande person påpekade synbarligen irriterad för cyklister som cyklade på den av staden utfästade cykelbanan: "Ni borde inte cykla förbi hundrastplatsen."

Om denne person avsåg att man skulle leda cykeln i stället för att cykla eller att ta en annan väg än den av staden för länge sedan såväl planerade och implementerade cykelbanan är osäkert. Hur som helst kan detta alltså ses som en likt Akilles och sköldpaddan väluppfostrande historia i hur vi tenderar att uppleva världen utifrån våra egna intressen och värderingar. (Notera att ordet inskränkt nämndes först i denna parentes. Samt några punkter ovan, men då ej i samband med hundar, hundägare respektive cyklar och cykelägare.)

Posted by hakank at 10:17 EM Posted to Blogging | Comments (5)

augusti 14, 2005

Spelteoretisk analys av uppvaktning

New Scientist: 'Worthless' gifts get the good girls berättar om två brittiska forskare, Peter Sozou och Robert Seymour, som gjort en spelteoretisk modell kring uppvaktning.

Från New Scientiskt-artikeln:

Men who spend big money wining and dining their dates are not frittering away hard-earned cash. According to a pair of UK researchers, they are merely employing the best strategy for getting the girl without being taken for granted.

Using mathematical modelling, Peter Sozou and Robert Seymour at University College London, UK, found that wooing girls with costly, but essentially worthless gifts – such as theatre tickets or expensive dinners out – is a winning courtship strategy for both sexes.

So [Sozou] and Seymour built a model based on a series of dating decisions. In the model males had to decide what kind of gift to offer females – valuable, extravagant or cheap – based on how attractive he finds her. The females had to either accept or decline the gift and then decide whether to mate with the gift-giver – a decision also weighted on the 'attractiveness' of their prospective partner.

When they measured the different outcomes of all the steps, they found the best solution for the males was to give extravagant, but intrinsically value-free gifts the vast majority of the time, while giving gifts of material value very occasionally.

The model showed that if males gave valuable gifts too often, the females would start to exploit them: the males have no clue as to the females’ real intentions in the model. Put simply, the females just take the diamonds and run. But when the gifts are worthless, an uninterested female has little incentive to accept, gaining no return on what could be just turn into the simple waste of an evening. Only girls who are serious would bother to go the distance.

Naturligtvis har modellen inte fått stå oemotsagd:

Alison Lenton, a social psychologist at the University of Edinburgh, UK, questions some of the model’s assumptions, however. For example, one assumption is that females obtain a negative outcome for accepting an unattractive, though committed, male. Women have been shown to prioritise traits associated with good parental care above physical attractiveness, she says.


Matematikern Keith Devlin intervjuas i en NPR-intervju om detta: Using Math to Move a Courtship Forward. (Det kommer först några sekunders reklam innan programmet.)


Papret
Papret är alltså Peter D. Sozou, Robert M. Seymour: Costly but worthless gifts facilitate courtship.
Abstract:

What are the characteristics of a good courtship gift?We address this question by modelling courtship as a sequential game. This is structured as follows: the male offers a gift to a female; after observing the gift, the female decides whether or not to accept it; she then chooses whether or not to mate with the male. In one version of the game, based on human courtship, the female is uncertain about whether the male intends to stay or desert after mating. In a second version, there is no paternal care but the female is uncertain about the male’s quality. The two versions of the game are shown to be mathematically equivalent.We find robust equilibrium solutions in which mating is predominantly facilitated by an ‘extravagant’ gift which is costly to the male but intrinsically worthless to the female. By being costly to the male, the gift acts as a credible signal of his intentions or quality. At the same time, its lack of intrinsic value to the female serves to deter a ‘gold-digger’, who has no intention of mating with the male, from accepting the gift. In this way, an economically inefficient gift enables mutually suitable partners to be matched.

Det finns även appendix som mer förklarar modellen.


Not: Thomas på 1 är inte ett stort tal skrev om detta för ett tag sedan, i I brist på annat.


Mer om matematik och romantik
Om man vill vet lite mer om romantikens matematiska vedermödor är t.ex. J. C. Sprotts Dynamical Models of Happiness (PDF) ett bra ställe att börja läsa. Där beskrivs olika typer av personligheters dynamik med hjälp av differentialekvationer (och inte spelteori som Sozou och Seymours modell). Notera att papret är mer om dynamiska system än seriös romantisk forskning. Inspirationen kom från Steven Strogats lilla Love Affairs and Differential Equations (hittar den inte på nätet längre), och Strogatz skriver även om detta i sin bok Nonlinear Dynamics and Chaos. Eller söka på "differential equations" "romeo and juliet". Ett mer seriöst paper i samma anda är Sergio Rinaldi: Laura and Petrarch: An Intriguing Case of Cyclical Love Dynamics

I Devlins NPR-intervju nämns också Gottman, Murray et.al Mathematics Of Marriage (c.f. här, här och lite här.)

Se även Devlins populärmatematiska krönikor Devil's Angle).

Posted by hakank at 10:30 FM Posted to Spelteori och ekonomi | Comments (1)

augusti 06, 2005

Lite om konsekutiva talpar i Lotto (och dess varianter)

I Konstantinos Drakakis paper Distances between the winning numbers in Lottery (arXiv, PDF) undersöks sannolikheten för en förekomst av konsekutivt talpar i Lotto-spel. Man ger en formel för denna typ av sannolikhet, och kommer t.ex. fram till att det för ett 6/49-Lotto (dvs där 6 nummer dras av 49) är det ungefär 49.5% chans att en Lotto-rad innehåller åtminstone ett konsekutivt talpar. Vilket är förvånansvärt högt.

Här nedan är några kommentarer och utvikningar, bl.a. med hjälp av riktig data för den Lotto-form vi har i Sverige, 7/35-Lottoformen (dock ej svensk data) samt simulering av sådan Lotto-typ.


Not: Sorterad dragningslista
En not kan vara på sin plats så här i början. Det är frågan om (konsekutiva) talpar i den sorterade listan av de dragna Lotto-numren. Det gäller alltså inte talpar som uppstår i själva dragningen. Exempel: Om en dragning görs av följande "bollar" (1, 14, 34, 2, 19, 15, 20) så tittar vi här på den sorterade listan (1, 2, 14, 15, 19, 20, 34) som ha tre stycken konsekutiva talpar: (1,2), (14,15) samt (19,20).

Notera också att varken Drakakis eller jag här nedan har brytt oss om tilläggstal och andra finesser.


Matematisk formel
Problemet formuleras på följande sätt i papret:

What is the probability that, out of m > 0 numbers drawn uniformly randomly from the range 1,..., n > m, at least two are consecutive?

Dvs vad är sannolikheten att det finns minst ett konsekutivt talpar (dvs ett eller flera) om man drar m tal från intervallet 1..n.

Den slutna matematiska formeln för denna sannolikhet uträknades till

p(n,m) = 1 - p(n,m)= 1 - ( C(n-m+1, m) / C(n,m) )

där C motsvarar (binomialkoefficienten ("n över m") och som i sin tur är definierad som n!/(k!*(n-k)!). Papret visar med matematisk stringens hur man kommit fram till detta resultat, men det vågar jag inte ha någon åsikt om och kommer inte heller att beröra detta här nedan.


Konkret
Låt oss i stället bli konkreta. För den ovan nämnda Lotto-typen 6/49 studerade värdena (n=49, m=6) får man sannolikheten för att det ska finnas minst ett konsekutivt talpar om man drar 6 tal från intervallet 1..47.

I det symboliska matematisk paketet MuPad (fritt att ladda ner och fritt att använda) uttrycks det på följande sätt.

>> n:=49:m:=6:1- binomial(n-m+1,m) / binomial(n,m);float(%);

22483/45402

0.4951984494

dvs det är cirka 49.5% chans att det finns åtminstone ett talpar. Förvånande mycket, eller hur?


Simulering
Min vana trogen har jag även simulerat detta, och lika troget är det gjort i statistikpaketet R. I simuleringen gjordes 100000 "dragningar" - med sample(1:49, 6) - och sedan räknar man hur många tal som ligger intill varandra. (Som vanligt använder jag den kompakta one-liner-formen för denna typ av simuleringar. En liknande simulering har förklarats lite mer ingående här.)


> sum(sapply(1:100000, function(x) {ddd<-diff(xxx<-sort(sample(1:49,6)));sss<-sum(ddd==1);sum(sss>=1)})/100000)
[1] 0.49559

dvs 49.5%, vilket stämmer hyfsat bra med formeln.


Den svenska Lottoforme(l)n: 7/35
OK, denna typ av Lotto kanske inte är så intressant för oss. Vad med den svenska formen 7/35, dvs där man drar 7 nummer av 35? Först tar vi den teoretiska beräkningen (i MuPad):


>> n:=35:m:=7:1- binomial(n-m+1,m) / binomial(n,m);float(%);

8903/11594

0.7678971882

Dvs det är nästan 76.8% chans att det finns åtminstone ett konsekutivt talpar i de svenska lottoraderna. En simulering av 100000 dragningar ger (nästan) samma resultat 76.6%:

> sum(sapply(1:100000, function(x) {ddd<-diff(xxx<-sort(sample(1:35,7)));sss<-sum(ddd==1);sum(sss>=1)})/100000)
[1] 0.76618


Utvidningar av detta
Kommen så här långt funderade jag på några andra saker kring Lottodragningar:

- finns det data för den svenska Lotto-formen?
- hur många konsekutiva talpar finns det i genomsnitt?
- hur är fördelningen för andra typer av talpars-differenser?


Data för Lotto på formen 7/35 (dock ej svensk)
Det vore ju roligt att se hur 7/35 ser ut i praktiken. Finns det då någon lista över en massa dragningar på det detta "svenska" Lotto-format 7/35? Jepp, det finns det. Mattias Hästbacka har samlat resultaten av Lottoraderna på sin Lotto-sida. Den fullständiga listan finns på Lotto-rader från v40/1980 till v17/2005, dvs nästan 25 år.

Observera att detta inte är Svenska Spels Lottodragningar, utan motsvarande "Finska Spel". Men det spelar egentligen ingen roll för det jag vill komma åt.

Om någon har motsvarande dataanhopning för Svenska Spels Lotto så vore jag mycket intresserad av få tillgång till den. (Maila mig gärna i så fall på hakank@bonetmail.com".)

Jag har bearbetat datan och i filen lotto_all_just_numbers.txt finns "rena" rader utan någon annan information, förutom en tillbörlig källhänvisning till Mattias Hästbackas sajt.


Analys av data
OK, tillbaka till undersökningen. Det finns i Mattias Hästbackas datamängd 957 rader med åtminstone ett konsekutivt talpar av 1283 dragningar, vilket är 957/1283 = 0.746, dvs 74.6%.

Det teoretiska värdet är som vi såg ovan 76.8%, vilket skulle motsvara 1293 * 0.7678971882, dvs ungefär 985 rader. Skillnanden mellan det praktiska värdet (957) och det teoretiska (985) är 985 - 957 = 28, vilket är ett fel på 28/1283, dvs ungefär 2.2% , vilket väl får anses vara rätt hyfsat.


Hur många par blir det i genomsnitt?
Den andra frågan är något annorlunda än Drakakis ursprungliga. Hans utgångspunkt var hur stor sannolikheten är för att det ska bli ett eller flera konsekutiva talpar (dvs åtminstone ett) i en dragning. En annan fråga man kan ställa sig är: hur många konsekutiva talpar det i genomsnitt blir per dragning.

Här är den första dragningen som Mattias Hästbacka sparade (vecka 40 1980):

7, 8, 9, 16, 17, 18, 30

Det finns alltså fyra konsekutiva talpar (7,8), (8, 9), (16, 17) samt (17, 18). Så, frågan är då hur många sådana talpar det blir i genomsnitti per dragning.

En körning på Hästbackas data ger totalt 1429 konsekutiva talpar och på 1283 dragningar blir det 1429/1283 = 1.113796. Dvs för varje dragning blev det igenomsnitt 1.1 konsekutivt talbar.


Äpplen och päron
Men, kan man nu fråga sig, hur rimmar detta 1.2 talpar per dragning med att det finns 76.6% chans för att det blir åtminstone ett konsekutivt talpar per dragning? Borde sannolikheten inte bli 100% istället? Nej, det är två olika saker (olika äpplen och päron).

Konstantinos formel tar inte hänsyn hur många konsekutiva talpar det är utan endast om det är ett eller fler. Dvs det spelade ingen roll för honom om det är 1 sådant par eller 4. Denna senare uträkning tar däremot hänsyn till detta antal. Den andra skillnaden (päronet alltså) är att vi inte räknar med sannolikheter längre utan med det genomsnittliga antalet per dragning.


Fördelning av konsekutiva talpar
En fördelning av antalet konsekutiva talpar i Hästbacka-datan är

0: 325 (0.25)
1: 565 (0.44)
2: 318 (0.25)
3: 69 (0.05)
4: 4 (0.00)
5: 1 (0.00)

Dvs det finns 325 Lotto-rader utan något konsekutivt talpar (cirka 25% av alla dragningar), 565 rader med exakt 1 konsekutivt talpar (~44%) och en rad med 5 par, nämligen den 581:e dragningen (vecka 47 år 1991) som gav följande tal 15 32 33 34 35 36 37.

Låt oss nu för skoj skull simulera detta. Koden som används ser ut så här:


num.talpar = function(num.sims=1283, n=35, m=7) {
# initiera tabellen som kommer att innehåla antalet
# konsekutiva talpar. Det kan vara max m-1 (här 7-1=6) sådana talpar,
# men vi måste även ha med 0, vilket innebär att det blir m stycken
konsek.talpar = rep(0, m)
for (i in 1:num.sims) {
ss = sort(sample(1:n, m))
dd = diff(ss) # differensen mellan talen
tt = sum(dd==1) # hur många konsekutiva talpar finns det
# öka med 1. Not: "tt+1" är för att även få med dragninar som
# inte har något konsekutivt talpar
konsek.talpar[tt+1] = konsek.talpar[tt+1] + 1
}
return(konsek.talpar)
}


Här är en sådan körning som har värden som inte är helt olika de faktiska (dvs Hästbacka-datan). Först antal och sedan fördelningen.

> (ss = num.talpar(1283))
[1] 314 519 353 88 8 0

> round(ss/1283,2)
[1] 0.24 0.40 0.28 0.07 0.01 0.00

För just denna simulering blev det alltså cirka 314 dragningar (cirka 24%, av 1283 rader) utan något konsekutivt talpar alls, 519 dragningar med ett sådant talbar, och hela 8 dragningar med 5 k.t.p (dvs där det finns 6 konsekutiva tal).

Om vi nu brassar på med 100 sådana här simuleringar om vardera 1283 dragningar, dvs 1283*100 = 128300 dragningar (och delar de värden vi får med 100) så får vi något mer exakta värden att jämföra med:


> (ss=num.talpar(1283*100)/100)
[1] 299.31 540.63 339.48 92.53 10.60 0.45 0.00

> round(ss/1283,2)
[1] 0.23 0.42 0.26 0.07 0.01 0.00 0.00

Vi ser alltså att det finns cirka 23% chans att det blir 0 stycken k.t.p., cirka 42% att det blir exakt ett k.t.p. osv.

Den intressanta frågan blir då vad är det (simulerade) genomsnittet konkekutiva par per dragning. I faktisk data blev det cirka 1.1 konsekutivt par per dragning.


sum.talpar = function(num.sims=1283, n=35, m=7) {
antal.talpar = 0
for (i in 1:num.sims) {
ss = sort(sample(1:n, m))
dd = diff(ss) # differensen mellan talen
tt = sum(dd==1) # hur många konsekutiva talpar finns det
antal.talpar = antal.talpar + tt
}
return(antal.talpar)
}
sum.talpar()


Först en enkel körning för att få en känsla för informationen.

> ss = sum.talpar(1283)
[1] 1580

> ss/1283
[1] 1.231489

Och sedan en lite tyngre körning


> sum.talpar(1283*100)/(1283*100)
[1] 1.200514

Dvs det blir cirka 1.2 konsekutiva talpar per dragning. Det är alltså mer än ett par i genomsnitt.

Hur fördelas differenserna av talen?
Ovan har vi endast studerat konsekutiva talpar, dvs tal där differensen är 1. Nen det är även intressant att studera övriga differenser som uppkommit i dragningarna. Det vi ovan kallat för "konsekutiva talpar" är talpar med differensen 1, vilket vi i det följande kallar "1-differens".

I Hästbacka-datan fördelas sig differenserna enligt följande (på formatet differens: antal förekomster). Notera att en dragning nästan alltid har flera olika differenser. T.ex. ovanstående 5-talpars-dragning (15 32 33 34 35 36 37) har fem stycken 1-differenser samt en 17-differens (dvs 32 - 15 = 17).

1: 1429
2: 1184
3: 939
4: 790
5: 683
6: 585
7: 447
8: 345
9: 283
10: 231
11: 207
12: 126
13: 108
14: 99
15: 66
16: 48
17: 44
18: 17
19: 22
20: 11
21: 16
22: 2
23: 5
24: 2
25: 3

Man kan här se att det är flest 1-differenser, sedan blir det ständigt färre och färre.


OK, för fullständighets skull så simulerar vi även detta. Koden är rätt lik den föregående.

diff.table.sim = function(num.sims=1283, n=35, m=7) {
diff.table = rep(0, n)
for (i in 1:num.sims) {
ss = sort(sample(1:n, m))
dd = diff(ss) # differensen mellan talen
# lägg in respektive differens i tabellen
for (d in dd) {
diff.table[d] = diff.table[d] + 1
}
}
return(diff.table)
}

Det vi söker är alltså det genomsnittliga antalet differens per dragning, så vi simulerar 100000 dragningar.

> cbind(diff.table.sim(100000)/100000)
[,1]
[1,] 1.19969
[2,] 0.98629
[3,] 0.80547
[4,] 0.65678
[5,] 0.52912
[6,] 0.42424
[7,] 0.33684
[8,] 0.26439
[9,] 0.20978
[10,] 0.15981
[11,] 0.12235
[12,] 0.09001
[13,] 0.06614
[14,] 0.04662
[15,] 0.03512
[16,] 0.02358
[17,] 0.01583
[18,] 0.01097
[19,] 0.00734
[20,] 0.00406
[21,] 0.00281
[22,] 0.00149
[23,] 0.00073
[24,] 0.00033
[25,] 0.00013
[26,] 0.00006
[27,] 0.00002
[28,] 0.00000
[29,] 0.00000
[30,] 0.00000
[31,] 0.00000
[32,] 0.00000
[33,] 0.00000
[34,] 0.00000
[35,] 0.00000

Varvid vi kan se att det är i genomsnitt (nästan) 1.2 stycken 1-differenser (dvs det vi ovan kallade konsekutiva talpar) per dragning, i genomsnitt 0.99 2-differens per rad osv.


Genomsnittlig antal differenser
Det genomsnittliga antalet differenser är cirka 4.53 enligt följande simulering. Här delas summan av differensvärdena med det totala antalet uppkomna differenser. (Man kan trixa med föregående värden, men jag vill ha lite kontroll över saker och ting.)

diffs = function(num.sims=1283, n=35, m=7) {
diffs = 0
num.diffs = 0
for (i in 1:num.sims) {
ss = sort(sample(1:n, m))
dd = diff(ss)
for (d in dd) {
diffs = diffs + d
num.diffs = num.diffs + 1
}
}
m = diffs/num.diffs # genomsnittligt antal
return(c(diffs, num.diffs, m))
}

Och så körningen, där vi endast är intresserade av det sista värdet:


> round(diffs(1283*100),3)
[1] 3465204.000 769800.000 4.501

Vilket alltså ger det genomsnittliga differensvärdet 4.501. Äh, vi säger 4.5.


Sammanfattning
Här ovan har vi kommit fram till bl.a. följande:

* Sannolikheten att det ska förekomma åtminstone ett konsekutivt talpar i en 7/35-dragning är cirka 77%
* Det blir i genomsnitt 1.2 konsekutiva talpar per dragning.
* Det genomsnittliga differensvärdet för en dragning är 4.5.

Som antytts så anser i alla fall jag att det är förvånande.

Upprinnelse (inspiration)
Upprinnelsen till allt detta var notisen Consecutive pairs in winning lottery numbers hos MathForge.


Se även
Se även min genomgång av födelseparadoxen,tillika med R-kod, i Sammanträffanden - anteckningar vid läsning av Diaconis och Mosteller 'Methods for Studying Coincidences'.

Jämför även med den simulering som gjordes för ett liknande problem (6/49-Lotto) i Lite om resampling, simulering, sannolikhetsproblem etc.. Sök efter "Litet problem i (engelsk) Lotto". (Det koms dock inte fram till exakt samma sak.)

Samt överhuvudtaget Simulation, probability theory etc, såsom Trisssimuleringen (Java applet).

Posted by hakank at 03:37 EM Posted to Matematik | Statistik/data-analys | Comments (8)

augusti 03, 2005

Roterade ord (shifted words)

Som ett led i det ständiga sökandet efter struktur i vårt språk har nu strålkastarna kommit till roterade ord ("shifted words").

Roterat ord
Ett roterat ord är ett ord som bildar ett annat ord om man flyttar en eller flera bokstäver till slutet av orginalordet. T.ex. om man från ordet "affinerar" flyttar (roterar) första a:et och placerar det sist blir det "raffinerar", grafiskt åskådliggjort på följande sätt:

affinerar -> raffinera

Ovanstående var en 1-rotation (dvs man roterar 1 bokstav). Mer generellt kan man göra n-rotationer och får sådana konstruktioner såsom:

ansträngt -> trängtans (3-rotation)
tonåringar -> artonåring (8-rotation)

Vänster vs. högerrotation
Not: Rotationen ovan var en rotation s.a.s. åt vänster. Skulle man göra högerrotation i stället skulle det bli andra rotationstal, eventuellt lägre. T.ex. vänsterrotationstalet 8 för "tonåringar" -> "artonåring" motsvarar högerrotationstalet 2. Mer generellt: vänsterrotationstal = ordlängd - högerrotationstal. Skulle man göra en "optimal" rotation, dvs ta den höger- eller vänsterrotation som är lägst blir det maximalt en rotation på Len / 2, där Len är ordets längd.


Symmetri
En rotation är självklart även symmetrisk i betydelsen att en rotation "ord1 -> ord2" med rotationstalet Rot motsvarar rotationen "ord2 -> ord1" med ett rotationstal Len - Rot.


Högsta vänsterrotationstalen
De högsta vänsterrotationstalen som hittades var n=13.

nationaliserade -> denationalisera
sensibiliserade -> desensibilisera
transformatoreffekt -> effekttransformator
transformatorström -> strömtransformator


Sammansättningar
Tyvärr är många av dessa högre roteringar tråkiga sammansattningar av två ord (Ord1 och Ord2) på formen "Ord1Ord2" -> "Ord2Ord1", t.ex. just "transformatorström" -> "strömtransformator". (Någonstans finns här en potential att göra automatiserad uppdelning av sammansatta ord, dvs att den del av ordet som roterats torde vara ett giltigt ord, liksom den del som är kvar.)


Multirotationsord
Det finns några multirotationsord, dvs som ger andra ord för olika rotationer. T.ex följande (inon parentes anges vänsterrotationstalet):

anar -> nara (1)
anar -> aran (2)
anar -> rana (3)

aren -> rena (1)
aren -> enar (2)
aren -> nare (3)

asar -> sara (1)
asar -> aras (2)
asar -> rasa (3)

argas -> gasar (2)
argas -> sarga (4)

alarm -> larma (1)
alarm -> malar (4)

aspar -> spara (1)
aspar -> paras (2)
aspar -> raspa (4)

eskapad -> skapade (1)
eskapad -> kapades (2)

raskatt -> kattras (3)
raskatt -> traskat (6)

jojo -> ojoj (1)
jojo -> jojo (2)
jojo -> ojoj (3)

hihihi -> hihihi (2)
hihihi -> hihihi (4)


Rotationsgrupp
Ord såsom "anar", "nara", "aran" samt "rana" bildar en fullständig rotationsgrupp, dvs att samtliga rotationer av ett ord bildar ett annat giltigt ord. Här är "anar" en generator, dvs den som startar just denna rotationssekvens. Andra sådana fullständiga rotationsgrupper är ("aren", "rena", "enar", "nare") samt ("asar", "sara", "aras","rasa"). (Begreppet "grupp" här får gärna förväxlas med det matematiska gruppbegreppet.)


"Cykliska"
Man bör också notera de "cykliska" orden såsom "jojo" -> "ojoj", samt "hihihi" -> "hihihi" (som är ett "egenroterande"/"egencykliskt" ord) där det blir samma ord för varannan rotation.


Transitivitet
Och nog katten är rotationstal transitiva över addition (med bibehållande av roteringsriktningen). Om en rotation ord1 -> ord2, har rotationstalet R1 och rotationen ord2 -> ord3 har rotationstalet R2 så har rotationen ord1 -> ord3 rotationstalet R1 + R2. Här måste man vara noga med att hålla reda på vilken "bas" man arbetar med, dvs vilket ord man gör rotationen från. "Basen" anges inom parentes efter rotationstalet, t.ex. "1(anar") betyder att det är vänsterrotationstalet 1 från "anar", vilket alltså är ordet "nara".

Som exempel kan vi ta rotationsgruppen med "anar" som generator:

anar -> nara -> aran -> rana
(0) (1) (2) (3)

nara: anar -> nara: R1 = 1(anar)
aran: nara -> aran: R2 = 1(nara) = 2(anar)
rana: aran -> rana: R3 = 1(aran) = 2(nara) = 3(anar)

Rotationstalet för rotationen anar -> rana är alltså 1(anar) + 1(nara) + 1(aran) = 1 + 1 + 1 = 3(anar). (Vilket egentligen inte är något märkvärdigt alls.)


Ordlista
En fullständig lista över de upphittade roterade orden (6672 ordpar) finns här (rätt stor fil, > 270kB). Filen består av två delar. Först är alla ord, rad för rad på formen:

ord -> roterat ord (antal roteringar)

Efteråt i filen kommer en lista över ord som har ett visst (vänster)roteringstal.


Anagram
Not: Rotationsord är en delmängd av anagram, där man kan skyffla runt bokstäverna lite hur som helst (man måste använda samtliga bokstäver i ordet).

Posted by hakank at 12:56 EM Posted to Språk | Comments (1)

augusti 02, 2005

Skånsk bloggaremiddag 14 august 2005, 13.00, Kin Long, Malmö. OBS! Ändrat datum till den 14:e!

OBS. Datum är ändrat från den 7:e till den 14:e! Hoppas att fler kan komma då.

Mer specifika koordinater för kommande skånska bloggaremiddag är nu bestämda. Förra gången bestämdes vilket datum, men inte exakt klockslag eller plats. Det föreslås bli nedanstående.

Tid: Söndagen 14 augusti 2005, 13.00 (det är alltså kommande söndag) (OBS! Nytt datum.)
Plats: Kinesrestaurangen Kin Long, Malmö (vid Triangeln).

Se t.ex. tidigare anteckningar (googlesökning) för att få en eller flera uppfattningar om vad som varit på tapeten vid de föregående träffarna.

Meddela helst om du är intresserad av att komma genom att kommentera i denna blogganteckning eller maila mig.

Posted by hakank at 09:18 FM Posted to Blogging | Comments (22)