Oczekiwana wartość robaka i jabłka

8

Jabłko znajduje się na wierzchołku z pięciokąta , a robak znajduje się dwa wierzchołki z dala, na . Każdego dnia robak czołga się z jednakowym prawdopodobieństwem do jednego z dwóch sąsiadujących wierzchołków. Tak więc po jednym dniu robak znajduje się w wierzchołku lub , każdy z prawdopodobieństwem . Po dwóch dniach robak może wrócić do , ponieważ nie pamięta poprzednich pozycji. Kiedy osiągnie wierzchołek , przestaje jeść. $A$ $ABCDE$ $C$ $B$ $D$ $1/2$ $C$ $A$

(a) Jaka jest średnia liczba dni do kolacji?

(b) Niech p będzie prawdopodobieństwem, że liczba dni wynosi lub więcej. Co mówi nierówność Markowa o ? $100$ $p$

Dla (a) niech będzie zmienną losową zdefiniowaną przez liczbę dni do obiadu. Więc $X$

P. (X = 0) = 0 P. (X = 1) = 0 P. (X = 2)) = \frac{1}{(\binom{5}{2)})} ⋮

$P(X = 0) = 0 \\ P(X=1) = 0 \\ P(X=2) = \frac{1}{\binom{5}{2}} \\ \vdots$

Jaka byłaby ogólna dystrybucja?

Dla (b), jeśli wiemy (a), to wiemy, że

P. (X \geq 100) \leq \frac{mi (X)}{100}

$P(X \geq 100) \leq \frac{E(X)}{100}$

probability markov-process

— probguy3434
źródło

2

Czy mógłbyś wyjaśnić swój pierwszy zestaw równań? Wydaje się, że nie uwzględniają one możliwości zmiany kierunku robaka ani nie wydają się prawidłowe. W końcu jest znacznie mniejsze niż szansa ścieżki która ma prawdopodobieństwo Zauważ, że sedno tego pytania jest takie, że uzyskanie pełnego rozkładu może być trudniejsze niż obliczenie jego oczekiwań; a Nierówność Markowa pozwala jednak wydedukować użyteczne informacje z samego oczekiwania.

1 / (\binom{5}{2}) = 1 / 10

$1/\binom{5}{2}=1/10$

A \to B \to C

$A\to B\to C$

(1 / 2) (1 / 2) = 1 / 4.

$(1/2)(1/2)=1/4.$

— whuber

6

W doskonałej odpowiedzi Glen_b pokazuje, że można obliczyć wartość oczekiwaną analitycznie za pomocą prostego układu równań liniowych. Stosując tę metodę analityczną można ustalić, że oczekiwana liczba ruchów do jabłka wynosi sześć. Inna doskonała odpowiedź Whubera pokazuje, jak uzyskać funkcję masy prawdopodobieństwa dla procesu po dowolnej liczbie ruchów, a tę metodę można również zastosować do uzyskania rozwiązania analitycznego dla oczekiwanej wartości. Jeśli chcesz dowiedzieć się więcej o tym problemie, powinieneś przeczytać kilka artykułów na temat przypadkowych spacerów po okręgu (patrz np. Stephens 1963 )

Aby dać alternatywne spojrzenie na problem, pokażę ci, jak możesz uzyskać ten sam wynik za pomocą metody brutalnej siły, po prostu obliczając łańcuch Markowa za pomocą obliczeń statystycznych. Ta metoda jest gorsza od analizy analitycznej pod wieloma względami, ale ma tę zaletę, że pozwala poradzić sobie z problemem bez konieczności posiadania większego wglądu matematycznego.

Metoda obliczeniowa siły brutalnej: przyjmowanie stanów w kolejności , przejścia łańcucha Markowa zgodnie z następującą macierzą przejścia: $A,B,C,D,E$

P = [\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 \end{matrix}]

$\mathbf{P} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\[6pt] \tfrac{1}{2} & 0 & \tfrac{1}{2} & 0 & 0 \\[6pt] 0 & \tfrac{1}{2} & 0 & \tfrac{1}{2} & 0 \\[6pt] 0 & 0 & \tfrac{1}{2} & 0 & \tfrac{1}{2} \\[6pt] \tfrac{1}{2} & 0 & 0 & \tfrac{1}{2} & 0 \\[6pt] \end{bmatrix}$

