Заметки о задаче «Беговая амёба»

Приводим комментарии члена жюри, который оценивал задачу «Беговая амёба». Напоминаем, что обсуждение критериев оценивания является живым процессом, в котором коллегия отталкивается от опыта и предварительных собственных решений каждой задачи. Критерии принимаются коллегией коллективно и применяются каждым из членов жюри.


Задача сама по себе очень простая — по сути, это просто задача про подкидывание монетки (чего участники, к сожалению, не поняли).

Итак, три подзадачи:
1) Найти распределение вероятностей по расстояниям. Ожидали, что участники сделают и покажут распределения вероятностей для разных значений времени жизни амёбы. Ключевой момент — вероятность умереть в точке с нечетной координатой равна нулю, если время жизни четное, и наоборот.

На гистограмме ширина «корзины» намерено сделанна равной двум, чтобы выглядело приблизительно одинаково, и можно было сравнить. Здесь зеленое — для времени жизни равного 10, желтое — для 100, красное — для 1000, количество итераций — 100к. Гистограмма не нормированная (по вертикальной оси — количество экспериментов из 100к, а не вероятность).

Участники, в своем большинстве, показывали распределение вероятностей демонстрировали только для какого-то одного значения времени жизни (обычно довольно маленького). Некоторые проводили моделирование для разных значений (проверяли соответствующим вопросом и просьбой нарисовать на доске), некоторые это проигнорировали. Огорчило массовое непонимание того, что называют распределением вероятностей, и какие они бывают, даже не гуглили (хотя в условии это словосочетание встречалось 😱). Одна команда, предположила, что распределение вероятностей биномиальное, потому что слово красивое, солидно звучит.

2) Найти среднее расстояние. Хоть в условии четко и не сказано, но ожидалось, что будет какая-то зависимость среднего расстояния от времени жизни амёбы. Даже если посчитать для трёх значений, уже видно, что это корень из времени:

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

3) третья часть задачи состоит из двух подпунктов:

  • вероятность за время \(t\) хотя бы раз пересечь порог \(|x|\);
  • распределение историй жизни по времени первого пересечения финиша.

Удовлетворительного результата никто не получил. Кто-то написал игру, которая выдавала результат вида прошел порог или нет для заданных значений \(t\) и \(x\), но это не решение. Было б лучше, для первой части задачи нужно было зафиксировать какую-то одну переменную (\(t\) или \(x\)), и проводить моделирование по второй переменной. Стоит отметить, что из всех вопросов, этот является наиболее трудозатратным.

Собственное решение, от которого мы в значительной степени отталкивались: построены гистограммы количества жизней, которые понадобились для того, чтобы хоть раз пройти порог, для некоторых значений T и Х:

Время жизни 10, порог 4
Время жизни 100, порог 10
Время жизни 1000, порог 30
Время жизни 1000, порог 100

Отсюда вероятность пройти порог с первого раза (то, что спрашивается в первой части) будет отношением высоты первого столбика гистограммы к сумме высот всех столбиков. Последняя гистограмма наталкивает на мысль, что искомая функция будет вида \(C\exp(x-x_0)\), где \(x_0\) − какое-то пороговое значение функции для определенного времени жизни. Тогда до этого порога она будет выглядеть как монотонно спадающая экспонента (как видно из первых трех гистограмм), в окрестности порога − шум (как на последней гистограмме), больше порога — монотонно возрастающая экспонента (пытались проверить поставив порог \(x = 300\), не посчитало даже количество жизней для одного прохождения порога — откуда сделали вывод, что так оно и есть). Вразумительные результаты показали две команды.

Н. Колосков

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

А. Пилиповский

5 коментар

  1. Интересно, хоть кто-то (физики же! :)) увидел аналогию с диффузией?…

    И – непонятно, что такого страшного в биномиальном распределении? (“Одна команда, предположила, что распределение вероятностей биномиальное, потому что слово красивое, солидно звучит.”) Нормальное распределение, по большому счету, ведь и есть приближение биномиального для большой выборки. Так что тут как раз команда права 🙂

  2. Здравствуйте!

    Позвольте спросить, а что считается полным решением задачи? Наша команда вывела конечные формулы для всех трёх пунктов, доказала и объяснила их. Также сверила с практикой, причём не только со случайным запуском большого количества амёб, но и с программируемым ответом (полученным с помощью динамического программирования). “Одна из команд получила что-то аналитически и проверила моделированием, но демонстрация осталась неубедительной.” — наверное, это про нас. Что ж поделать, я не знаю, как можно убедить людей в истинности какого-либо факта лучше, чем точное доказательство этого факта. Допускаю, конечно, что жюри просто не захотело вникать в наше доказательство и поэтому осталось неудовлетворённым, но не это ли работа жюри — оценить, насколько команда продвинулась к решению задачи?

    Также хотелось бы спросить “о генераторах псевдослучайных чисел: насколько корректно отображает физическую реальность тот или иной генератор, если использовать его для больших наборов данных”. Почти все генераторы случайных чисел основаны на какой-то псевдослучайной формуле. Какой тогда генератор вы использовали для построения своих графиков? Ведь если вы использовали псевдослучайный генератор, то выходные данные могли не отражать действительность.

    И напоследок хотелось бы уточнить, доказывали ли вы полученные зависимости (распределение в п.1, корень из времени в п.2, экспоненциальную зависимость в п.3), или же сделали вывод об ответах, лишь посмотря на графики для разных значений?

    С уважением, члены команды “Люстра и петрушка”.

    1. Я не имею никакого отношения к жюри, но тема очень интересная, так что позвольте вставить свои 5 копеек…
      Нормальное распределение (при больших N), и пропорциональность корню от времени вы бы увидели мгновенно, если бы выполнили поиск по термину “случайное блуждание”, или если бы кто-то провел аналогию с диффузией и ее законами. Наверное, непосредственный вывод этих формул сложноват для школьников, но то, что должно было получиться, в этой задаче можно было легко узнать заранее 🙂 По части третьей не скажу, что-то такие формулы не припоминаются, возможно, здесь нужно было проводить реальный вычислительный эксперимент, а не демонстрационный.

      1. Добавлю свою лепту – получить аналитически формулы для третьей части можно с помощью довольно красивого трюка с отражением траекторий. Эта задача также известна как задача о разорении игрока и в такой формулировке многократно обсуждается в разных учебниках по теории вероятности.

        1. Андрей, спасибо, а не подскажете какой-то URL или конкретную книгу? просто интересно было бы ознакомиться, но как обычно – на интересное, но совершенно не относящееся к работе, времени для поиска не хватает… Хотелось бы что-то, что можно прочесть чуть ли не как научпоп 🙂 – ну, чтоб несколько страниц идей и окончательный вывод. Буду признателен за точную наводку.

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *