?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Entries by tag: math

В военное время значение синуса может достигать четырех
nyaload
_winnie
sin(π/2 - ln(4 + √15)⋅i) = 4:
http://www.wolframalpha.com/input/?i=sin%28pi%2F2+-+%28ln%284+%2B+sqrt%2815%29%29+*+i%29

Кратко, разоблачение магии и как определить arcsin(4): Read more...Collapse )
Tags: ,

(1 - a^x)^x
nyaload
_winnie
Попробуйте найти значение x, при котором (1 - a^x)^x минимально. 0<a<1.
Нужно где-то заметить симметрию, не получится просто так найти обратную функцию для производной, чтобы поставить в неё 0.

Я решал так: сначала попробовал приравнять производную нулю. Не сообразил, как справится с этим крокодилом, симметрии в нём не увидел. Нашёл численный ответ для a = 1/3, a=1/5, a=1/e. Найденные цифры числа — поискал в гугле (даже OEIS не понадобился). Нашёл простое выражение для числа. Дальше по выражению — сообразил, как «красиво» получить ответ без численного подсчета. В комментах - уже три решения, в т.ч. моё (я ещё написал, почему минимум есть и единственный).
Tags:

Фильтр Блума, теоретический предел для размера
nyaload
_winnie
Про фильтр блума, как оценить снизу количество необходимых бит для хранения set, с возможностью ложных срабатываний (false positive для элементов которых нет в set, но мы всё равно возвращаем true).

Пусть мы хотим запомнить N элементов из бесконечно большого множества T

Оценим, сколько битов надо для указания какой-либо функции, которая возвращает true именно для наших N элементов. И разрешим с вероятностью p возвращать ("ошибочно") true на остальных элементах.

Будем перебирать вообще все функции которые возвращают true для элементов T с вероятностью p (без ограничения для наших N элементов).
С вероятностью p^N такая функция будет возвращать true для именно наших N элементов (и false с вероятность 1-p для всех остальных). Для хранения такой функции - нужно Log2(1/p^N) битов. Например, можно начать перечислять все такие функции, и записать номер той функции которая подошла. Где-то 1/p^N шаге нам повезёт, мы запомним номер этого шага, для запоминания номера нужно Log2(номер шага) битов.

Я не знаю, как это рассуждение превратить в строгое (во-первых, я ограничил способ поиска нужной функции, во-вторых я не очень могу объяснить переход от "подходит 1/x часть функций" -> "нужно log(x) битов")

Итого, мы получили оценку -N*log2(p). Она похожа на формулу битов для настоящего фильтра блума, отличается ровно в Log(e)≈1.44 раз в меньшую сторону (у фильтра блума — -N*Log2(p) * Log2(e) == -N*ln(p)/ln^2(2)). Это значит, что фильтр блума где-то в полтора раза хуже некоего идеального алгоритма (но не в N раз, и не в миллион раз).

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

(no subject)
nyaload
_winnie
Невозможно 2147483648 конфет раздать поровну миллиарду детишек: у кого-то будет две, у кого-то три.
Будьте осторожны с rand()%N

Ссылки:
Как правильно делать в C++11: http://dobrokot.ru/pics/i2014-06-27__02-01-24_55kb.png (из этой презентации, видео), спасибо bik_top
Интересные комментари из похожего поста: http://users.livejournal.com/_winnie/219862.html
StackOverflow: http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator ( спасибо realsupport )
Tags: ,

Ложь + ложь = статистика
nyaload
_winnie
Парадокс плохих весов:

Пусть есть весы, которые ошибаются на ±100 кг. Взвесим каждого жителя города с населением в n=1'000'000 жителей и сложим измереный вес, разделим на n. Полученное число можно использовать для определения среднего веса гражданина, с точностью ±сотня грамм. ( дисперсия ошибки весов - 1/3*(100^2) (см. тут), среднеквадратичное отклонение для посчитаного среднего, т.е. корень из дисперсии - √(1/3*100^2) / √(n) = 1/(10*√(3)) (см. тут) около 50 грамм, ЦПТ, правило трёх сигм ).

Для каждого конкретного гражданина весы будут показывать совершенно неадекватную метрику, включая отрицательные значения, или 120 кило для ребёнка.
Парадокс заключается в том, что после усредения этих неадекватных измерений по миллиону человек - мы получим корректное значение среднего веса.

Даже если у весов есть постоянная ошибка в какую-то сторону, т.е. не просто "±100 килограмм", а "±100 килограмм и ещё на 1кг меньше ", во-первых их всё равно можно использовать для отслеживания изменений среднего веса, во-вторых их можно иногда всё-таки откалибровать в лабораторных условиях. Ошибаться на ±100 кило они будут так же, но мы будем знать что к измерению надо добавить 1кг.
Tags:

Рефакторинг классиков
nyaload
_winnie
Почитал в n-й раз про метод Гаусса-Зейделя (wiki). Заметил, что внутренний цикл переписывается в одну строчку, если не выкидывать одно слагаемое из цикла, а вычесть его в самом конце. Причем "вычитается" оно заменой с x[i] = ... на x[i] +=

Метод Гаусса-Зейделя получается из метода Якоби добавлением бага "пишем данные туда же, откуда читаем". Наверняка так оно и было, а "разделение на верхне- и нижнетреугольную матрицы" уже потом (где-то в 1820-1870 годах) придумали.