Pierwszym stanem jest stan wchłaniania którym robak znajduje się przy jabłku. Niech być liczba ruchów aż robak dostaje jabłko ze stanu . Zatem dla wszystkich prawdopodobieństwo, że robak znajdzie się na jabłku po tej liczbie ruchów, to więc oczekiwana liczba ruchów, aby dostać się do jabłka z tego stanu to: $A$ $T_C$ $C$ $n \in \mathbb{N}$ $\mathbb{P}(T_C \leqslant n) = \{ \mathbf{P}^n \}_{C,A}$

mi ({T.}_{do}) = \sum_{n = 0}^{\infty} P. ({T.}_{do} > n) = \sum_{n = 0}^{\infty} (1 - {{P.}^{n}}_{do, ZA}) .

$\mathbb{E}(T_C) = \sum_{n=0}^\infty \mathbb{P}(T_C > n) = \sum_{n=0}^\infty (1-\{ \mathbf{P}^n \}_{C,A}).$

Pojęcia sumy zmniejszają się wykładniczo dla dużej liczby dzięki czemu możemy obliczyć oczekiwaną wartość do dowolnego pożądanego poziomu dokładności poprzez obcięcie sumy o skończonej liczbie wyrazów. (Gwałtowny rozkład terminów gwarantuje, że możemy ograniczyć rozmiar usuniętych terminów do poziomu poniżej pożądanego poziomu.) W praktyce łatwo jest wziąć dużą liczbę terminów, dopóki rozmiar pozostałych terminów nie będzie wyjątkowo mały. $n$

Programowanie w R: Możesz zaprogramować to jako funkcję przy Rużyciu poniższego kodu. Ten kod został zektoryzowany w celu wygenerowania szeregu mocy macierzy przejściowej dla skończonej sekwencji ruchów. Generujemy również wykres prawdopodobieństwa, że jabłko nie zostało osiągnięte, pokazując, że zmniejsza się on wykładniczo.

#Create function to give n-step transition matrix for n = 1,...,N
#N is the last value of n
PROB <- function(N) { P <- matrix(c(1, 0, 0, 0, 0, 
                                    1/2, 0, 1/2, 0, 0, 
                                    0, 1/2, 0, 1/2, 0,
                                    0, 0, 1/2, 0, 1/2,
                                    1/2, 0, 0, 1/2, 0),
                                  nrow = 5, ncol = 5, 
                                  byrow = TRUE);
                      PPP <- array(0, dim = c(5,5,N));
                      PPP[,,1] <- P;
                      for (n in 2:N) { PPP[,,n] <- PPP[,,n-1] %*% P; } 
                      PPP }

#Calculate probabilities of reaching apple for n = 1,...,100
N  <- 100;
DF <- data.frame(Probability = PROB(N)[3,1,], Moves = 1:N);

#Plot probability of not having reached apple
library(ggplot2);
FIGURE <- ggplot(DF, aes(x = Moves, y = 1-Probability)) +
          geom_point() +
          scale_y_log10(breaks = scales::trans_breaks("log10", function(x) 10^x),
                        labels = scales::trans_format("log10", 
                                 scales::math_format(10^.x))) +
          ggtitle('Probability that worm has not reached apple') +
          xlab('Number of Moves') + ylab('Probability');
FIGURE;

#Calculate expected number of moves to get to apple
#Calculation truncates the infinite sum at N = 100
#We add one to represent the term for n = 0
EXP <- 1 + sum(1-DF$Probability);
EXP;

[1] 6

Jak widać z tego obliczenia, spodziewana liczba ruchów, aby dostać się do jabłka, wynosi sześć. Obliczenia były niezwykle szybkie przy użyciu powyższego wektoryzowanego kodu dla łańcucha Markowa.

— Ben - Przywróć Monikę
źródło

5

