Med anledning av en fråga i Java-forumet ställdes jag inför problemet hur man definierar en välblandad kortlek. I mitt kodexempel använde jag mig av en heltalsarray med längden 52 som initierades med :
<code>
for (int i=0;i<52;i++)
kortlek(i)=i;
</code>
där färg och valör definierades som :
<info>
valör = kortnummer modulus 13 (0 till 12)
färg = kortnummer heltalsdividerat med 13 (0 till 3)
</info>
Så nu till min fråga, hur definierar man en välblandad kortlek? I princip ska ju inte alltför många kort ligga kvar på sin ursprungliga plats för att den ska vara väl sorterad, såvida det inte slumpar sig så. Så hur många kort ska i genomsnitt ligga på rätt plats i en välsorterad kortlek? Mitt lilla testprogram visade att ett (1) kort ska ligga på rätt plats oavsett kortlekens storlek1. Är det så enkelt att sannolikheten att första kortet ska ligga på rätt plats är 1/52, samma för andra kortet o s v så att :

1/52 + 1/52 + ... + 1/52 = 52*1/52 = 1 ???

Det är för länge sedan jag läste statistik men ovanstående formel verkar för enkel. Om första kortet ligger fel så minskar ju sannolikheten att resten av korten ligger rätt eftersom ytterligare ett kort då måste vara felaktigt placerat, om jag tänker rätt.

Jag skulle snarare ha gissat att det handlar om en kvot där antalet permutationer av 52 kort är en del i uttrycket (52!). Någon som har detta aktuellt som kan visa att det ska bli ett (1) oavsett kortlekens storlek?

'Är det så enkelt att sannolikheten att första kortet ska ligga på rätt plats är 1/52, samma för andra kortet o s v'

Är det inte så här? :
1/52 för första kortet. När sen första kortet har "hamnat rätt" så har du ju bara 51 möjliga "korrekta" platser för nästa kort, dvs 1/51... osv

Sannolikheten att de två första korten ligger på rätt plats borde väl då bli
<code>
1 1 1
--- * --- => -------
52 51 52*51
</code>
vilket i sin tur borde ge sannolikheten
<code>
1
-------
52! <----- "Fakulteten av 52"
</code>
för att alla kort ligger på rätt plats..???

Frågan är om man inte skall tänka lite baklänges i detta fall...
Jag menar, sannolikheten för att första kortet inte ligger på samma plats i leken är ju 51/52... När man sen skall beräkna sannolikheten för nästa kort börjar det ju bli intressant...
Sannolikheten för det andra kortet borde då vara 50/51 såvida inte första kortet hamnade på andra kortets ursprungsplats då sannolikheten blir 51/51...
Å tredje kortet... 49/50... eller 50/50... beroende på var de två förra hamnade...

Som du ser så kommer vi "farligt nära" 1 här... om min teori stämmer... fast det var 10 år sen jag läste sannolikhetslära. Iofs har jag undervisat i matte... dock inte i sannolikhet... ;)

Innan vi räknar på sannolikheter måste vi komma fram till en bra definition av "välblandad".

Att inte för många kort får finnas på sina "rätta" platser är alltför naivt, vilket följande exempel visar:
Utgå från en fullständigt sorterad kortlek där alla kort ligger på rätt plats. Tag sedan det översta kortet och placera i botten. Då ligger inget kort på rätt plats. Men är leken välblandad? Knappast...

Välblandat är väl när man blandar enligt principen:
Dela leken i två ungefär lika stora högar
tag 1-3 kort från botten på hög 1, lägg 2-3 från botten på hög 2 ovanpå dessa
upprepa tills båda högarna är slut
upprepa ett par gånger (4-10st?)

Tycker det är mysko definitioner ni gör...

Välblandat borde väl inte sättas i relation till en ordnad kortlek på det sättet ni säger?
Det är väl snarare blandningen som kan vara fullständig eller inte.

En metod jag anser vara lämplig är följande:
Börja med en kortlek (sorterad eller osorterad, hur som helst) i vänster hand.
1. Ta det översta kortet i vänster hand, lägg i en hög.
2. Ta det översta kortet i vänster hand, lägg slumpartat någonstans i högen.
3. Upprepa från 2.

Eller så tar man en slumpvis från vänster och lägger överst i högen, det är ju skit samma.

På detta sätt är varje enskild blandning lika trolig, och då är det per (min) definition så blandat det kan vara.

Niklas metod :
"1. Ta det översta kortet i vänster hand, lägg i en hög."
"2. Ta det översta kortet i vänster hand, lägg slumpartat någonstans i högen."
"3. Upprepa från 2."

