Slottet, slumpen, sannolikheten och strategierna

Pelle och Lisa besöker Versailles. Endast bottenvåningen är tillgänglig för besökare (det går inte att förflytta sig uppåt).Våningen utgörs av m × n kvadratiska rum, med dörrar emellan.⁽¹⁾ Från varje rum kan man ta sig till fyra angränsande rum.⁽²⁾ Låt oss också säga att det finns fönster i alla rum med ytterväggar, och i hörnrum, så att man där (men bara där) kan orientera sig efter solen.

Pelle och Lisa kommer ifrån varandra. De måste nu leta upp varandra igen. Hur lång tid kan det tänkas ta? I värsta fall? I bästa fall? I genomsnitt? Beroende på vilken strategi de eventuellt har kommit överens om på förhand? Eller beroende på de strategier som var och en funderar ut först när situationen uppstår?

Vi antar att de båda i varje tidsintervall förflyttar sig från ett rum till något av de angränsande rummen. Självklart kan de också välja att stanna i det rum där de för närvarande befinner sig, under ett eller flera tidsintervall.⁽³⁾

Om de båda irrar omkring planlöst i slottet kan sannolikheten för att de ska återfinna varandra i ett visst tidsintervall uppskattas till 1 / mn.⁽⁴⁾⁽⁵⁾ I genomsnitt krävs det alltså omkring mn intervall. I bästa fall träffas de redan efter ett enda intervall. I värsta fall träffas de aldrig.⁽⁶⁾

Om Lisa stannar kvar på samma ställe och Pelle irrar runt planlöst, eller vice versa, gäller samma resonemang som ovan.⁽⁷⁾

Om Lisa stannar kvar på samma ställe och Pelle systematiskt söker igenom våningen⁽⁸⁾ krävs max mn - 1 förflyttningar. I genomsnitt krävs då mn / 2 intervall.⁽⁹⁾  Men om båda stannar kvar på samma ställe, träffas de aldrig igen.

Det naturligaste sättet att söka igenom våningen systematiskt är att förflytta sig uppåt n rum; sedan till vänster; därefter nedåt n rum, och sedan till höger, o.s.v., m gånger. Eller, på motsvarande sätt, att förflytta sig till höger m rum; sedan uppåt; därefter till vänster m rum; och sedan nedåt, o.s.v., n gånger.^(10)(11) Låt oss kalla dessa båda strategier vertikal respektive horisontell avsökning.

Om både Pelle och Lisa söker i samma ledd (horisontellt eller vertikalt), och åt samma håll, träffas de i värsta fall aldrig. (Men kanske ibland, och ganska snart, beroende på var de börjar, och eventuellt beroende på våningens dimensioner, m och n... Här är jag osäker.) Om de båda söker i samma ledd men åt olika håll krävs som mest mn / 2 tidsintervall. (Tror jag, men se ovan.)

Om de söker i olika ledd men åt samma håll; eller i olika ledd och åt olika håll - hur blir det då?

Om Pelle och Lisa inte har kommit överens om en strategi på förhand, hur bör de då agera? Det systematiska sökandets framgång är ju avhängig av vilka val de båda gör, och om valen inte är koordinerade på förhand är den därför avhängig slumpen.

Ett förslag är att var och en förflyttar sig till ett hörn, och alternerar mellan att vänta där (så många tidsintervall som det tar för den andra personen att ta sig ett varv runt ytterkanterna) och att själv ta ett varv runt kanterna. Men inte heller denna strategi eliminerar risken för att rundturerna är synkroniserade så att den ena hela tiden rör sig framför den andra. Ett sätt att minska denna risk är att justera väntetiden genom att multiplicera det antal tidsintervall som krävs för en rundtur med ett primtal. (Ungefär som vissa insekter gör för att undvika rovdjur under sina sällsynta parningssäsonger.) Det finns fortfarande en risk att båda väljer samma primtal, men annars kommer de så småningom att träffas. Alternativt kan de variera sin väntetid genom att efter varje rundtur slumpmässigt välja ett nytt primtal och sedan vänta så många intervall innan de påbörjar nästa rundtur.