Wystarczy zilustrować prosty sposób patrzenia na część (a) bez przechodzenia przez całą procedurę łańcucha Markowa. Istnieją dwie klasy stanów, o które należy się martwić: bycie o krok i bycie o dwa kroki (C i D są identyczne pod względem oczekiwanych kroków, aż do osiągnięcia A, a B i E są identyczne). Niech „ ” reprezentuje liczbę kroków, jakie wykonuje od wierzchołka i tak dalej. $S_B$ $B$

$E(S_C) = 1+\frac12[E(S_B)+E(S_D)] = 1+ \frac12[E(S_B)+E(S_C)]$

Podobnie napisz równanie dla oczekiwania na . $E(S_B)$

drugi na pierwszy (i dla wygody wpisz dla ), a otrzymasz rozwiązanie dla kilku wierszach. $c$ $E(S_C)$ $c$

— Glen_b - Przywróć Monikę
źródło

3

+1. Podoba mi się to, zastępując oczekiwania funkcjami generującymi prawdopodobieństwo, otrzymujesz podobne równanie, równie łatwo rozwiązane, pokazujące, że pgf dla stanu początkowego wynosi i to prowadzi do prostej formuły dla dowolnego prawdopodobieństwa. Lepiej: niech będzie liczbą kroków rozpoczynających się odZdefiniuj iRelacje to iPodstawienie tego drugiego do pierwszego daje dla Zatem jest

t^{2} / (4 - 2 t - t^{2}),

$t^2/(4-2t-t^2),$

X_{y}

$X_y$

y \in {A, B} .

$y\in\{A,B\}.$

f_{n} = 2^{n} Pr (X_{A} = n)

$f_n=2^n\Pr(X_A=n)$

g_{n} = 2^{n} Pr (X_{B} = n) .

$g_n=2^n\Pr(X_B=n).$

f_{n} = f_{n - 1} + g_{n - 1}

$f_n=f_{n-1}+g_{n-1}$

g_{n - 1} = f_{n - 2} .

$g_{n-1}=f_{n-2}.$

f_{n} = f_{n - 1} + f_{n - 2}

$f_n=f_{n-1}+f_{n-2}$

n \geq 3.

$n\ge 3.$

f_{n}

$f_n$

n - 2^{nd}

$n-2^\text{nd}$ Liczba Fibonacciego.

— whuber

@whuber: Powinieneś zamienić swój komentarz w pełną odpowiedź - jest naprawdę dobra.

— Ben - Przywróć Monikę

1

Zgadzam się, warto pisać jako odpowiedź, nawet w tej krótkiej formie.

— Glen_b

3

Problem

Ten łańcuch Markowa ma trzy stany, w zależności od tego, czy robak znajduje się w odległości czy spacji od Niech będzie zmienną losową, podając ile kroków robak podejmie, aby osiągnąć ze stanu Ich funkcje generujące prawdopodobieństwo są wygodnym sposobem algebraicznym do kodowania prawdopodobieństw tych zmiennych. Nie trzeba się martwić o problemy analityczne, takie jak zbieżność: wystarczy spojrzeć na nie jako na formalne serie potęg w symbolu podanym przez $0,$ $1,$ $2$ $C.$ $X_i$ $C$ $i\in\{0,1,2\}.$ $t$

{fa}_{ja} (t) = Par (X_{ja} = 0) + Par (X_{ja} = 1) t^{1} + Par (X_{ja} = 2)) t^{2)} + \dots + Par (X_{ja} = n) t^{n} + \dots

$f_i(t) = \Pr(X_i=0) + \Pr(X_i=1)t^1 + \Pr(X_i=2)t^2 + \cdots + \Pr(X_i=n)t^n + \cdots$

Ponieważ trywialne jest, że Musimy znaleźć $\Pr(X_0=0)=1,$ $f_0(t)=1.$ $f_2.$

Analiza i rozwiązanie

Od stanu ślimak ma równe prawdopodobieństwo poruszających się z powrotem do stanu lub osiągnięcia . Uwzględnienie tego kroku dodaje do wszystkich potęg , równoznacznych z pomnożeniem pgf przez , dając $1,$ $1/2$ $2$ $C$ $1$ $t$ $t$