Det är ju förstås en mycket bättre lösning som dessutom bara kräver 52 förflyttningar. Men hade jag valt den lösningen först så hade jag ju aldrig börjat fundera på hur man mäter hur bra blandad en kortlek är :-)

Jag tycker inte min "mätmetod" är så tokig. Jag påstår ju inte att antalet kort på rätt plats ska vara 1 varje gång kortleken blandas om. Det är ju ett statistiks fenomen, så genomsnittet ska närma sig 1 om man granskar många kortlekar.

En kortlek där alla kort ligger ett steg fel kan ju vara blandad på ett korrekt slumpmässigt sätt om det har slumpat sig att korten hamnade så. Som några av er påpekat så är det rimligare att blandningsprocessen ska vara "slumpmässig" och inte kortens slutgiltiga placering.

Men trots detta så är det ju rimligt att några kort hamnar på "rätt" plats, och detta måste gå att räkna ut ganska lätt. Detta måste väl vara ett korrekt sätt att mäta hur bra en blandningsprocess är på samma sätt som man kan kolla hur välformad en tärning är genom att kasta tärningen 10000-tals gånger och ta medelvärdet av antalet ögon och jämföra med det förväntade talet 3,5. Om det avviker mycket från detta värde är ju tärningen troligen(!) inte välformad. Det kan ju dock vara en slumpmässig avvikelse...

Mina simuleringar gav som sagt att om man granskar många välblandade kortlekar så ligger i snitt 1 kort på rätt plats oavsett kortlekens storlek...någon som kan bevisa det? Jag har även kollat att det stämmer för kortlekar med upp till 4 kort manuellt på papper.

Intressant frågeställning, det måste jag säga...Man kan ju faktiskt hålla med om att det borde finnas något mätetal på kortlekens blandning trots allt.

Misstänker dock att det är ganska knepigt... man kan ju köra vidare på ditt exempel med tärningen...
Det kan ju bli 3,5 om det bara är ettor och sexor, så då får man kolla på någon form av standardavvikelse också. I fallet tärning är det väl kanske lite lättare, men att titta på en hel kortlek verkar ganska krångligt...
Vet inte med er andra, men själv ska jag nog ta och fundera en del på det här.

Har tänkt lite och har hittills kommit fram till följande:

Till att börja med; lite mer precis problemformulering:
--
Tänk en kortlek med n kort. Det finns n! olika kombinationer.
För varje av dessa kombinationer kommer det ligga ett antal kort rätt. Vi kallar detta antal för x(n). Medelvärdet av antalet korrekt lagda kort måste sålunda vara x(n)/n!.

Vår hypotes är att detta tal är 1.
--

Okej... om vi nu tänker oss en kortlek på ett kort (vi numrerar dem med 1, 2, osv.) så har vi en kombination; (1), och den har ett kort rätt, vilket ger genomsnitt 1.
Har vi två kombinationer så har vi (1,2) och (2,1) => 2 rätt vs 0 rätt, genomsnitt 1.
3 kort => 6 komb: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), med 3, 1, 1, 0, 0, 1 rätt. Summa 6 rätt=genomsnitt 1.

Vilket gör hypotesen mycket trolig. Om vi nu antar att vi har lagt de första k korten rätt så kommer det ligga x(n-k)+k*(n-k)! kort rätt. (Det ligger x(n-k) rätt i de nya korten, det finns k rätta kort i varje kombination, och det finns (n-k)! kombinationer).

Själv tycker jag det känns lite mysko just nu eftersom ett stort antal fall är borttagna, de där färre än k är rätt. Har lite funderingar på om man kan trixa fram och tillbaka med formeln, men är mycket osäker. Nån som har förslag?

Jag tror att jag är nära lösningen nu...

Det finns två olika möjligheter för första kortet, antingen ligger det på rätt plats eller inte. Om vi undersöker dessa var för sig så får vi :

a) Första kortet ligger på rätt plats : Sannolikheten för detta är 1/n och vi har nu egentligen exakt samma situation som vi startade med fast med endast n-1 kort.

b) Första kortet ligger på fel plats : Sannolikheten för detta är (n-1)/n och vi har en ny situation där n-1 kort ska placeras ut på n-1 platser men 1 kort kan aldrig placeras rätt. Därför var jag tvungen att definiera en ny funktion :

x(n,k) = genomsnittligt antal kort som placeras rätt på n platser där k av korten är "ogiltiga" och som omöjligt kan placeras rätt. Endast n-k kort kan alltå placeras korrekt. (Notera att min definition av x() skiljer sig från Niklas funktion med en faktor på n!. Jag orkade inte skriva om texten efter att jag noterat detta själv.)

