Amoeba Wywiad Pytanie

25

Zadano mi to pytanie podczas wywiadu dotyczącego pozycji handlowej w firmowej firmie handlowej. Bardzo chciałbym poznać odpowiedź na to pytanie i intuicję.

Amoeba Pytanie: Populacja ameb zaczyna się od 1. Po 1 okresie ameba może podzielić się na 1, 2, 3 lub 0 (może umrzeć) z jednakowym prawdopodobieństwem. Jakie jest prawdopodobieństwo, że cała populacja ostatecznie umrze?

probability

— AME
źródło

czy mamy przypuszczać, że robi to z prawdopodobieństwem ?

1 / 4

$1/4$

— shabbychef

16

z biologicznego punktu widzenia ta szansa wynosi 1. Środowisko zmieni się do punktu, w którym żadna populacja nie będzie w stanie przetrwać, biorąc pod uwagę, że za X miliardów lat słońce eksploduje. Ale chyba nie była to odpowiedź, której szukał. ;-) To pytanie też nie ma sensu. Ameba może podzielić się tylko na 2 lub 0. Morał: handlowcy nie powinni zadawać pytań na temat biologii.

— Joris Meys,

7

Takie pytanie podczas rozmowy o takie stanowisko? Może to coś takiego jak dilbert.com/strips/comic/2003-11-27 ?

1

To słodkie pytanie, jak wspomina Mike. Intuicja tutaj jest taka, że ostateczne prawdopodobieństwo przeżycia / wyginięcia jest takie samo między dwoma pokoleniami. Bardziej kreatywną wersję można by pomyśleć, gdy prawdopodobieństwo przeżycia zmienia się w zależności od liczby obecnych ameb. Dodałem go do mojego bloga witryny.

— brokuły

1

1) Ameba rozmnaża się przez binarne mitozy. 2) Ameba nie rozmnażają się w nienormalnych postaciach mitotycznych, np. W czasach 3, jeśli zaobserwowano by to, byłoby to śmiertelne. 4) Zadawanie pytań podczas rozmowy, które wywołują stronniczość potwierdzeń, jest ogólnie uważane za niskiej jakości. Rada; możesz nie chcieć tej pracy.

— Carl

36

Ładny problem. Tego rodzaju rzeczy probabiliści robią w głowach dla zabawy.

Technika ta polega na założeniu, że istnieje takie prawdopodobieństwo wymarcia nazwać . Następnie, patrząc na jedno-głębokie drzewo decyzyjne dla możliwych wyników, które widzimy - używając Prawa Całkowitego Prawdopodobieństwa - to $P$

$P=\frac{1}{4} + \frac{1}{4}P + \frac{1}{4}P^2 + \frac{1}{4}P^3$

zakładając, że w przypadku 2 lub 3 „potomstwa” prawdopodobieństwo wyginięcia wynosi IID. To równanie ma dwa możliwe pierwiastki, i $1$ . Ktoś mądrzejszy ode mnie może wyjaśnić, dlaczego $\sqrt{2}-1$ $1$ nie jest wiarygodny.

Praca musi być ciasna - jakiego rodzaju ankieter oczekuje, że rozwiążesz równania sześcienne w twojej głowie?

— Mike Anderson
źródło

3

Powód 1 nie jest pierwiastkiem jest łatwo widoczne, uznając oczekiwaną liczbę Amoeba po

krokach nazwać

. Można łatwo pokazać, że

. Ponieważ prawdopodobieństwo dla każdego wyniku jest

mamy

, a więc

rośnie bez ograniczenia w

. To wyraźnie nie ma znaczenia przy

.

k

$k$

E_{k}

$E_k$

E_{k} = E_{1}^{k}

$E_k = E_1^k$

1 / 4,

$1/4,$

E_{1} = 3 / 2

$E_1 = 3/2$

E_{k}

$E_k$

k

$k$

P = 1

$P = 1$

— shabbychef

9

@shabbychef Nie jest to dla mnie takie oczywiste. Możesz sprawić, że oczekiwania rosną wykładniczo (lub nawet szybciej), podczas gdy prawdopodobieństwo wymarcia wciąż zbliża się do jedności. (Na przykład rozważmy stochastyczny proces, w którym populacja albo czterokrotnie w każdym pokoleniu, albo całkowicie wymiera, każde z równymi szansami. Oczekiwanie na pokolenie n wynosi 2 ^ n, ale prawdopodobieństwo wyginięcia wynosi 1.) Zatem nie ma nieodłącznego sprzeczność; twój argument wymaga czegoś dodatkowego.

— whuber

1

