Вероятность про урну с нумерованными шарами

[vicvolf]

mihaild Спасибо.
Хотел бы уточнить вопрос в отношении мат. ожидания для первой гипотезы Харди-Литтлвуда, которое я имел в виду.
Как я уже писал, количество простых кортежей, не превосходящих натуральное $n$ - $K(n)$ является арифметической функцией. Поэтому на $n$-ом вероятностном пространстве, построенном на начальном интервале натурального ряда, ему соответствует равновероятная случайная величина со значениями: $K(1),K(2),...,K(n)$. Рассмотрим также вероятности на пространствах от 1 до $n$: $p_1=K(1)/1,p_2=K(2)/2,...,p_n=K(n)/n$.
На другом вероятностном пространстве построим случайную величину, равную сумме случайных Бернулли $K_n=\sum_{i=1}^n {x_i}$, с указанными вероятностями:$p_1,p_2,...,p_n$.
Известно, что математическое ожидание данной случайной величины равно $E(K_n)= \sum_{i=1}^n {p_i}=\sum_{i=1}^n {K(i)/i}$.
Поставим вопрос, когда $K(n)$ асимптотически равно данному мат. ожиданию, т.е. выполняется $K(n) \sim E(K_n)=\sum_{i=1}^n {K(i)/i}$?
Таким случаем является $K(n)=Cn/\ln^k(n)$, так как $\sum_{i=1}^n{1/\ln^k(i)} \sim Cn/\ln^k(n)$. Это как раз подходит для первой гипотезы Харди-Литтлвуда. Также это выполняется для других подмножеств натурального ряда, содержащих бесконечное количество простых чисел. Например, для количества простых чисел на интервале натурального ряда, в арифметической прогрессии или в полиноме.

[mihaild]

vicvolf в сообщении #1661828 писал(а):

выполняется $K(n) \sim E(K_n)=\sum_{i=1}^n {K(i)/i}$?

Это можно записать как $K(n) \cdot (1 + h(n)) = \sum\limits\frac_{i=1}^n \frac{K(i)}{i}$, где $h(n) = o(1)$. Т.е. $K(n) \cdot (1 + h(n)) - K(n - 1)\cdot(1 + h(n - 1)) = \frac{K(n)}{n}$. Или $K(n) = K(n - 1) \cdot \frac{1 + h(n - 1)}{1 - 1/n + h(n)}$. Вроде бы это эквивалентно $\frac{K(n)}{K(n - 1)} \to 1$ (в одну сторону очевидно, в другую чуть-чуть расписать надо).

[vicvolf]

mihaild в сообщении #1661881 писал(а):

$\frac{K(n)}{K(n - 1)} \to 1$

Этому условию удовлетворяет любая монотонная возрастающая функция. Следовательно, любая $K(n)$. Но это не так. Например не подходит функции: $\ln^{k}(n), n^{1-\epsilon}$.

[mihaild]

vicvolf в сообщении #1661894 писал(а):

Этому условию удовлетворяет любая монотонная возрастающая функция

Нет, $K(n) = \exp(n)$ не удовлетворяет. Но да, у меня где-то константный множитель потерялся, потому что для $K(n) = \sqrt{n}$ нужно сумму умножить на $2$.

[vicvolf]

mihaild в сообщении #1661897 писал(а):

$K(n) = \exp(n)$

$1 \leq K(n) \leq n$. Так как $K(n)$ монотонно возрастает, то $K(n)/n$ - монотонно убывает, поэтому $\sum_{i=1}^n {K(i)/i}=\int_{t=1}^n {\frac{K(t)dt}{t}}+O(1)$.
С другой стороны $\sum_{i=1}^{\infty}{K(i)/i} \geq \sum_{i=1}^{\infty}{1/i}$, поэтому расходится. Учитывая это асимптотика $\sum_{i=1}^n {K(i)/i}$ не изменится при отбрасывании конечного числа первых членов.

[mihaild]

vicvolf в сообщении #1662002 писал(а):

Так как $K(n)$ монотонно возрастает, то $K(n)/n$ - монотонно убывает