Alltså skriver vi om problemet :

Vi vill visa att

x(n,0) = 1 för alla n=1,2,3,...

Situationen beskriven ovan kan alltså skrivas :

(1) x(n,0) = 1/n * x(n-1,0) + (n-1)/n * x(n-1,1)

och kanske gäller det generellt för alla k? Dvs

x(n,k) = 1/n * x(n-1,k) + (n-1)/n * x(n-1,k+1)

men här körde jag fast så jag började resonera på ett annat sätt i stället.

I det generella fallet med n kort varav k är "ogiltiga" så har vi n-k kort som har en chans att placeras rätt. Dessa ska placeras ut på n platser. Sannolikheten för att vart och ett av dessa n-k kort ska hamna på rätt plats är 1/n och totala antalet kombinationer är n! :

Antalet kort på rätt plats för en specifik kombination : (n-k) * 1/n

Antalet kort på rätt plats för alla kombinationer : (n-k) * 1/n * n!

(2) x(n,k) = (n-k) * 1/n * n! / n! = (n-k)/n

Vi ser direkt att

x(n,0) = (n-0)/n = 1

Q.E.D.

Vi vet också att x(n,n)=0 för alla n eftersom det motsvarar fallet när det bara återstår "ogiltiga" kort som inte kan placeras rätt. Formeln visar att :

x(n,n) = (n-n)/n = 0/n = 0

Så långt är jag riktigt nöjd. Problemet är att när man sätt in x(n,k)=(n-k)/n i formel (1) så får man :

x(n,0) = 1/n * ((n-1)-0)/(n-1) + (n-1)/n * ((n-1)-1)/(n-1) =

= 1/n + (n-2)/n = (n-1)/n <> 1 !!!!!!!!

Nu är klockan 5 på morgonen och jag är svintrött så jag har väl räknat fel någonstans, men jag försökte i alla fall :-)

Go natt...

Tänkte spinna vidare på Niklas idé.

Hans uttryck för genomsnittligt antal kort på rätt plats, x(n)/n!, är rätt.
Problem är att vi behöver ett sätt att bestämma x(n).

Antalet gånger ett specifikt kort förekommer bland alla möjliga kombinationer är n! vilket stämmer eftersom antalet kombinationer är n! och varje kort finns en gång i varje kombination.

Anta sedan att spridningen för ett specifikt kort bland alla möjliga platser är likformig.
Antalet gånger ett specifikt kort befinner sig på en specifk plats blir då: n!/n.

Detta innebär också att ett specifikt kort kommer att befinna sig på rätt plats n!/n gånger. Då antalet kort är n, kommer det totala antalet kort som befinner sig på rätt plats bland n! kombinationer att bli n!/n*n = n!, x(n)=n!.

Det genomsnittliga antalet kort i en kortlek som ligger på rätt plats blir då: x(n)/n! = n!/n! = 1.

Jag har kontrollerat detta för hand upp till 6 kort och med datorn till 10 kort.

/Pedro Cunha

Jag tror du är helt rätt ute och att ditt resonemang visar nog att jag också var rätt ute. Titta på min formel (2) ovan :

(2) y(n,k) = (n-k)/n

Jag kallar min funktion y() fr o m nu eftersom er funktion x() ger antalet korrekt kort för samtliga kombinationer medan min ger medelvärdet (faktorn n! alltså).

x(n,k) = y(n,k) * n! = (n-k)/n * n!

men problemet vi vill lösa är ju när k=0 så

x(n,0) = (n-0)/n * n! = n!

vilket är samma resultat som du får fram. Min formel löser ju ett mer generellt problem så ditt resonemang är betydligt enklare att förstå. Jag önskar att jag gått den vägen redan från början, så hade jag kanske inte behövt sitta till kl 5 i morse :-)

> I det generella fallet med n kort varav k är "ogiltiga" så har vi n-k kort som har en
> chans att placeras rätt. Dessa ska placeras ut på n platser. Sannolikheten för att
> vart och ett av dessa n-k kort ska hamna på rätt plats är 1/n och totala antalet
> kombinationer är n! :
>
> Antalet kort på rätt plats för en specifik kombination : (n-k) * 1/n
>
> Antalet kort på rätt plats för alla kombinationer : (n-k) * 1/n * n!

Här hänger jag inte med riktigt. Jag tycker att du inte tar hänsyn till att två kort inte kan placeras på samma plats.