{fa}_{1} = \frac{1}{2)} t ({fa}_{2)} + {fa}_{0}) .

$f_1 = \frac{1}{2}t\left(f_2 + f_0\right).$

Podobnie, od stanu robak ma równe szanse pozostania w stanie lub osiągnięcia stanu skąd $2$ $2$ $1,$

{fa}_{2)} = \frac{1}{2)} t ({fa}_{2)} + {fa}_{1}) .

$f_2 = \frac{1}{2}t\left(f_2 + f_1\right).$

Pojawienie się sugeruje, że nasza praca zostanie ułatwiona poprzez wprowadzenie zmiennej dając $t/2$ $x=t/2,$

{fa}_{1} (x) = x ({fa}_{2)} (x) + {fa}_{0} (x)); {fa}_{2)} (x) = x ({fa}_{2)} (x) + {fa}_{1} (x)) .

$f_1(x) = x(f_2(x) + f_0(x));\quad f_2(x) = x(f_2(x) + f_1(x)).$

Podstawienie pierwszego do drugiego i przywołanie daje $f_0=1$

$\begin{matrix} (*) & {fa}_{2)} (x) = x ({fa}_{2)} (x) + x ({fa}_{2)} (x) + 1)) \end{matrix}$ $f_2(x) = x(f_2(x) + x(f_2(x) + 1))\tag{*}$

którego unikalnym rozwiązaniem jest

\begin{matrix} (**) & {fa}_{2)} (x) = \frac{x^{2)}}{1 - x - x^{2)}} . \end{matrix}

$f_2(x) = \frac{x^2}{1 - x - x^2}.\tag{**}$

Podkreśliłem równanie aby podkreślić jego podstawową prostotę i formalne podobieństwo do równania, które uzyskalibyśmy, analizując tylko oczekiwane wartości w efekcie, przy takiej samej ilości pracy, jaką zajmuje znalezienie tej jednej liczby, otrzymujemy całą dystrybucję. $(*)$ $E[X_i]:$

Implikacje i uproszczenie

Równolegle, gdy jest wypisywane termin po terminie, a potęgi są dopasowane, to stwierdza, że dla $(*)$ $t$ $n\ge 4,$

{2)}^{n} Par (X_{2)} = n) = {2)}^{n - 1} Par (X_{2)} = n - 1) + {2)}^{n - 2)} Par (X_{2)} = n - 2)) .

$2^n\Pr(X_2=n) = 2^{n-1}\Pr(X_2=n-1) + 2^{n-2}\Pr(X_2=n-2).$

Jest to powtórzenie słynnej sekwencji liczb Fibonacciego

({fa}_{n}) = (1, 1, 2), 3), 5, 8, 13, 21, 34, 55, 89, 144, \dots)

$(F_n) = (1,1,2,3,5,8,13,21,34,55,89,144,\ldots)$

(indeksowane od ). Dopasowaniem rozwiązania jest sekwencja przesunięta o dwa miejsca (ponieważ nie ma prawdopodobieństwa, że lub i łatwo sprawdzić, czy ). $n=0$ $(**)$ $X_2=0$ $X_2=1$ $2^2\Pr(X_2=2)=1=2^3\Pr(X_2=3)$

w konsekwencji

$Par (X_{2)} = n) = {2)}^{- n - 2)} {fa}_{n - 2)} .$ $\Pr(X_2 = n) = 2^{-n-2}F_{n-2}.$

Dokładniej,

\begin{aligned} {fa}_{2)} (t) & = {2)}^{- 2)} {fa}_{0} t^{2)} + {2)}^{- 3)} {fa}_{1} t^{3)} + {2)}^{- 4} {fa}_{2)} t^{4} + \dots \\ = \frac{1}{4} t^{2)} + \frac{1}{8} t^{3)} + \frac{2)}{16} t^{4} + \frac{3)}{32} t^{5} + \frac{5}{64} t^{6} + \frac{8}{128} t^{7} + \frac{13}{256} t^{8} + \dots . \end{aligned}

