Список заданий по ДМ 2017 весна

<wikitex>

1. Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
2. Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?
3. Чему равна вероятность, что если вытянуть из колоды две случайные карты, одной из них можно побить другую (одна из мастей назначена козырем, картой можно побить другую, если они одинаковой масти или если одна из них козырь)?
4. Чему равна вероятность, что на двадцати брошенных честных монетах выпадет поровну нулей и единиц?
5. Петя и Вася три раза бросают по одной честной игровой кости. Вася два раза выкинул строго больше, чем Петя, а один раз строго меньше. При этом Петя в сумме выкинул строго больше, чем Вася. С какой вероятностью такое могло произойти?
6. Приведите пример трех событий, для которых $P(A \cap B \cap C) = P(A)P(B)P(C)$, но которые не являются независимыми, причем вероятности всех трех событий больше 0
7. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(C) > 0$ выполнено $P(A \cap B|C) = P(A|C)P(B|C)$
8. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(A) > 0$, $P(B) > 0$ выполнено $P(C|A \cap B) = P(C|A)P(C|B)$
9. Рассмотрим множество костей домино (неупорядоченные пары $(i, j)$, где $i$ и $j$ от 0 до 6, всего костей 28). Можно ли вероятностное пространство костей домино представить как прямое произведение вероятностных пространств, каждое из которых имеет более одного элементарного исхода?
10. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $P(A) = P(B)$
11. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $A$ и $B$ независимы
12. Доказать или опровергнуть: если $P(A|C) = P(B|C)$, то $P(C|A) = P(C|B)$
13. Доказать или опровергнуть: если $A$ и $B$ независимы, то $\Omega \setminus A$ и $\Omega \setminus B$ независимы
14. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч интересным, если перед его просмотром он не знает, кто выиграет финал. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 4 интересных матча?
15. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч зрелищным, если перед его просмотром он не знает, кто его выиграет. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 5 зрелищных матчей?
16. Перемножим счетное число вероятностных пространств, соответствующих честным монетам. Что получится? Как бы вы ввели на результате вероятностную меру?
17. Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
18. Найдите распределение и математическое ожидание следующей случайной величины: число бросков честной монеты до второго выпадения 1.
19. Докажите, что если $f$ и $g$ независимы, то для любых $a$ и $b$ события $[f = a]$ и $[g = b]$ независимы
20. Случайные величины f, g и h называются независимыми в совокупности, если для любых a, b и c события [f <= a], [g <= b] и [h <= c] независимы. Приведите пример независимых попарно, но не независимых в совокупности случайных величин
21. Случайные величины f, g и h называются независимыми в совокупности, если для любых a, b и c события [f <= a], [g <= b] и [h <= c] независимы. Приведите пример независимых попарно, но не независимых в совокупности случайных величин, запрещается использовать величины, пропорциональные индикаторным случайным величинам событий
22. Найдите математическое ожидание числа инверсий в перестановке чисел от 1 до $n$
23. Найдите математическое ожидание числа подъемов в перестановке чисел от 1 до $n$
24. Найдите математическое ожидание числа троек $i$, $j$, $k$, где $i < j < k$ и $a[i] < a[j] < a[k]$ в перестановке чисел от 1 до $n$
25. Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
26. Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )"
27. Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )"
28. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
29. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
30. Верно ли, что если $\xi$ и $\eta$ - независимые случайные величины, то таким будут и $f(\xi)$ и $g(\eta)$ для любых функций $f$ и $g$?
31. Постройте случайную величину, имеющую конечное математическое ожидание и бесконечную дисперсию.
32. Постройте случайную величину, имеющую бесконечное математическое ожидание и конечную дисперсию.
33. Оцените вероятность, что значение на игральной кости отличается от матожидания больше чем на 2 с помощью неравенства Чебышева. Насколько точна эта оценка?
34. Докажите, что вероятность того, что значения на двух нечестных игральных костях совпадает, не меньше $1/6$.
35. Найдите дисперсию следующей случайной величины: число бросков честной монеты до первого выпадения 1.
36. Найдите дисперсию следующей случайной величины: число бросков честной монеты до $k$-го выпадения 1.
37. Докажите, что корреляция случайных величин лежит в диапазоне от -1 до 1
38. Докажите или опровергните, что корреляция случайных величин равна 0 тогда и только тогда, когда они независимы
39. Докажите, что корреляция случайных величин равна 1 тогда и только тогда, когда они линейно зависимы $(f = cg)$ и $c > 0$ (если $c < 0$, то корелляция равна -1)
40. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 11. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
41. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
42. Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
43. По аналогии с доказательством на лекции, докажите оценку на отклонение суммы $n$ честных монет от $n/2$ вниз: $P(\xi \le (1-\delta)n/2) \le \exp(-\delta^2/(4n))$.
44. Используйте метод границы Чернова, чтобы следующее. Пусть нечестную монету с вероятностью выпадения 1 равной p бросили $n$ раз. Обозначим случайную величину "число выпавших единиц" как $\xi$. Тогда $P(\xi \le n/2) \le exp(-\frac{1}{2p}n\left(p-\frac{1}{2}\right)^2)$.
45. Как использовать результат из предыдущего задания для проверки, в какую сторону "перекошена" нечестная монета?
46. Сколько байт в бите?
47. Докажите, что для монеты энтропия максимальна в случае честной монеты
48. Докажите, что для n исходов энтропия максимальна если они все равновероятны
49. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
50. Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m P(b_i) \sum\limits_{j = 1}^n P(a_j | b_i) \log P(a_j | b_i))$. Докажите, что $H(A | B) + H(B) = H(B | A) + H(A)$
51. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
52. Что можно сказать про $H(A | A)$?
53. Петя хочет пойти в кино с вероятностью ровно 1/3, а у него есть только честная монета. Может ли он осуществить свой замысел?
54. Петя хочет пойти в кино с вероятностью ровно 1/13, а у него есть только честная монета. Может ли он осуществить свой замысел?
55. Решите предудыщее задание для любой дроби $0 \le p/q \le 1$.
56. Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
57. Докажите, что если у вас есть честная монета, то вы можете получить случайный источник с распределением вероятностей $q_1, \ldots, q_m$ для любых значений $q_i$. Считайте, что вы можете сравнивать $q_i$ с рациональными числами и производить с ними арифметические операции.
58. Докажите, что если у вас есть случайный источник с распределением вероятностей $p_1, \ldots, p_n$, где хотя бы две значения отличны от 0, то вы можете получить случайный источник с распределением вероятностей $q_1, \ldots, q_m$ для любых значений $q_i$.
59. Пусть у вас есть случайный источник с распределением вероятностей $1/n, \ldots, 1/n$ и вы используете его, чтобы получить случайный источник с распределением вероятностей $1/m, ..., 1/m$, где $m > n$. Оцените число экспериментов, которые в среднем необходимы для соответствующей симуляции. Сделайте вывод с точки зрения теории информации.
60. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
61. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
62. Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
63. Предложите решение задачи 41 для произвольных выигрышных строк Васи и Пети (за полином от суммы длин этих строк).
64. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 001. Какую строку длины 3 оптмально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
65. Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
66. Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
67. Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Предложите алгоритм определния, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
68. Постройте регулярную Марковскую цепь с двумя состояниями и эргодическим распределением $[a, 1-a]$ для заданного $a$.
69. Постройте регулярную Марковскую цепь с $n$ состояниями и заданным распределением.
70. В случае, если НОД длин циклов единственного эргодического класса не равен 1, соотвтствующая Марковская цепь будет периодической и эргодического распреления не будет. Можно ли что-нибудь сказать про распределения в моменты с заданным остатком по модулю НОД длин циклов?
71. Пусть $L$ - формальный язык. Обозначим как $L^*$ множество слов, представимых в виде конкатенации 0 или более слов языка $L$. Например, $\{a, bb\}^*$ - слова из $a$ и $b$, в которых любой последовательный блок символов $b$ имеет четную длину. Докажите, что $(L^*)^* = L^*$
72. Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = R^* \cup S^*$.
73. Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cap S)^* = R^* \cap S^*$.
74. Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = (R^*S^*)^*$.
75. Пусть $R$ и $S$ - языки. Обозначим как $RS$ язык слов, представимых в виде конкатенации слова из $R$ и слова из $S$ (в этом порядке). Докажите, что $(R\cup S)T=RT \cup ST$, $(R\cap S)T=RT \cap ST$.
76. Пусть $L$ - язык. Обозначим как $Lc$ язык, который получается из $L$ дописыванием в конец каждому слову символа $c$. Обозначим как $Lc^{-1}$ язык, который получается из $L$ откидыванием всех слов, которые не заканчиваются на $c$, а затем у оставшихся слов откидыванием конечного символа $c$. Докажите или опровергните, что $(Lc)c^{-1}=L$, $(Lc^{-1})c=L$.

</wikitex>