Нет. $K(n)$ может, например, меняться между $n / 2$ и $n$.

$$K(n) = K(n - 1) \cdot \frac{1 + h(n - 1)}{1 - 1/n + h(n)}$$

$$\frac{K(n)}{K(n - 1)} \cdot \left(1 - 1/n + h(n)\right) = 1 + h(n - 1)$$

$$h(n) = \frac{K(n - 1)}{K(n)} \cdot (1 + h(n - 1)) - 1 + 1/n = \frac{K(n - 1)}{K(n)} - 1 + \frac{K(n - 1)}{K(n)} h(n - 1) + 1/n$$

Обозначим $g(n) = \frac{K(n - 1)}{K(n)} - 1 + 1/n$ (так что для случая когда равенство не просто асимптотическое а точное, $K(n) = n$, $g(n) = 0$.

$$h(n) = g(n) + (g(n) + 1 - 1/n) \cdot h(n - 1)$$

Как-то ни во что хорошее не сворачивается.

[vicvolf]

mihaild в сообщении #1662052 писал(а):

vicvolf в сообщении #1662002 писал(а):

Так как $K(n)$ монотонно возрастает, то $K(n)/n$ - монотонно убывает

Нет. $K(n)$ может, например, меняться между $n / 2$ и $n$.

Не понял. $K(n)$ - количество простых кортежей, не превосходящих $n$. $K(n)=\sum_{i=1}^n {1_A(i))$, где $1_A(i)$ - функция индикатор. $K(n)$ всегда монотонно возрастает.

[mihaild]

vicvolf в сообщении #1662065 писал(а):

Не понял. $K(n)$ - количество простых кортежей, не превосходящих $n$

Во-первых, нехорошо переключаться между произвольной арифметической функцией и конкретной.
Во-вторых, посмотрите, что будет, если $A = \cup_k [(2k)!, (2k + 1)!]$. При $n = (2k)!$ будет $\frac{K(n)}{n} \approx 0$, а при $n = (2k + 1)!$ - $\frac{K(n)}{n} \approx 1$.

[vicvolf]

mihaild в сообщении #1662068 писал(а):

посмотрите, что будет, если $A = \cup_k [(2k)!, (2k + 1)!]$. При $n = (2k)!$ будет $\frac{K(n)}{n} \approx 0$, а при $n = (2k + 1)!$ - $\frac{K(n)}{n} \approx 1$.

Спасибо, за пример. Но меня интересуют конкретные $K(n)$, которые я приводил ранее. Они являются монотонно возрастающими.

[mihaild]

vicvolf в сообщении #1662071 писал(а):

Но меня интересуют конкретные $K(n)$, которые я приводил ранее

Возрастающими или неубывающими?
Мой пример является неубывающим. А монотонно возрастающая арифметическая функция, принимающая неотрицательные значения, всего одна :)

[vicvolf]

mihaild в сообщении #1662077 писал(а):

Возрастающими или неубывающими?

Неубывающие.

[Dmitriy40]

Друзья, хотелось бы чуть продолжить тему, но немного в другую сторону.
Итак, исходные данные: пусть ищем кортеж длиной 25 последовательных простых чисел, гипотеза ХЛ1 выдаёт для него мат.ожидание пусть ровно $1.0$ для интервала $[0, 10^{33}]$. Допустим для его нахождения действительно достаточно проверить вот этот вот интервал $[0, 10^{33}]$. Допустим распределение вероятности кортежа по интервалу равномерное.

Вопрос №1: а если ищем не один такой кортеж, а любой из 10 разных, для каждого из которых гипотеза ХЛ1 выдаёт ровно то же мат.ожидание ровно $1.0$ для интервала $[0, 10^{33}]$. Сколько надо в среднем проверить для нахождения любого из 10 кортежей? 1/10 интервала или в $e$ или в $\sqrt{10}$ раз больше? Интуитивно кажется 1/10.
Но это вряд ли правильно, во всяком случае увеличив количество разных кортежей до $10^{30}$ штук окажется достаточно проверить их наличие (любого из них) лишь до $1000$, что явно неправильно. Или неправильно исходное допущение о равномерности распределения кортежей по интервалу, что и даёт такой абсурдный результат?

