Червь и Apple Ожидаемая стоимость

Яблоко расположено в вершине $A$ пятиугольника $ABCDE$ , и червь находится две вершины в стороне, по крайней $C$ . Каждый день червь ползет с равной вероятностью к одной из двух смежных вершин. Таким образом , после того, как один день червь при вершине $B$ или $D$ , каждый из которых с вероятностью $1/2$ . Через два дня червь может снова вернуться в $C$ , потому что у него нет памяти о предыдущих позициях. Когда он достигает вершины $A$ , он прекращает обедать.

а) Какое среднее число дней до обеда?

(b) Пусть p - вероятность того, что количество дней составляет $100$ или более. Что говорит неравенство Маркова о $p$ ?

Для (a) пусть $X$ будет случайной величиной, определяемой количеством дней до обеда. Поэтому

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

Каково будет общее распределение?

Для (б), если мы знаем (а), то мы знаем, что

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

В превосходном ответе Glen_b он показывает, что вы можете рассчитать ожидаемое значение аналитически, используя простую систему линейных уравнений. Следуя этому аналитическому методу, вы можете определить, что ожидаемое количество ходов к яблоку равно шести. Другой отличный ответ от whuber показывает, как получить функцию вероятности для процесса после любого заданного числа ходов, и этот метод также можно использовать для получения аналитического решения для ожидаемого значения. Если вы хотели бы увидеть дальнейшее понимание этой проблемы, вам следует прочитать некоторые статьи о случайных круговых блужданиях (см., Например, Stephens 1963 )

Чтобы дать альтернативное представление о проблеме, я собираюсь показать вам, как вы можете получить тот же результат, используя метод грубой силы, просто вычисляя цепь Маркова с помощью статистических вычислений. Этот метод во многих отношениях уступает аналитическому исследованию, но имеет то преимущество, что он позволяет вам решать проблему, не требуя каких-либо серьезных математических знаний.

---

Метод вычисления методом грубой силы: Принимая состояния в порядке , ваши цепные переходы Маркова переходят в соответствии со следующей матрицей переходов:$A,B,C,D,E$

$$\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}$$

Первое состояние - поглощающее состояние где червь находится у яблока. Пусть будет количество ходов , пока червь не попадает в яблоко из состояния . Тогда для всех вероятность того, что червь окажется у яблока после этого числа ходов, равна и поэтому ожидаемое количество ходов, чтобы добраться до яблока из этого состояния:$A$$T_C$$C$$n \in \mathbb{N}$$\mathbb{P}(T_C \leqslant n) = \{ \mathbf{P}^n \}_{C,A}$

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

Слагаемые в сумме уменьшаются экспоненциально при больших поэтому мы можем вычислить ожидаемое значение с любым желаемым уровнем точности, урезав сумму до конечного числа слагаемых. (Экспоненциальное затухание терминов гарантирует, что мы можем ограничить размер удаленных терминов ниже желаемого уровня.) На практике легко взять большое количество терминов, пока размер оставшихся терминов не станет чрезвычайно маленьким.$n$

---

Программирование этого в R: Вы можете запрограммировать это как функцию, Rиспользуя код ниже. Этот код был векторизован для генерации массива степеней матрицы перехода для конечной последовательности ходов. Мы также генерируем график вероятности того, что яблоко не было достигнуто, показывая, что оно уменьшается в геометрической прогрессии.

#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

Как видно из этого расчета, ожидаемое количество ходов к яблоку составляет шесть. Этот расчет был чрезвычайно быстрым с использованием приведенного выше векторизованного кода для цепи Маркова.

Просто хочу проиллюстрировать простой способ взглянуть на часть (а) без прохождения всей рутинной цепочки Маркова. Есть два класса состояний, о которых нужно беспокоиться: один шаг и два шага (C и D идентичны с точки зрения ожидаемых шагов до достижения A, а B и E идентичны). Пусть « » представляет количество шагов, которое требуется от вершины и так далее.$S_B$$B$

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

Аналогичным образом напишите уравнение для ожидания .$E(S_B)$

Подставьте второе в первое (и для удобства напишите для ), и вы получите решение для в несколько строк.E ( S C ) $c$$E(S_C)$$c$

