Задача о шпионах за круглым столом

Попалась тут задача, в которой ChatGPT меня обошел. Я хотел придумать какой-нибудь способ упростить рассуждения и сделать решение наглядным, но потом сдался, а ChatGPT решил задачу тупо в лоб. Сначала посмотрим на отредактированное решение, а потом я расскажу, почему его проглядел.

Условие

На банкете за круглым столом сидят $$n$$ шпионов. Каждый шпион независимо от остальных случайным образом выбирает одного из двух соседей — левого или правого — и подсыпает яд ему в бокал. Каково математическое ожидание числа выживших шпионов?

$$\usetikzlibrary{arrows.meta} \begin{tikzpicture}[scale=1.4] \tikzset{spy/.style={circle,draw,minimum size=6mm,inner sep=1pt}} \foreach \i [evaluate=\i as \angle using 360/8*(\i-1)] in {1,...,8} { \node[circle, minimum size=6mm, inner sep=1pt] (spy\i) at (\angle:1.5); \coordinate (below\i) at (\angle:1.1); } \foreach \a/\b in {1/2, 2/1, 3/4, 4/5, 5/4, 6/7, 7/6, 8/1} { \draw[-{Stealth[length=1.6mm]}] (spy\a) to[bend right=15] (spy\b); } \foreach \i in {3,8} { \node[spy,green!40!black,fill=green!10!white] at (spy\i) {\i}; \node[green!60!black] at (below\i) {$\checkmark$}; } \foreach \i in {1,2,4,5,7,6} { \node[spy, red!50!black,fill=red!10!white] at (spy\i) {\i}; \node[red!80!black] at (below\i) {$\dagger$}; } \end{tikzpicture} $$

Говоря простыми словами, нам надо найти среднюю долю выживших при многократном повторении эксперимента.

Решение

Пусть шпионы пронумерованы по кругу числами от 1 до $$n$$ (шпион $$n$$ считается соседом шпиона 1). Обозначим через $$X$$ количество выживших шпионов. Требуется найти математическое ожидание $$\mathbb{E}[X]$$.

Рассмотрим судьбу одного конкретного шпиона, скажем, с номером $$i$$. Он погибает в том и только в том случае, если хотя бы один из соседей выбрал его целью. Таким образом, шпион $$i$$ выживает, если и шпион $$i-1$$, и шпион $$i+1$$ выбрали не его. Поскольку выбор жертв происходит независимо, и каждый выбирает левого или правого соседа с вероятностью 1/2, вероятность того, что оба соседа шпиона $$i$$ выбрали другого соседа, равна:

$$ \mathbb{P}(\text{шпион }i\text{ выживает})=\left(\frac{1}{2}\right)^2=\frac{1}{4}. $$

Введем индикаторную случайную величину $$X_i$$, равную 1, если шпион $$i$$ выживает, и 0 в противном случае. Тогда общее число выживших:

$$X=\sum_{i=1}^n X_i.$$

Так как все шпионы находятся в равных условиях, математическое ожидание $$\mathbb{E}[X_i]$$ одинаково для всех и вычисляется по определению:

$$\mathbb{E}[X_i]=0\cdot\mathbb{P}(\text{шпион }i\text{ умирает})+1\cdot\mathbb{P}(\text{шпион } i \text{ выживает})={1\over4}.$$

Следовательно, по линейности математического ожидания:

$$\mathbb{E}[X]=\sum_{i=1}^n\mathbb{E}[X_i]=n\cdot\frac{1}{4}=\frac{n}{4}.$$

Таким образом, в среднем выживает четверть шпионов, независимо от их числа.

Обсуждение решения и ошибок

ChatGPT получил правильную формулу только для $$n>2$$. Если $$n=2$$, то ответ $$n/4=1/2$$ неправильный, так как в этом случае сосед слева и справа — один и тот же человек, и оба шпиона отравят друг друга. И для $$n=1$$ ответ тоже неприменим.

Самый неочевидный шаг в этом решении — переход от $$\mathbb{E}[X]$$ к $$\mathbb{E}[X_1]+\mathbb{E}[X_2]+\ldots+\mathbb{E}[X_n]$$. Если бы случайные величины $$X_i$$ были независимы, например, как результаты многократного подбрасывания монеты, никого бы не удивило математическое ожидание количества орлов, равное $$n/2$$. Но в нашем случае $$X_i$$ зависимы друг от друга. Так, если шпион $$i$$ выжил, то его соседи $$i\pm1$$ точно выбрали своими жертвами шпионов $$i\pm2$$, сидящих через одного от $$i$$, и они гарантированно не выжили. Не повлияют ли такие взаимосвязи на среднее количество выживших?

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