Вопрос №2: пусть гипотеза ХЛ1 даёт идентичные мат.ожидания ровно $10^{-9}$ для любых кортежей в некотором одном и том же диапазоне (ну вот подберу такие кортежи чтобы оно выполнялось), сколько надо разных кортежей проверять чтобы обнаружить любой из них в этом диапазоне? Миллиард или заметно больше/меньше? Мне кажется должно быть миллиард. Я понимаю что здесь где-то должна фигурировать вероятность, но пусть она одинакова для группы кортежей любого размера, так ведь можно же?

Фактически оба вопроса про одно и то же: про сложение мат.ожиданий.

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

Или этот вопрос математически неразрешим потому что во втором случае (много разных кортежей) мы фактически опираемся на существование статистических флуктуаций (что хотя бы один из множества кортежей встретится очень сильно задолго до своего мат.ожидания равного 1), чего математика гарантировать не может (можно лишь оценить вероятность такого)?

[mihaild]

Dmitriy40 в сообщении #1664177 писал(а):

Сколько надо в среднем проверить для нахождения любого из 10 кортежей? 1/10 интервала или в $e$ или в $\sqrt{10}$ раз больше?

$1/10$. Если взять такую постановку: забываем про все интервалы и числа, и просто кидаем монетку с вероятностью орла $p$, то среднее число орлов за $n$ бросков равно $np$, а среднее число бросков до первого орла включительно - $\frac{1}{p}$. Вероятность же получить орла за $\frac{1}{p}$ бросков - примерно $1 - \frac{1}{e}$ (при малых $p$), это почти что первый замечательный предел.

Dmitriy40 в сообщении #1664177 писал(а):

Или неправильно исходное допущение о равномерности распределения кортежей по интервалу, что и даёт такой абсурдный результат?

Оно прямо противоречит (на бесконечности) самой гипотезе Харди-Литлвуда. А про начальные интервалы эта гипотеза, вроде бы, ничего не говорит вообще.

Dmitriy40 в сообщении #1664177 писал(а):

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

Если наша задача найти как можно больше кортежей и мы проверяем очень большие диапазоны - то, согласно первой гипотезе Харди-Литтлвуда, второе выгоднее. Потому что $\int_2^{Dn} \frac{dt}{\log^{k} t} < D \int_2^n \frac{dt}{\log^k t}$.

[Dmitriy40]

mihaild в сообщении #1664178 писал(а):

$1/10$. Если взять такую постановку: забываем про все интервалы и числа, и просто кидаем монетку с вероятностью орла $p$, то среднее число орлов за $n$ бросков равно $np$, а среднее число бросков до первого орла включительно - $\frac{1}{p}$. Вероятность же получить орла за $\frac{1}{p}$ бросков - примерно $1 - \frac{1}{e}$ (при малых $p$), это почти что первый замечательный предел.

Спасибо, так понятно.

mihaild в сообщении #1664178 писал(а):

Если наша задача найти как можно больше кортежей и мы проверяем очень большие диапазоны

А если хотя бы один любой из $D$ штук? То неизвестно потому что это будут флуктуации (вероятность которых считается по другому), да?

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

[Dmitriy40]

mihaild в сообщении #1664178 писал(а):

Потому что $\int_2^{Dn} \frac{dt}{\log^{k} t} < D \int_2^n \frac{dt}{\log^k t}$.

Попытался посчитать насколько именно меньше, для реальных чисел вышло:
для $D=1$ расчётное общее время счёта 600млн лет в один поток;
для $D=10^{6}$ время в 100 раз меньше (точнее отношение двух величин из формулы равно 100, это не совсем отношение времён, но для грубой прикидки сойдёт);
для $D=10^{12}$ время в 30000 раз меньше;
для $D=10^{15}$ время в 900000 раз меньше.
Но $10^{15}$ паттернов только генериться будут сравнимое время, если не больше.
Выигрыш очевидно есть, но недостаточен для практики. Либо надо сотни-тысячи потоков запускать, тогда есть некоторая надежда на время в год счёта.