Задача о шпионах за круглым столом
Попалась тут задача, в которой 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} $$
А ещё Евгений Степанищев подтвердил теоретический ответ с помощью моделирования методом
Подключил Akismet для борьбы со спамом
Со временем технологии развивались, и через selenium разработчики автоматизировали действия ботов через полноценные браузеры. Метод защиты с помощью Javascript стал фильтровать только самых тупых ботов.
Затем для борьбы со спамом я включил предарительную проверку комментариев перед публикацией. К этому времени поток комментариев на сайте как раз уменьшился. Немногочисленные нормальные комментарии легко одобрить вручную, особенно когда отвечаешь на них. Тогда же я запрограммировал обход предварительной проверки для залогиненных модераторов — пользователей, которые управляют отображением комментариев.
Чтобы облегчить себе жизнь по окончательному удалению спаммерских комментариев из очереди на модерацию, я задумался над тем, какова цель спаммеров? Конечная цель — разместить ссылки для манипуляции индексом цитирования и для привлечения посетителей. Если запретить оставлять ссылки, спаммерам не будет смысла оставлять комментарии без них. А если ссылку хочет разместить человек в хорошем комментарии, сайт скажет ему, чтобы он удалил http:// из ссылки. Запрет на ссылки принес свои плоды, но
Сейчас я решил посмотреть, как привлечь новые технологии для фильтрации спама. Теоретически можно натренировать нейросеть на
Akismet — это система фильтрации спама в комментариях, разработанная авторами WordPress. В вордпрессе есть плагин, который обращается к API Akismet. Однако сам API открыт и может быть использован любым сайтом, для обращения нужен только лицензионный ключ. Лизензия для некоммерческого использования бесплатная.
Основная особенность Akismet заключается в том, что он используется на множестве сайтов. Таким образом можно быстро выявлять новые
Я подключил сервис и несколько дней его тестировал. По каждому комментарию Akismet возвращает свое решение: либо это хороший комментарий, либо спам, либо «вопиющий» (blatant) спам. В итоге остановился на следующем алгоритме фильтрации комментариев:
- если комментарий хороший, он публикуется сразу;
- если комментарий признан вопиющим спамом, он даже не сохраняется, при попытке его отправить будет возвращено сообщение об ошибке;
- если комментарий спаммерский, он остается скрытым, а уведомление о нем отправляется модераторам;
- если владелец сайта не указал в настройке лицензионный ключ Akismet или если сервис не ответил, комментарий либо публикуется либо остается скрытым в зависимости от того, включен ли режим модерации (откат к старому алгоритму).
После внедрения за две недели пришло 62 комментария. Из них 60 спаммерских комментариев были отсеяны либо как вопиющий спам (21 комментарий), либо как спам с наличием ссылок в тексте. Остальные два комментария опубликованы: один хороший комментарий и один спаммерский со ссылкой на yotube.
Понятно, что у способа есть свои недостатки.