@shabbychef - dzięki za edycję. Nie zdawałem sobie sprawy, że możemy użyć wbudowanego TeXa do matematyki! @ whuber - stwierdzenie shabbychef

jest tylko odmianą mojego stwierdzenia o prawdopodobieństwie wyginięcia, po prostu dodaj oczekiwania zamiast mnożenia prawdopodobieństwa. Dobra robota, shab.

E_{k} = E_{1}^{k}

$E_k = E_1^k$

— Mike Anderson,

1

To jasne, Mike, ale o co ci chodzi? Czy nie mówimy o tym, jak wykluczyć 1 jako rozwiązanie? Nawiasem mówiąc, jest oczywiste (poprzez inspekcję i / lub zrozumienie problemu), że 1 będzie rozwiązaniem. To redukuje go do równania kwadratowego, które można łatwo rozwiązać na miejscu. Jednak zwykle nie o to chodzi w pytaniu na rozmowę kwalifikacyjną. Pytający prawdopodobnie bada, co wnioskodawca aktywnie wie o procesach stochastycznych, ruchu Browna, rachunku Ito itp. Oraz o tym, jak sobie radzą z rozwiązywaniem problemów, a nie czy potrafią rozwiązać to konkretne pytanie.

— whuber

3

@shabbychef: Jednym ze sposobów wykluczenia P = 1 jest zbadanie ewolucji funkcji generującej prawdopodobieństwo. Pgf uzyskuje się zaczynając od t (reprezentując początkową populację 1) i iteracyjnie zastępując t przez (1 + t + t ^ 2 + t ^ 3) / 4. Dla dowolnej wartości początkowej t mniejszej niż 1 grafika łatwo pokazuje, że iteracje są zbieżne do Sqrt (2) -1. W szczególności pgf trzyma się z dala od 1, pokazując, że nie może zbiegać się wszędzie w 1, co oznaczałoby całkowite wyginięcie. Właśnie dlatego „1 nie jest prawdopodobne”.

— whuber

21

Niektóre obliczenia koperty (dosłownie - miałem kopertę leżącą na biurku) dają prawdopodobieństwo 42/111 (38%), że nigdy nie osiągnę populacji 3.

Przeprowadziłem szybką symulację Pythona, sprawdzając, ile populacji wymarło przez 20 pokoleń (w tym momencie zwykle albo wymarły albo są w tysiącach), i zabiłem 4164 z 10000 uruchomień.

Tak więc odpowiedź wynosi 42%.

— Emile
źródło

9

to 0,4142, więc zgadza się z analitycznym wynikiem Mike'a. I +1, ponieważ lubię symulacje ;-)

\sqrt{2} - 1

$\sqrt{2}-1$

2

Również +1, ponieważ lubię symulacje. To byłaby moja odpowiedź;).

— Fomite

7

To dźwięki związane z procesem Galtona Watsona , pierwotnie sformułowanym w celu zbadania przetrwania nazwisk. Prawdopodobieństwo zależy od oczekiwanej liczby subamboów po pojedynczym podziale. W tym przypadku, oczekiwana liczba jest która jest większa od wartości krytycznej , a tym samym prawdopodobieństwo ugaszenia pożaru jest mniejszy niż . $3/2,$ $1$ $1$

Uwzględniając oczekiwaną liczbę ameb po podzieleniu , można łatwo wykazać, że jeśli oczekiwana liczba po jednym podziale jest mniejsza niż , prawdopodobieństwo wyginięcia wynosi . Druga połowa problemu nie jest tego taka pewna. $k$ $1$ $1$

— shabbychef
źródło

6

Podobnie jak odpowiedź Mike'a Andersona mówi, że możesz zrównać prawdopodobieństwo wyginięcia linii ameby z sumą prawdopodobieństwa wyginięcia linii potomnej.

p_{p a r e n t} = \frac{1}{4} p_{c h i l d}^{3} + \frac{1}{4} p_{c h i l d}^{2} + \frac{1}{4} p_{c h i l d} + \frac{1}{4}

$p_{parent} = \frac{1}{4} p_{child}^3 + \frac{1}{4} p_{child}^2 + \frac{1}{4} p_{child} + \frac{1}{4}$

Następnie, gdy ustalisz równe prawdopodobieństwo wyginięcia ich linii przez rodziców i dzieci, otrzymasz równanie:

p = \frac{1}{4} p^{3} + \frac{1}{4} p^{2} + \frac{1}{4} p + \frac{1}{4}

$p = \frac{1}{4} p^3 + \frac{1}{4} p^2 + \frac{1}{4} p + \frac{1}{4}$

