Postawiona niedawno zagadka pyta o to, jakie są szanse na nieskończony rozwój kolonii bakterii, jeżeli zaczynamy od jednej bakterii, a każda bakteria ma w każdym cyklu 80% szans na podwojenie oraz 20% szans na śmierć.
Podejść do rozwiązania można na co najmniej dwa sposoby: symulacyjnie lub analitycznie. Zaczniemy od tego drugiego.
Oznaczmy sobie prawdopodobieństwo śmierci kolonii przez x. Tym samym szanse na jej przetrwanie wynoszą (1-x).
Na start bakteria jest tylko jedna. Co się teraz może wydarzyć? Może ona paść albo się rozmnożyć do dwóch sztuk. Rozmnożenie owo występuje średnio osiem razy na dziesięć.
A jak już mamy dwie bakterie, to szansa, że obydwie padną w kolejnym cyklu wynosi x2. A szansa, że nie padną: 1-x2.
Wiemy też, że szansa na to, że po pierwszym kroku będą dwie bakterie wynosi 80%, czyli 0.8. Tak więc szansa na to, że obydwie bakterie nie wymrą po drugim kroku wynosi 0.8(1-x2).
Ale z samego początku rozumowania wiemy też, że szansa na przetrwanie kolonii to (1-x).
Mamy więc równość: 1-x = 0.8(1-x2), z której łatwo wyliczamy, że x=0.25, czyli szanse na przetrwanie kolonii wynoszą 75%.
A jak ktoś nie lubi liczyć, zawsze pozostaje symulacja. Na przykład taka:
from random import random
maxtrials = 100000
success_count = 0
probability = 0.8
for trials in range(maxtrials):
population = 1
while(population > 0 and population < 100):
newpopulation = 0
for n in range(population):
if(random() <= probability):
newpopulation += 2
population = newpopulation
if(population > 0):
success_count += 1
print(success_count / maxtrials)Założyłem tu upraszczająco, że jeżeli populacja przekroczy 100 osobników, to już na pewno przeżyje. Daje to minimalnie zawyżone wyniki, ale różnica jest pomijalnie mała. Powyższy kod zawsze zwraca liczbę w okolicy 0.75, czyli tyle, ile wyszło nam poprzednio z obliczeń.
Ponadto z symulacji wychodzi mi, że kolonia rozrasta się do setki średnio w 10-11 pokoleniach, a pada średnio w dwóch (a więc jak już przeskoczy 3-4 pokolenia to raczej przeżyje), co jednocześnie pokazuje, że ustawienie "nieskończoności" na poziomie 100 to całkiem przyzwoity zapas bezpieczeństwa.
A jak Wam poszło?
Tym razem tylko jedna osoba podeszła do rozwiązania: Waldek przysłał poprawną odpowiedź opartą na nieskończonej sumie. Skoro, mówi Waldek, szansa że jedna bakteria nie przetrwa wynosi 0.2, to trzeba posumować (0.2)x od jeden do nieskończoności - w wyniku dostajemy 0.75. Gratuluję wygranej!
P.S. W ostatniej chwili drugie rozwiązanie nadesłał - tak dla odmiany - również Waldek. Tym razem rozpisane bardziej szczegółowo (i równie prawidłowo jak pierwsze):
W związku z powyższym Waldek powinien sobie teraz wziąć dwa ziemniaki: z mniejszego zrobić medal, a z większego wyciąć cztery równej długości słupki i połączyć je ze sobą w pętelkę pod kątem prostym, wreszcie na koniec wetknąć ów medal między te połączone słupki i w efekcie otrzymać medal do kwadratu.
Oj, za szybko pojawiło się rozwiązanie, za szybko. Widziałem wcześniej, ale dopiero teraz miałem chwilę, by siąść do rozwiązania, a tu już rozwiązanie było. Symulacji nie pisałem, niemniej wychodziło na czuja właśnie 25% – 20% szans na wymarcie w pierwszym pokoleniu, 4% w kolejnym, czyli 5 razy mniej. Co już daje 24% i pachnie ciągiem 1/5 + 1/5^2 + 1/5^3 +…, który na oko zbiega się w 25% właśnie. Wolframalpha potwierdza https://www.wolframalpha.com/input/?i=1%2F5+%2B+1%2F5%5E2+%2B+1%2F5%5E3+%2B+…
To była bardzo prosta zagadka, moim zdaniem niewiele straciłeś 🙂 Następna będzie ciekawsza, obiecuję. A trzy dni to faktycznie nieco za mało – może wydłużę do tygodnia? Pomyślę.
Zauważyłem, że w twoim wzorze: 1-x = 0.8(1-x^2) są dwa x, ale ten po lewej stronie znaku równości to prawdopodobieństwo śmierci kolonii, a ten po prawej stronie to prawdopodobieństwo śmierci jednej bakterii, czyli L<>P.
P.S. Po podstawieniu: (prawy x)= 0,2 otrzymamy (lewy x)=23,2% oraz 1-(lewy x)=76,8%.
X po obu stronach znaku równości oznacza prawdopodobieństwo śmierci całej kolonii, nie pojedynczej bakterii.
Szansa, że pierwsza bakteria podzieli się na dwie wynosi 0.8. Szansa, że te dwie nie wymrą wynosi 1-x^2. A więc po prawej stronie (drugie pokolenie) mamy szansę nie-wymarcia równą 0.8(1-x^2).
Jest to również szansa, że pierwsza bakteria nie wymrze, czyli (1-x).
Rozwiązując 1-x=0.8(1-x^2) dostajemy x=0.25.
Pewnie masz rację, musiałem popełnić błąd gdzieś w poniższym rozumowaniu:
Jeśli (1-x^2) to prawdopodobieństwo przeżycia co najmniej jednej z dwóch bakterii w drugim pokoleniu, to x^2 jest prawdopodobieństwem śmierci tych dwóch bakterii, więc x musi być prawdopodobieństwem śmierci jednej bakterii.