Проблема

Эта цепь Маркова имеет три состояния, которые различаются тем, находится ли червь на расстоянии или от Пусть - случайная величина, определяющая, сколько шагов червь предпримет для достижения из состояния Их функции, генерирующие вероятности, являются удобным алгебраическим способом кодирования вероятностей этих переменных. Нет необходимости беспокоиться об аналитических вопросах, таких как конвергенция: просто рассматривайте их как формальные степенные ряды в символе заданном$0,$ $1,$$2$$C.$$X_i$$C$$i\in\{0,1,2\}.$$t$

$$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$$

Поскольку тривиально, что Нам нужно найти$\Pr(X_0=0)=1,$$f_0(t)=1.$$f_2.$

Анализ и решение

Из состояния червь имеет равные шансы перемещения обратно в состояние или достижения . Учет одного этого шага добавляет ко всем степеням , равнозначно умножению pgf на , давая$1,$$1/2$$2$$C$$1$$t$$t$

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

Аналогично, из состояния червь имеет равные шансы остаться в состоянии или достичь состояния откуда$2$$2$$1,$

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

Появление говорит о том, что наша работа будет упрощена путем введения переменной давая$t/2$$x=t/2,$

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

Подстановка первого во второе и вызов дает$f_0=1$

$$f_2(x) = x(f_2(x) + x(f_2(x) + 1))\tag{*}$$

чье уникальное решение

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

Я выделил уравнение чтобы подчеркнуть его простоту и формальное сходство с уравнением, которое мы получили бы, анализируя только ожидаемые значения фактически, для того же объема работы, который требуется для нахождения этого единственного числа, мы получаем весь дистрибутив.$(*)$$E[X_i]:$

Последствия и упрощение

Эквивалентно, когда выписывается поэлементно, а степени совпадают, это утверждает, что для$(*)$$t$$n\ge 4,$

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

Это повторение знаменитой последовательности чисел Фибоначчи

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

(индексируется из ). Соответствие решения состоит в том, что эта последовательность сдвинута на два места (потому что нет никакой вероятности, что или и легко проверить, что ).$n=0$$(**)$$X_2=0$$X_2=1$$2^2\Pr(X_2=2)=1=2^3\Pr(X_2=3)$

следовательно

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

Более конкретно,

$$\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. }$$

---

Ожидание легко найти, оценивая производную и подставляя потому что (дифференцируя степени term по терму) это дает формулу$X_2$$f^\prime$$t=1,$$t$

$$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$$

который, как сумма вероятностей раз значение именно определение из Взятие производной с использованием дает простую формулу для ожидания.$X_2,$$E[X_2].$$(**)$

---

Несколько кратких комментариев

Разложив как частичные дроби, можно записать как сумму двух геометрических рядов. Это сразу показывает, что вероятности будут уменьшаться в геометрической прогрессии. Это также дает замкнутую форму для вероятностей хвоста Используя это, мы можем быстро вычислить, что чуть меньше$(**)$$f_2$$\Pr(X_2=n)$$\Pr(X_2 \gt n).$$\Pr(X_2 \ge 100)$$10^{-9}.$

Наконец, эти формулы включают Золотое сечение Это число - длина хорды правильного пятиугольника (со стороны единицы), дающая поразительную связь между чисто комбинаторной цепью Маркова на пятиугольнике (которая «ничего не знает» о евклидовой геометрии) и геометрией правильного пятиугольника в Евклидова плоскость.$\phi = (1 + \sqrt{5})/2.$

Среднее количество дней до обеда - условие шага, сделанного в первый день. Пусть будет количеством дней, пока червь не получит яблоко. Пусть будет первым шагом.$X$$F$

Тогда у нас есть

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

Если первый шаг к то либо червь получает яблоко на 2-й день с вероятностью наполовину, либо он возвращается к вершине с вероятностью наполовину, и он начинает сначала. Мы можем написать это как$B,$$C$

$$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}$$

Если первый шаг к то по симметрии это то же самое, что и в вершине за исключением того, что червь сделал один шаг, так$D,$$C$

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

Собрав все вместе, мы получаем

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

Решение для выходов$E[X]$

$$E[X] = 6$$