Read more...Collapse )

Fountain code
nyaload
_winnie
Предположим, вы идете с флешкой в гости к Васе и Лене, у Васи есть фильм «Матрица», у Лены - «Амели».
Вы хотите принести им те фильмы, которых у них нет. Васе «Амели», а Лене «Матрицу».

Вы можете не класть оба фильма на флешку, а положить на неё Z=(«Матрица» + «Амели»). Сложение можно взять побитовое, т.е. XOR.
У Васи делаем (Z - «Матрица») и получаем «Амели», и так же делаем у Лены, получая «Матрицу» из (Z - «Амели»).

( по мотивам http://en.wikipedia.org/wiki/Fountain_code ).
Tags: , ,

Автоматическое дифференцирование
nyaload
_winnie
Предположим, у вас есть функция вида

double f(double x) {
    ... ад, матан, коллеги, goto, и проблема останова ... 
}

для которой вы хотите найти производную.

Создаём новый арифметический тип RealWithDiff, из пары чисел, с операциями сложения, умножения и перегруженными sin и тп.
Первое число в паре - повторяет поведение обычных чисел. А второе - это "производная".
Правила сложения и тп. определяются так:
RealWithDiff(f, df) * RealWithDiff(g, dg) = RealWithDiff(f*g, df*g + dg*f)
sin(RealWithDiff(f, df)) = RealWithDiff(sin(f), cos(f) * df)
(RealWithDiff(x, df) > n) = (x > n)

Подставляем этот тип вместо double в функцию f, это делается более-менее втупую автозаменой, а в случае python даже не нужно копаться внутри функции. Получаем новую функцию, которая считает для функции f значение вместе с производной.

Это не является численным разностным дифференцированием. Например, нет проблемы какой эпсилон выбрать для функции sin(1/x) или "150 итерация в mandelbrot".
И не является символьным дифференцированием (мы считаем число, а не преобразуем выражение).

Интересно, для чего ещё может пригодится такой трюк с подменой типа переменной.

Источник: http://en.wikipedia.org/wiki/Automatic_differentiation
Пример кода: https://gist.github.com/dobrokot/8383678
Tags:

substring probability, n successes in a row
nyaload
_winnie
Оказывается, задача "с какой вероятностью встречается данный паттерн-подстрока в случайной строке" - нетривиальна.
Ответ зависит от паттерна - может ли он пересечься сам с собой. Например, ответ разный для паттернов 'wat', 'wow', 'www'.
Как ни парадоксально, то, что паттерн может пересекаться с самим собой - уменьшает его вероятность появления, несмотря на то, что самопересечение позволяет запихать его большее число раз в строку.
А вот матожидание количества паттернов в строке - считается тривиально и не зависит от паттерна. Так как можно складывать матожидания зависимых величин, то можно сложить матожидания "паттерн есть на i-й позиции" и получить матожидание количества паттернов.

Для простейшего случая, "вероятность есть ли паттерн '11' в случайной строке из N нулей/единиц" - ответ 1 - Fibbonachi(n+2)/2^N. Для паттерна '01' - ответ 1 - (n+1)/2^N.
Read more...Collapse )
Матрицы можно построить для произвольного регулярного выражения (сделать конечный автомат, и сделать матрицу из переходов между состояниями).
Tags:

arctg(e^x)
nyaload
_winnie
Из любопытства посчитал, какое распределение получится, если взять логарим модуля случайной величины с распределением Коши ( pdf, f(x) = π-1/(1+x2) ). Получил cdf F(x)=(2/π)arctg(ex) (а официальное название - Hyperbolic secant distribution). Исходя из симметрии начального распределения, результат должен тоже быть симметричный относительно точки (x=0,y=1/2).

И действительно: оказалось, функция что функция arctg(ex)-π/4 - нечетная (симметричная относительна начала координат), хоть это и не видно сразу из формулы. WolframAlpha подсказал, что эта функция - это функция Гудермана, только пополам ( gd(x) = 2arctg(ex)-π/2 ), в википедии можно почитать, как она связывает обычную тригонометрию и гиперболическую.

Для меня оказалось неожиданно, что симметричность функции arctg(ex) - видна только со второго взгляда, а не сразу, если бы не симметричность начальной задачи - я бы не заметил это.

Read more...Collapse )

Немного удивлён, что гиперболических тригонометрических функций - не было ни в школе, ни в универе, а они постоянно всплывают, как сегодня.

Ещё, логарифм распределения Парето (Ципфа) - это экспоненциальное распределение (сдвинутое на константу).

Распределение Хи-квадрат и гамма-распределение - это одно и тоже, только гамма-распределение - Хи-квадрат умноженое на константу.

Хи-квадрат(2), т.е. N12+N22 - это экспоненциальное распределение. Что и даёт способ генерации нормального распределения, когда генерируют случайную точку на плоскости, с квадратом радиуса как корень экспоненциальнго распределения (т.е. логарифм равномерного), и равномерно распределённым углом. Декартовы координаты этой точки - будут двумя независимыми случайными величинами с нормальным распределением (
angle = random.uniform(0, 2*pi)
rad = sqrt(-2*log(random.uniform(0, 1))) # 2* - для нормировки stddev, и обработайте логарифм нуля
N1_x = sin(angle)*rad
N2_y = cos(angle)*rad

)
Tags: