Список заданий по продвинутым алгоритмам 2022 осень

1. Задания с 1 по 12 только для магистратуры. Бакалавриат пока отдыхает. Используя формулу Стирлинга $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ оцените, чему равна вероятность, что на $2n$ брошенных честных монетах выпадет поровну нулей и единиц. Найдите асимптотическое поведение при $n \to \infty$
2. Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
3. 10 шаров раскладываются по 5 корзинам. Для каждого шара равновероятно выбирается, в какую корзину он помещается. Какое математическое ожидание числа пустах корзин? Числа корзин, содержащих ровно один шар?
4. Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
5. Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )""
6. Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 8, а затем к получившейся перестановке верный алгоритм из задания 7. Будет ли полученное распределение на перестановках равномерным? Применим верный алгоритм из задания 7, а затем к получившейся перестановке алгоритм из задания 8. Будет ли полученное распределение на перестановках равномерным?
7. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
8. Улучшить неравенство Маркова в общем случае нельзя. Докажите, что для любого $c > 1$ найдется такая неотрицательная случайная величина $\xi$, что $P(\xi \ge cE\xi) = 1/c$.
9. Можно ли подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = 1/c_i$ ($i \in \{1, 2\}$)?
10. Для какого максимального $\alpha$ можно подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = \alpha/c_i$ ($i \in \{1, 2\}$)?
11. Улучшить неравенство Чебышева в общем случае нельзя. Докажите, что для любого $c > 0$ найдется такая отличная от константы случайная величина $\xi$, что $P(|\xi - E\xi| \ge c) = D\xi/c^2$.
12. Улучшить неравенство Чебышева нельзя даже для суммы. Докажите, что для любого $c > 0$ найдется такое семейство одинаково распределенных отличных от константы случайных величин $\xi_1, \xi_2, \ldots, \xi_n$, что $P(|\sum\xi_i - \sum E\xi_i| \ge c) = nD\xi/c^2$.