На мой взгляд, стохастические исчисления — это один из тех великолепных разделов высшей математики (наряду с топологией и комплексным анализом), где формулы встречаются с поэзией; это место, где они обретают красоту, место где начинается простор для художественного творчества. Многие из тех, что прочли статью Винеровский хаос или Еще один способ подбросить монетку, даже если и мало, что поняли, всё же смогли оценить великолепие этой теории. Сегодня мы с вами продолжим наше математическое путешествие, мы погрузимся в мир случайных процессов, нетривиального интегрирования, финансовой математики и даже немного коснемся функционального программирования. Предупреждаю, держите наготове свои извилины, так как разговор у нас предстоит серьезный.

Теория вероятности никогда не переставала меня удивлять, начиная ещё с того момента, как я впервые с ней столкнулся, и до сих пор. В разное время в разной степени меня настигали, назовём их «вау-эффекты», шоковые удары в мозжечок, от которых меня накрывало эффектом третьего ока, и мир навсегда переставал быть прежним.

• Первый «вау-эффект» я испытал от Центральной предельной теоремы. Берем кучу случайных величин, устремляем их количество в бесконечность и получаем нормальное распределение. И совсем неважно как распределены эти величины, неважно, будь это подбрасывания монетки или капли дождя на стекле, вспышки на Солнце или остатки кофейной гущи, результат будет всегда один — их сумма всегда стремится к нормальности. Разве что, нужно потребовать их независимость и существование дисперсии (позднее я узнал, что существует теорема и для экстремальных тяжелохвостых распределений с бесконечной дисперсией). Тогда этот парадокс долго не давал мне заснуть.
• В какой-то момент учебы в университете такие предметы как дискретная математика и функциональный анализ слились вместе и всплыли в теорвере под видом выражения «почти наверное». Стандартный пример: вы случайно выбираете число от 0 до 1. С какой вероятностью вы ткнёте в рациональное число (привет, функция Дирихле)? Спойлер: 0. Ноль, Карл! Бесконечное множество не имеет никакой силы, если оно счетно. У вас бесконечное число вариантов, но вы не выберете ни один из них. Вы не выберете 0, или 1, или 1/2, или 1/4. Вы и не выберете 3/2.
  
  Да-да, что выбрать 1/2, что выбрать 3/2, вероятность нулевая. Вот только в 3/2 вы не ткнёте точно, таковы условия, а в 1/2 вы не попадёте ну… «почти наверное». Концепция «почти всюду»/«почти наверное» забавляет математика, а обывателя заставляет крутить пальцем у виска. Многие ломают себе мозг в попытке классифицировать нули, но результат того стоит.
• Третий по счёту, но не по силе, «вау-эффект» настиг уже на переходе в advanced level
  

Библиотека RandLib позволяет работать с более чем 50 известными распределениями, непрерывными, дискретными, двумерными, циклическими и даже одним сингулярным. Если нужно какое-нибудь распределение, то вводим его имя и добавляем суффикс Rand. Заинтересовались?

Пусть нам дан набор точек и соответствующий им набор положительных весов . Мы считаем, что некоторые точки могут быть важнее других (если нет, то все веса одинаковые). Неформально говоря, мы хотим, чтобы на соответствующем интервале была проведена красивая кривая таким образом, чтобы она «лучше всего» проходила через эти данные.

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

В современных условиях интерес к анализу данных постоянно и интенсивно растет в совершенно различных областях, таких как биология, лингвистика, экономика, и, разумеется, IT. Основу этого анализа составляют статистические методы, и разбираться в них необходимо каждому уважающему себя специалисту в data mining.

К сожалению, действительно хорошая литература, такая что умела бы предоставить одновременно математически строгие доказательства и понятные интуитивные объяснения, встречается не очень часто. И данные лекции, на мой взгляд, необычайно хороши для математиков, разбирающихся в теории вероятностей именно по этой причине. По ним преподают магистрам в немецком университете имени Кристиана-Альбрехта на программах «Математика» и «Финансовая математика». И для тех, кому интересно, как этот предмет преподается за рубежом, я эти лекции перевел. На перевод у меня ушло несколько месяцев, я разбавил лекции иллюстрациями, упражнениями и сносками на некоторые теоремы. Замечу, что я не профессиональный переводчик, а просто альтруист и любитель в этой сфере, так что приму любую критику, если она конструктивна.

Вкратце, лекции вот о чем:

Данная статья является продолжением поста Генераторы непрерывно распределенных случайных величин. В этой главе учитывается, что все теоремы из предыдущей статьи уже доказаны и генераторы, указанные в ней, уже реализованы. Как и ранее, у нас имеется некий базовый генератор натуральных чисел от 0 до RAND_MAX:

unsigned long long BasicRandGenerator() {
    unsigned long long randomVariable;
    // some magic here
    ...
    return randomVariable;
}

С дискретными величинами все интуитивно понятнее. Функция распределения дискретной случайной величины:


Несмотря на простоту распределений дискретных случайных величин, генерировать их подчас сложнее, нежели чем непрерывные. Начнем, как и в прошлый раз, с тривиального примера.

Распределение Бернулли

Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984)