Пространство элементарных событий и математическое ожидание суммы случайных величин

В задачах, подобных рассмотренной, бывает удобно ввести так называемое пространство элементарных событий $$\Omega$$ — множество всех возможных непересекающихся исходов $$\omega_k$$. Например, в качестве элементарных событий в нашей задаче удобно взять совокупность принятых решений каждым шпионом. Чтобы закодировать элементарное событие, будем выписывать по порядку цифры 0 или 1: 0, если очередной шпион выбрал жертвой соседа слева, и 1 — если справа. Таким образом, каждая последовательность из $$n$$ нулей и единиц соответствует некоторому исходу, то есть некоторому элементарному событию, и наоборот, для каждого исхода можно указать соответствующую последовательность нулей и единиц.

В простых случаях можно перечислить все элементарные события и их вероятности. Например, вот все возможные исходы в нашей задаче:

$$\begin{align*} \omega_0&=000\ldots000,\\ \omega_1&=000\ldots001,\\ \omega_2&=000\ldots010,\\ \omega_3&=000\ldots011,\\ &\ldots\\ \omega_{2^n-2}&=111\ldots110,\\ \omega_{2^n-1}&=111\ldots111.\\ \end{align*}$$

Все они равновероятны, поэтому вероятность каждого исхода $$P(\omega_k)=1/{2^n}$$.

Нам осталось понять, какой смысл имеет понятие случайной величины $$X$$ с точки зрения элементарных событий. Для каждого элементарного события случайная величина $$X$$ имеет вполне определенное значение, то есть это обычная функция от $$\omega_k$$. Рассмотрим для примера случайную величину $$X_2$$ из нашей задачи, которая равна 1, если второй шпион выжил, и 0 в противном случае.

$$ \begin{tikzpicture}[scale=1.4] \tikzset{spy/.style={circle,draw,minimum size=6mm,inner sep=1pt}} \foreach \i [evaluate=\i as \angle using 360/8*(\i-1)] in {1,...,8} { \node[circle, minimum size=6mm, inner sep=1pt] (spy\i) at (\angle:1.5); \coordinate (below\i) at (\angle:1.1); } \foreach \a/\b in {3/4, 2/3, 1/8, 4/3, 8/1} { \draw[->] (spy\a) to[bend right=15] (spy\b); } \foreach \i in {2} { \node[spy,green!40!black,fill=green!10!white] at (spy\i) {\i}; \node[] at (below\i) {$a$}; } \node[] at (below1) {$0$}; \node[] at (below3) {$1$}; \node[] at (below4) {$b$}; \foreach \i in {1,3,4,8} { \node[spy, red!50!black,fill=red!10!white] at (spy\i) {\i}; } \node at(2.4,1.05) {$X_2(1a0b...)=1$}; \end{tikzpicture} $$

Так как на второго шпиона влияют только первый и третий шпионы, то значение $$X_2$$ определяется цифрами на первом и третьем месте, а именно $$X_2(0a1b...)=1$$, $$X_2(0a0b...)=X_2(1a0b...)=X_2(1a1b...)=0$$.

Определение математического ожидания случайной величины состоит в том, что это обычное усредение её значения на элементарных событиях с весом, равным вероятности события. Воспользуемся этими знаниями для вычисления математического ожидания суммы элементарных событий:

$$\begin{align*} \mathbb{E}[X]&=\sum_{k=0}^{2^n}X(\omega_k)P(\omega_k)=\sum_{k=0}^{2^n}\left[X_1(\omega_k)+X_2(\omega_k)+\ldots+X_n(\omega_k)\right]P(\omega_k)=\\ &=\sum_{k=0}^{2^n}X_1(\omega_k)P(\omega_k)+\sum_{k=0}^{2^n}X_2(\omega_k)P(\omega_k)+\ldots+\sum_{k=0}^{2^n}X_n(\omega_k)P(\omega_k)=\\ &=\mathbb{E}[X_1]+\mathbb{E}[X_2]+\ldots+\mathbb{E}[X_n]. \end{align*}$$

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

Дополнение

Выпишем ответ в явном виде для торопящихся читателей:

$$\mathbb{E}[X]=\begin{cases} 1&\text{при }n=1,\\ 0&\text{при }n=2,\\ \frac{n}{4}&\text{при }n>2. \end{cases} $$

А ещё Евгений Степанищев подтвердил теоретический ответ с помощью моделирования методом Монте-Карло на языке R.