Результат: ученик использует Random как явный детерминированный источник состояния, реализует корректные алгоритмы случайного выбора и отделяет доказательство распределения от наблюдений конечной серии.

Содержание:

  1. Понять состояние генератора

    • Random как объект с внутренним состоянием;
    • начальное зерно seed;
    • одинаковая последовательность вызовов;
    • сдвиг всей дальнейшей последовательности после дополнительного вызова;
    • зависимость воспроизводимости от реализации и версии среды.

  2. Использовать целочисленные диапазоны

    • Next();
    • Next(maxValue) и диапазон [0, maxValue);
    • Next(minValue, maxValue) и полуоткрытая верхняя граница;
    • равномерный индекс массива;
    • включительная правая граница через корректное преобразование и проверку переполнения.

  3. Использовать NextDouble

    • исходный диапазон [0, 1);
    • масштабирование в вещественный диапазон;
    • событие Бернулли через сравнение с p;
    • граничные вероятности 0 и 1;
    • влияние машинного округления на преобразованный диапазон.

  4. Управлять источником явно

    • один генератор на логическую последовательность;
    • создание на внешней границе сценария;
    • передача параметром;
    • запрет пересоздания с тем же зерном перед каждым значением;
    • отделение случайного слоя от детерминированного вычислительного ядра.

  5. Обеспечивать воспроизводимость

    • фиксация seed;
    • фиксация версии .NET;
    • фиксация полного порядка обращений;
    • повтор по зерну;
    • повтор по сохранённому массиву случайных входов;
    • различие этих двух гарантий.

  6. Реализовывать базовые случайные операции

    • заполнение массива и таблицы;
    • выбор элемента и координаты;
    • независимое включение каждого элемента;
    • гистограмма категорий;
    • случайное блуждание;
    • детерминированная проверка границ каждого результата.

  7. Реализовывать равномерное перемешивание

    • алгоритм Фишера—Йейтса;
    • выбор индекса из уменьшающегося диапазона;
    • сохранение перестановки;
    • инвариант окончательного суффикса;
    • воспроизводимость;
    • доказательство равномерности.

  8. Выбирать без повторов

    • частичное тасование;
    • ровно k элементов;
    • сохранение или изменение исходного массива;
    • равномерность упорядоченной и неупорядоченной выборки;
    • резервуарная выборка при неизвестной заранее длине потока.

  9. Выполнять взвешенный выбор

    • неотрицательные веса;
    • проверка положительной суммы;
    • накопленные интервалы;
    • нулевой вес;
    • переполнение суммы;
    • доказательство вероятности weight[i] / total.

  10. Строить вероятностный эксперимент

    • пространство элементарных исходов;
    • аналитическая вероятность;
    • независимые серии;
    • гистограмма и частота;
    • среднее, дисперсия и разброс;
    • сопоставление эмпирии с теоретической моделью.

  11. Исследовать классические модели

    • сумма костей;
    • биномиальное распределение;
    • геометрическое ожидание числа попыток;
    • совпадение дней рождения;
    • случайное блуждание;
    • метод Монте-Карло;
    • неподвижные точки перестановки.

  12. Обнаруживать смещение алгоритма

    • операция % при несовместимом размере исходного диапазона;
    • метод отбраковки;
    • наивное тасование;
    • равномерные отдельные частоты без независимости;
    • переходные частоты и длины серий;
    • равномерная точка в геометрической области.

  13. Работать с редкими и тяжёлыми исходами

    • нулевой счётчик редкого события;
    • ожидаемое число наблюдений;
    • вероятность не увидеть событие;
    • цензурированный опыт;
    • коллекционер купонов;
    • нестабильность выборочного среднего при тяжёлом хвосте.

  14. Сравнивать стратегии на общих сценариях

    • заранее сгенерированные одинаковые случайные данные;
    • разность результатов на одной паре сценариев;
    • уменьшение случайного шума;
    • опасность общего генератора при разном числе вызовов;
    • отделение свойства стратегии от расписания генератора.

  15. Использовать вероятностную проверку

    • односторонний алгоритм;
    • отсутствие ложного отказа для правильного результата;
    • вероятность ложного принятия;
    • усиление независимыми раундами;
    • алгоритм Фрейвальдса как пример;
    • явная оценка ошибки 2^{-rounds}.