Популярность стохастических алгоритмов все растет. Многие из них базируются на генерации большого количества различных случайных величин. Далеко не всегда равномерно распределенных. Здесь я попытался собрать информацию о быстрых и точных генераторах случайных величин с известными распределениями. Задачи могут быть разными, разными могут быть и критерии. Кому-то важно время генерации, кому-то — точность, кому-то — криптоустойчивость, кому-то — скорость сходимости. Лично я исходил из предположения, что мы имеем некий базовый генератор, возвращающий псевдослучайное целое число, равномерно распределенное от 0 до некого RAND_MAX

unsigned long long BasicRandGenerator() {
    unsigned long long randomVariable;
    // some magic here
    ...
    return randomVariable;
}

и что этот генератор достаточно быстрый. Я имею ввиду, что дешевле сгенерировать с десяток случайных чисел, нежели чем посчитать логарифм или возвести в степень одно из них. Это могут быть стандартные генераторы: std::rand(), rand в MATLAB, Java.util.Random и т.д. Но имейте ввиду, что подобные генераторы редко подходят для серьезной работы. Зачастую они проваливают разные статистические тесты. А также, помните, что вы полностью зависите от них и лучше использовать свой собственный генератор, чтобы иметь представление о его работе.

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


Каждый алгоритм я буду сопровождать кодом, небольшим количеством математики и гистограммой из десятка миллионов сгенерированных случайных величин.

Равномерное распределение

Этот пост про относительно новый метод обработки сигналов, описанный в статье Adaptive data analysis via sparse time-frequency representation, а также про крохотную, но сбившую лично меня с толку, ошибку. Сию статью опубликовали в 2011 году профессора прикладной математики Калифорнийского Технологического института Томас И. Хоу и Ши Цзоцян, и, вероятно, к моменту, как вы это читаете, они уже её поправили.
На эту статью я наткнулся в поиске различных методов частотно-временного анализа нелинейных и нестационарных сигналов — в моем случае ультразвуковых сигналов от передвигающихся форменных элементов крови в сосудах человека. Суть такого анализа состоит в отслеживании изменений характеристик сигнала, иначе говоря, мы хотим знать зависимость составляющих сигнал частот от времени. За исключением широко распространенных методов — спектрального и вейвлет-анализа, были найдены такие методы как EMD (разложение на эмпирические моды) и синусоидальное моделирование, о котором далее пойдет здесь речь.
Метод эмпирических мод довольно прост в применении, однако не особо развит с точки зрения обоснованности полученных результатов. Томас Хоу и Ши Цзоцян пошли дальше в развитии математического аппарата и предложили свой метод синусоидального моделирования сигнала. Его идея заключается в разреженной декомпозиции сигнала на гармоники с гладкими амплитудами. Какой результат мы ожидаем получить — на картинке выше. В данном случае раскладывался сигнал, полученный функцией f(t) = 6t + cos(8πt) + 0.5 cos(40πt). Разложение сигнала, естественно, не уникально, поэтому был введен критерий минимума составляющих гармоник, и задача сформировалась следующим образом:

Откровенно говоря, ранее я ни разу не занимался в серьезной мере методами тестирования программного обеспечения. Однако, понимаю, что для полной уверенности в том, что программа будет работать, нужно перепробовать всевозможные варианты её использования. Также очевиден для меня и тот факт, что сделать это не всегда возможно. Если имеются конкретные варианты использования, но невозможно проверить их всех в силу их количества, стараются построить набор, который покроет все самые используемые варианты. Но что делать, если использование всех вариантов равновероятно? Как за минимальное число времени обнаружить все ошибки, на которые есть большая вероятность наткнуться? Данная задача действительно известна, и с ней нередко сталкиваются, ну хотя бы, в Яндексе.

Чтобы стало понятно о чем идет речь, представим, что нам необходимо протестировать какую-либо программу или сайт. Очень хорош пример с тестированием веб-формы, скажем, для регистрации или для поиска. Возникает вопрос, с какими ошибками в ней скорее всего встретится пользователь? Пускай у нас в форме имеется 6 вопросов, для каждого из которых возможны 10 вариантов ответа. Допустим, на страницу зашел целый миллион пользователей, и каждый из них ответил уникально. Теперь представим, что в форме для заполнения ответами скрывается ошибка. Если ошибка обнаруживается только при определенной комбинации ответов на все 6 вопросов, то на неё наткнется лишь один человек. Если же ошибка вылетает при наборе определенных ответов на какие-то 3 вопроса, то количество людей, обнаруживших ошибку возрастет до тысячи. Очевидно, что чем меньше элементов в комбинации, требуемой для ошибки, тем больше людей с ней встретится. Соответственно, перед нами теперь стоит задача: если мы не можем обнаружить все ошибки, то давайте хотя бы найдем самые критичные, то есть те, на которые наткнется больше всего пользователей.
Таким образом, мы должны сформировать тест-кейсы (и чем меньше, тем лучше), при переборе которых мы наткнемся на самые легкодоступные ошибки. Допустим, у нас имеется множество вопросов A, которое мы задаем количеством вариантов ответа на каждый из них: А = {2, 3, 5, 2, ...}. Пусть n — количество вопросов, а 1≤m≤n — степень критичности ошибок, она же степень покрытия или глубина покрывающего набора. Чем меньше значение m, тем критичнее ошибка. Задавая степень покрытия мы строим тестовый набор, который позволит обнаружить все ошибки, степень критичности которых меньше данного m. Если m = n, то поиск ошибок сводится к перебору всех вариантов. Чем меньше задаем степень, тем меньше тест-кейсов будет сформировано и тем меньше ошибок мы найдем.