?

Log in

No account? Create an account
ushastyi
ushastyi
.............. .... ..........

Links

Июль 2019
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31

ushastyi [userpic]
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 │
└───────────────┴──────────────┴────────────────────┘



Интуиция не подвела.

Comments

Здравствуйте!
Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категориям: IT, Еда.
Если вы считаете, что система ошиблась — напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее.
Фрэнк,
команда ЖЖ.

Не думаю, что задачи по математике съедобны.

Можно считать, что пять банок яблочного варенья из антоновки, пять из ренета, и Карлсон ест вообще всё варенье. Тогда три варианта последней банки - малина, антоновка, ренет, - равновероятны.

Поиграю в адвоката дьявола. Карлсон же не обязан доходить до последней банки. Он же может слопать все малиновое варенье раньше и остановиться.

Так я потому и говорю: "можно считать". Вероятность, о которой спрашивается в задаче, от этого допущения никак не меняется, но становится очевидной симметрия.

Как недавно было у Иванова-Петрова: человеку, у которого в руках микроскоп, всё вокруг кажется гвоздями...
Всё равно же перебор идёт по последовательностям фиксированной длины, и это тривиально, что на пальцах, что на компе. А чуть усложнить условие, учитывать при переборе последовательности разной длины - и SQL отправляется в /dev/null


Edited at 2019-08-01 03:15 (UTC)

Журнал ИП -- кладезь остроумных замечаний. Но тут надо смотреть, какой микроскоп. Если он ClickHouse, то там полноценные лямбды на массивах. Хотя гвозди гвоздями от этого быть не перестанут, конечно.