który ma pierwiastki $p=1$ , $p=\sqrt{2}-1$ , a $p=-\sqrt{2}-1$ .

Pozostaje pytanie, dlaczego odpowiedź powinna brzmieć $p=\sqrt{2}-1$ a nie $p=1$ . Jest to na przykład zadawane w tym zduplikowanympytaniu podczas wywiadu z amebą: Czy P (N = 0) 1 czy 1/2? . Wodpowiedzi z shabbychefwyjaśnione jest, że można patrzeć, $E_k$ , oczekiwaną wartością wielkości populacji po sobie $k$ -tego devision i zobaczyć, czy to jest albo kurczy się lub rośnie.

Dla mnie jest w tym argumentacja pośrednia i wydaje się, że nie jest to do końca udowodnione.

Na przykład w jednym z komentarzy Whuber zauważa, że można mieć rosnącą wartość oczekiwana $E_k$ , a także mają na prawdopodobieństwo wymarcia w $k$ etapie podejścia -tej 1. Jako przykład można przedstawić katastrofalne wydarzenie, które ociera się całego ameba populacji i występuje z pewnym prawdopodobieństwem $x$ na każdym etapie. Wtedy rodowód ameby prawie na pewno umrze. Jednak oczekiwania dotyczące wielkości populacji w kroku $k$ rosną.
Ponadto liście odpowiedź otworzyć co mamy myśleć o sytuacji, gdy $E_k = 1$ (na przykład, gdy an dzieli Amoeba lub nie dzieli z równym, 50% prawdopodobieństwem, to ród ameby staje wymarły z prawdopodobieństwem niemal $1$ eventhough $E_k= 1$ )

Alternatywne pochodne.

Zauważ, że rozwiązanie $p=1$ może być pustą prawdą . Porównujemy prawdopodobieństwo wyginięcia linii rodzica z linią dziecka.

Jeżeli „prawdopodobieństwo wyginięcia rodu dziecka jest równe $1$ ”.
Wtedy „prawdopodobieństwo wyginięcia linii rodzica jest równe $1$ ”.

Ale to nie nie oznacza, że jest prawdą, że „prawdopodobieństwo dla linii dziecka do wyginąć jest $1$ ”. Jest to szczególnie wyraźne, gdy zawsze będzie niezerowa liczba potomstwa. Np. Wyobraź sobie równanie:

p = \frac{1}{3} p^{3} + \frac{1}{3} p^{2} + \frac{1}{3} p

$p = \frac{1}{3} p^3 + \frac{1}{3} p^2 + \frac{1}{3} p$

Czy moglibyśmy znaleźć rozwiązanie w nieco inny sposób?

$p_k$ $k$

p_{1} = \frac{1}{4}

$p_1 = \frac{1}{4}$

i relacja powtarzalności

p_{k + 1} = \frac{1}{4} p_{k}^{3} + \frac{1}{4} p_{k}^{2} + \frac{1}{4} p_{k} + p_{1}

$p_{k+1} = \frac{1}{4} p_{k}^3 + \frac{1}{4} p_k^2 + \frac{1}{4} p_k + p_1$

lub

δ_{k} = p_{k + 1} - p_{k} = \frac{1}{4} p_{k}^{3} + \frac{1}{4} p_{k}^{2} - \frac{3}{4} p_{k} + p_{1} = f (p_{k})

$\delta_k = p_{k+1} - p_k = \frac{1}{4} p_{k}^3 + \frac{1}{4} p_k^2 - \frac{3}{4} p_k + p_1 = f(p_k)$

$f(p_k)>1$ $k$ $k$

Konwergencja do pierwiastka i związek z wartością oczekiwaną

$f(p_k) < p_{\infty}-p_k$ $p_k$ $k$ $f(p_\infty) = 0$

$f(p_k)$ $-1$ $0\leq p \leq 1$ $f(p) = -p + \sum_{k=0}^{\infty} a_k p^k$ $a_k \geq 0$ .

f^{'} (p) = - 1 + \sum_{k = 1}^{\infty} a_{k} k p^{k - 1}

$f^\prime(p) = -1 + \sum_{k=1}^{\infty} a_k k p^{k-1}$

f^{'} (0) = - 1

$f^\prime(0) = -1$

f^{'} (1) = - 1 + E_{1}

$f^\prime(1) = -1 + E_1$

p = 0

$p=0$

p = 1

$p=1$

E_{1} > 1

$E_1>1$

0

$0$

1

$1$

E_{1} \leq 1

$E_1 \leq 1$

0

$0$

1

$1$

f (p) = 0

$f(p) = 0$

a_{1} = 1

$a_1 = 1$

— Sextus Empiricus
źródło