$\eqalign{ f_2(t) &= 2^{-2}F_0t^2 + 2^{-3}F_1 t^3 + 2^{-4} F_2 t^4 + \cdots \\ &= \frac{1}{4}t^2 + \frac{1}{8}t^3 + \frac{2}{16}t^4 + \frac{3}{32}t^5 + \frac{5}{64}t^6 + \frac{8}{128}t^7 +\frac{13}{256}t^8 + \cdots. }$

Oczekiwanie na można łatwo znaleźć, oceniając pochodną i podstawiając ponieważ (różnicując potęgi termin po termie) daje to wzór $X_2$ $f^\prime$ $t=1,$ $t$

{fa}^{'} (1) = Par (X_{2)} = 0) (0) + Par (X_{2)} = 1) (1) 1^{0} + \dots + Par (X_{2)} = n) (n) 1^{n - 1} + \dots

$f^\prime(1) = \Pr(X_2=0)(0) + \Pr(X_2=1)(1)1^0 + \cdots + \Pr(X_2=n)(n)1^{n-1} + \cdots$

które, jak suma prawdopodobieństw razy wartości właśnie określenie z Biorąc pochodną za pomocą tworzy prosty wzór na oczekiwanie. $X_2,$ $E[X_2].$ $(**)$

Kilka krótkich komentarzy

Rozwijając jako ułamki częściowe, można zapisać jako sumę dwóch szeregów geometrycznych. To natychmiast pokazuje prawdopodobieństwo, że spadnie wykładniczo. Daje również zamkniętą postać prawdopodobieństw ogona Korzystając z tego, możemy szybko obliczyć, że jest nieco mniejszy niż $(**)$ $f_2$ $\Pr(X_2=n)$ $\Pr(X_2 \gt n).$ $\Pr(X_2 \ge 100)$ $10^{-9}.$

Wreszcie, te formuły obejmują Golden Ratio Liczba ta jest długością cięciwy pięciokąta zwykłego (od strony jednostki), co daje uderzające połączenie między czysto kombinatorycznym łańcuchem Markowa na pięciokącie (który „nic nie wie” o geometrii euklidesowej) i geometrią zwykłego pięciokąta w Samolot euklidesowy. $\phi = (1 + \sqrt{5})/2.$

— Whuber
źródło

1

Przez średnią liczbę dni do obiadu, warunek z kroku podjętego pierwszego dnia. Niech będzie liczbą dni, po których robak dostanie jabłko. Niech będzie pierwszym krokiem. $X$ $F$

Potem będzie

mi [X] = mi [X | fa = b] [P. (fa = b)] + mi [X | fa = re] P. [fa = re]

$E[X]=E[X|F=B] \ [P(F=B)]+E[X|F=D] \ P[F=D]$

Jeśli pierwszym krokiem jest wtedy albo robak dostaje jabłko w dniu 2 z prawdopodobieństwem o połowę, albo wraca do wierzchołka z prawdopodobieństwem o połowę i zaczyna od nowa. Możemy to napisać jako $B,$ $C$

mi [X | fa = b] = 2) (\frac{1}{2)}) + (2) + mi [X]) (\frac{1}{2)}) = 2) + \frac{mi [X]}{2)}

$E[X|F=B]=2 \left( \frac{1}{2} \right) + \left(2+E[X] \right) \left( \frac{1}{2} \right)=2+\frac{E[X]}{2}$

Jeśli pierwszym krokiem jest to przez symetrię jest to to samo, co w wierzchołku tyle że robak zrobił jeden krok, więc $D,$ $C$

mi [X | fa = re] = 1 + mi [X]

$E[X|F=D]=1+E[X]$

Łącząc to wszystko, otrzymujemy

mi [X] = (2) + \frac{mi [X]}{2)}) (\frac{1}{2)}) + (1 + mi [X]) (\frac{1}{2)})

$E[X] = \left( 2+\frac{E[X]}{2} \right)\left( \frac{1}{2} \right) + \left( 1 + E[X] \right)\left( \frac{1}{2} \right)$

Rozwiązywanie dla daje $E[X]$

mi [X] = 6

$E[X] = 6$

— soakley
źródło

1

To wydaje się podsumować odpowiedź @ Glen_b.

— whuber