Playing poohsticks in the Styx

Берём стандартную монету и начинаем её бросать, пока количество выпавших орлов не превысит количество выпавших решек.

Чему равно матожидание доли выпавших орлов?

С вероятностью 1/2, т. е. если сразу выпадет орёл, эта доля равна 100%. С вероятностью 1/8, т. е. если выпадет решка-орёл-орёл, эта доля равна 2/3, и т. д. Я не математик, а программист, поэтому написал простенькую симуляцию и по ней догадался, но если написать программку неправильно, то и догадка будет неправильная.

Прежде чем задавать эту задачку ИИ, попробуйте сами. :)

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

В моём случае более длинный файл - от силы десяток тысяч строк, более короткий - редко когда более тысячи строк, поэтому наивный O(n*m) алгоритм мне бы годился, просто писать было лень. Но я в промпте это не сказал, и получил от Cerebras программу на Питоне, которая пользовалась этим алгоритмом только в качестве крайнего случая, если не был доступен NumPy.

А если NumPy был доступен, то программа каждой уникальной строке, встретившейся в обоих файлах, ставила в соответствие случайное комплексное число длины 1, кроме *, для которой брался 0. Потом она строила соответствующие массивы чисел, удлиняя при необходимости до степени 2, причем для второго массива числа брались сопряжённые, и делала всему этому делу FFT со всеми возможными смещениями от 0 до разницы длин файлов.
В конкретных деталях алгоритма я не разбирался, но мотивировалось это тем, что для совпадающих строк произведение чисел будет равно в точности вещественному 1, а для несовпадающих - произвольным комплексным числам со случайным Re, в среднем равным нулю. Так как нас интересуют только нетривиальные совпадения, то совпадения со звёздочкой, сиречь умножения на 0, общий результат не изменяют.
Потом в массиве полученных результатов находился максимум, и его индекс объявлялся искомым смещением.

Этим всем делом Cerebras был очень горд, потому что вычислительная сложность получалась меньше, типа O((n+m)*log(nm)) или что-то в таком духе.

Ну и, короче, в тех случаях, когда реальное совпадение было стопроцентным, этот алгоритм с хорошей вероятностью выдавал правильное смещение, хотя и с рейтингом заметно меньше 1 (обычно около 0.8-0.9), а для совпадения с погрешностями результат был произвольным и непохожим на реальность. Пришлось подавить это безобразие, закомментировав "import math", и всё заработало ровно так, как я хотел.