Конспект: вероятностный анализ и матожидание

Понятия

Исход - один полностью описанный результат опыта; событие - множество исходов; вероятность при равновозможных исходах - доля исходов события.

Независимые события - знание об одном не меняет вероятности другого: P(A и B) = P(A) · P(B).

Условная вероятность P(A | B) = P(A и B) / P(B) - доля A среди исходов B.

Случайная величина - число, зависящее от исхода. Матожидание E[X] = Σ x · P(X = x) - среднее многих повторов.

Индикатор события - величина 1 или 0; его ожидание равно вероятности события.

Геометрическое распределение - номер попытки с первым успехом: P(X = k) = (1 − p)ᵏ⁻¹ · p.

Что унести

ПРАВИЛА СЧЁТА                                       ЧТО НУЖНО
P(не A) = 1 − P(A)                                  ничего
P(A или B) = P(A) + P(B) − P(A и B)                 ничего
P(A₁ или … или Aₙ) ≤ P(A₁) + … + P(Aₙ)              ничего: оценка объединения
P(A и B) = P(A) · P(B)                              независимость
«хотя бы раз» = 1 − P(ни разу)                      независимость - для произведения внутри

два кубика: сумма 7 - 6/36;  хотя бы одна шестёрка - 11/36, не 12/36
20 серверов по 0,01:  точно 0,1821 при независимости,  оценка объединения 0,2 - всегда

ОЖИДАНИЕ                                            ЧТО НУЖНО
E[X + Y] = E[X] + E[Y],  E[cX] = c · E[X]           ничего: линейность
E[X · Y] = E[X] · E[Y]                              независимость (иначе обычно неверно)
E[число случившихся событий] = сумма вероятностей   ничего: индикаторы
P(X ≥ 1) ≤ E[X] для счётчика X                      ничего

кубик 3,5;  min и max двух кубиков: 2,53 + 4,47 = 7,  а E[min · max] = 12,25 ≠ 11,30

МЕТОД ИНДИКАТОРОВ
1. что считает счётчик     2. события: по элементу, по паре, по шагу
3. вероятность одного - обычно из симметрии               4. сложить

ОЖИДАНИЕ УСПЕХА, вероятность p, попытки независимы
E = 1 + (1 − p) · E   →   E = 1/p            шестёрка: 6 бросков
P(ждать дольше k) = (1 − p)ᵏ                 дольше 12 бросков: 11%;  дольше 18: 3,8%
открытая адресация, случайные пробы, неудачный поиск: 1 / (1 − α)    α = 0,5 → 2;  α = 0,9 → 10

КУПОНЫ, n равновероятных вариантов
этап «собрано i»: ждать n / (n − i)          всего n · Hₙ ≈ n · ln n;   n = 50 → 225
половина коллекции - 34 попытки, последние пять вариантов - 114
n попыток на n вариантов задевают только 63% вариантов

ШАРЫ И КОРЗИНЫ, n в n                        n = 20 000, замер
доля корзин с k шарами ≈ 1 / (e · k!)        0,370  0,364  0,185  …   пустых 7403
самая полная: k! ≈ n / e,  Θ(ln n / ln ln n)          7
два выбора: ln ln n / ln 2 + O(1)                     3;   βᵢ₊₁ ≲ βᵢ²
d выборов: ln ln n / ln d + O(1) - дальше только множитель

КУКУШКИНО ХЕШИРОВАНИЕ
ключ k лежит в t1[h1(k)] или в t2[h2(k)]     поиск и удаление: две пробы в худшем случае
вставка: занять ячейку, выселенного - на его второе место, до пустой ячейки или до предела
случайные хеши, доля ≤ 1/2 − ε: P(успех) → 1 при росте n
порог 50% асимптотический; неудача возможна и ниже порога
ячейка на 4 ключа: порог 98%;   три функции: 91%;   предел исчерпан - новые функции и перестройка

Модуль random в тренажёре. random.seed(число) - зерно, после него числа повторяются от запуска к запуску и совпадают с настоящим Python. random.randint(a, b) - целое от a до b включительно, random.randrange(n) - от 0 до n − 1, random.random() - дробное от 0 до 1, random.shuffle(список) - перемешать на месте, random.choice(список) - случайный элемент.

Генератор: зерно и состояние обеспечивают повторимость, период ограничен числом состояний; для секретов нужен криптографический источник, а остаток от диапазона может давать смещение.

Пуассон: один ящик при m/n=λ приближённо имеет P(X=k)=e⁻λ·λᵏ/k!; пустых ожидается точно n(1−1/n)ᵐ. При m=n максимум имеет порядок log n/log log n с вероятностью, стремящейся к единице при росте n.

Йенсен: выпуклая f даёт f(E[X]) ≤ E[f(X)]; для вогнутой знак обратный. Квадратичная цена среднего не учитывает добавку дисперсии.

Ловушки джокера

Сложил вероятности пересекающихся событий. 1/6 + 1/6 для «хотя бы одной шестёрки» считает исход (6, 6) дважды; на семи кубиках такая сумма больше единицы.

Перемножил зависимое. Два диска из одной партии отказывают вместе чаще, чем p². Перед умножением - вопрос, что у событий общего.

Принял ожидаемое число за вероятность. 0,69 ожидаемых совпадений - не 69% шансов на совпадение. Счётчик даёт только оценку сверху.

Принял ожидание за гарантию. Средние 20 мс не мешают одному запросу из ста занимать две секунды.

Подставил среднее в формулу. E[X²] не равно E[X]²: у кубика 15,17 против 12,25.

Решил, что у попыток есть память. После десяти неудач впереди те же 1/p попыток.

Заполнил кукушкину таблицу на 70%. При двух функциях и одном ключе в ячейке порог - половина.

Проверь себя

Почему линейность ожидания не требует независимости? Откуда в числе обновлений максимума логарифм? Почему последние пять купонов из пятидесяти стоят половину всего времени? Почему второй случайный выбор меняет порядок роста, а третий - нет? Чем кукушкина таблица платит за две пробы?