SQL для решения задачек на вероятности
Месяц назад жена с детьми ездила в математический лагерь Жени Кац (janemouse). Особенность матлагеря была в том, что развлекали и учили не только детей, но и их родителей. Каждый день им что-то рассказывали и давали задачки желающим немного поскрипеть мозгами. Какие-то интересные, какие-то не очень. Жена решала все, и едва ли не лучше всех. Физтех. Но я из дома на них тоже посматривал. Уже давно я пользуюсь SQL, если нужно что-то несложное посчитать, и тут попалась задачка на вероятности, которую можно было очень просто решить SQL запросом. Вот такая:
В темном погребе стоит 15 банок с вареньем, 5 с малиновым и 10 с яблочным. Карлсон таскает варенье из погреба, беря каждый раз по одной банке наугад. Его цель -- утащить все малиновое варенье. Какова вероятность того, что когда Карлсон утащит последнюю банку малинового варенья, в погребе не останется никакого варенья вообще?
Задача кажется простой, и инстинктивный ответ 1/3 оказывается правильным. Но если его попытаться обосновать, то начинаются некоторые сложности. Поэтому, чтобы отсечь сомнения, я сделал так.
Закодируем последовательность добывания банок Карлсоном. Так как типов варенья у нас всего два, то можно использовать битовое кодирование: 1 -- малиновое, 0 -- яблочное. Первый бит -- первая утащенная банка, второй бит -- вторая, и т.д. 15 битов -- это 2^15-1 = 32767. Нашим вероятностным пространством будут битовые последовательности, содержащие ровно 5 единиц. Например, 000000000011111. А подмножеством искомых исходов такие числа, где 15й бит -- малиновая банка, то есть единица. Например, 100000000001111. Чтобы не использовать битовые операции можно просто взять числа больше или равные 2^14 = 16384. Получается вот такой коротенький запрос:
SELECT
count() AS all_five_bits,
countIf(number >= 16384) AS last_bit_set,
last_bit_set / all_five_bits AS prob
FROM numbers(32767)
WHERE length(bitmaskToArray(number)) = 5
┌─all_five_bits─┬─last_bit_set─┬───────────────prob─┐
│ 3003 │ 1001 │ 0.3333333333333333 │
└───────────────┴──────────────┴────────────────────┘
Интуиция не подвела.
В темном погребе стоит 15 банок с вареньем, 5 с малиновым и 10 с яблочным. Карлсон таскает варенье из погреба, беря каждый раз по одной банке наугад. Его цель -- утащить все малиновое варенье. Какова вероятность того, что когда Карлсон утащит последнюю банку малинового варенья, в погребе не останется никакого варенья вообще?
Задача кажется простой, и инстинктивный ответ 1/3 оказывается правильным. Но если его попытаться обосновать, то начинаются некоторые сложности. Поэтому, чтобы отсечь сомнения, я сделал так.
Закодируем последовательность добывания банок Карлсоном. Так как типов варенья у нас всего два, то можно использовать битовое кодирование: 1 -- малиновое, 0 -- яблочное. Первый бит -- первая утащенная банка, второй бит -- вторая, и т.д. 15 битов -- это 2^15-1 = 32767. Нашим вероятностным пространством будут битовые последовательности, содержащие ровно 5 единиц. Например, 000000000011111. А подмножеством искомых исходов такие числа, где 15й бит -- малиновая банка, то есть единица. Например, 100000000001111. Чтобы не использовать битовые операции можно просто взять числа больше или равные 2^14 = 16384. Получается вот такой коротенький запрос:
SELECT
count() AS all_five_bits,
countIf(number >= 16384) AS last_bit_set,
last_bit_set / all_five_bits AS prob
FROM numbers(32767)
WHERE length(bitmaskToArray(number)) = 5
┌─all_five_bits─┬─last_bit_set─┬───────────────prob─┐
│ 3003 │ 1001 │ 0.3333333333333333 │
└───────────────┴──────────────┴────────────────────┘
Интуиция не подвела.