Den mest framgångsrika strategin måste väl vara att söka sig mot mitten av våningen. Om båda gör det träffas de garanterat efter ett minimalt antal intervall. Förutsatt att det finns ett rum "i mitten". Och det beror på våningens dimensioner. Om både m och n är udda tal finns det ett enda mittersta rum. Att ta sig dit kräver maximalt (m + n) / 2 intervall. Om m är jämnt och n är udda (eller vice versa) finns en mittersta rad (eller kolumn) av två intilliggande rum. Alla strategier, förutom att stanna kvar i det första rum man når, garanterar att man träffas efter högst en ytterligare förflyttning. Men om m och n båda är jämna tal utgörs mitten av en kvadrat med 2 × 2 rum. Och det räcker för att ingen (icke på förhand avtalad) strategi kan garantera att man någonsin möts.

Hur svårt är det egentligen att räkna ut maximal och genomsnittlig tid för att återfinna varandra, beroende på beteende? Är det ens möjligt? Vad kan man göra annars? Simulera! Modellera alla tänkbara scenarier i en dator och testköra ett stort antal gånger.

(Och här kommer förstås en beskrivning av modellering och testkörningsresultat, och en jämförelse mellan dessa och de teoretiska värdena.)

---

⁽¹⁾ Dörrarna är stängda. Och tjocka, och tunga, och stänger sig själva när man har öppnat dem.

⁽²⁾ Eller tre, eller två, beroende på om man befinner sig vid en yttervägg eller vid ett hörn.

⁽³⁾ Hur långt är ett tidsintervall? Det vet vi inte, och det spelar ingen roll: Vi är blott intresserade av hur många tidsintervall som krävs för en återförening. (Men låt oss säga att det tar 10 sekunder att röra sig från ett rum till ett annat.)

⁽⁴⁾ Uppskattningen baseras på att de båda, i varje intervall, kan befinna sig i vilket som helst av de mn rummen. Sannolikheten för att de båda ska befinna sig i ett visst rum är därför 1 / (mn)². Men eftersom vilket som helst av rummen är en tänkbar mötesplats är sannolikheten att de båda samtidigt befinner sig i något rum 1 / mn.

⁽⁵⁾ Den här uppskattningen är kanske inte helt realistisk, eftersom det rum som en person befinner sig i vid tidpunkt t är beroende av i vilket rum personen befann sig vid tidpunkt t-1. Men om vi antar att placeringarna är oberoende av varandra överskattar vi antalet möjligheter, vilket är att föredra när vi vill beräkna en övre gräns för tidsåtgången.

⁽⁶⁾ Åtminstone kan antalet tidsintervall bli godtyckligt stort.

⁽⁷⁾ Vilket kanske verkar konstigt. Men tänk dig att du slår två tärningar: Hur stor är sannolikheten att du får ett par? Det spelar ingen roll om du först slår en tärning och därefter den andra; eller om du slår båda  tärningarna samtidigt. Sannolikheten att få ett par är 1/6 (6 * 1 / 6²). Om du i stället placerar en av tärningarna med en viss sida upp (vilket motsvarar att en person stannar kvar i samma rum) och bara slår den andra, vad är då sannolikheten att denna andra tärning visar samma sida som den du valt på förhand? Den är fortfarande 1/6.

⁽⁸⁾ Det vill säga att Pelle aldrig besöker ett rum två gånger (innan han besökt alla andra rum). Detta är möjligt eftersom Pelle kan utgå från en yttervägg eller ett hörn (och förmågan att skilja mellan höger och vänster). Inga fönster krävs.

⁽⁹⁾ Under antagandet att sannolikhetsfördelningen är likformig, vilket i det här fallet innebär att Pelle och Lisa kan befinna sig på vilka platser (avstånd från varandra) som helst, med samma sannolikhet, när de "upptäcker" att de har kommit ifrån varandra.

⁽¹⁰⁾ Beroende på vilket hörn man utgår ifrån börjar man antingen att röra sig uppåt eller nedåt; antingen till vänster eller till höger. Det finns alltså totalt fyra varianter.

⁽¹¹⁾ Vi utgår alltså ifrån att man först tar sig till ett hörn, och bortser från de förflyttningar som krävs för  att göra detta.