Вероятностное доказательство

[vicvolf]

Любая гипотеза считается доказанной, если она доказана для всех случаев. Поэтому вероятностное доказательство, которое в лучшем случае доказано с вероятностью равной 1, т.е. почти для всех случаев, не является доказательством для всех случаев. Следовательно, вероятностное доказательство является только обоснованием гипотезы. Аналогичное можно сказать о любом утверждении внутри вероятностного доказательства. Прав ли я?
С другой стороны, есть вероятностные доказательства, которые признаны серьезными теоремами https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 1%86%D0%B0 С чем это связано? Помогите разобраться.

[mihaild]

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

Поэтому вероятностное доказательство, которое в лучшем случае доказано с вероятностью равной 1, т.е. почти для всех случаев, не является доказательством

Совершенно непонятно, что это значит.
Во-первых, что вы понимаете под "вероятностным доказательством"?
Во-вторых, что такое "доказанное доказательство"?

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

[vicvolf]

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

Давайте подправим текст:

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

Любая гипотеза считается доказанной, если она доказана для всех случаев. Поэтому вероятностное доказательство, которое в лучшем случае справедливо с вероятностью равной 1, т.е. почти для всех случаев, не является доказательством для всех случаев.

[Евгений Машеров]

Если конкретно о Теореме Эрдёша — Каца, то в 1940 году было дано не доказательство в строгом смысле, а некая "эвристика Каца". А в доказательстве 1958 года, насколько я способен его понять, эвристические соображения не используются.
http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa417.pdf

[mihaild]

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

Математическое доказательство — рассуждение с целью обоснования истинности какого-либо утверждения (теоремы), цепочка логических умозаключений, показывающая, что при условии истинности некоторого набора аксиом и правил вывода утверждение верно.

Не совсем так. Например, понятия "цель" в определении быть не должно:)
Можно, например, так: доказательство - последовательность утверждений, каждое из которых либо является аксиомой, либо выводится из предыдущих по одному из правил вывода, и заканчивающаяся доказываемым утверждением.

Чтобы хотя бы сформулировать, что значит "утверждение справедливо с вероятностью $1$", нужно задавать вероятностное пространство.
Например, есть ЗБЧ: для любого вероятностного пространства определенной структуры, определенная последовательность случайных величин сходится к чему нужно почти наверное. При этом сам ЗБЧ доказывается, и нельзя оценивать вероятность того, что он верен.

Не говорят "$X$ почти наверное доказано". Говорят "доказано, что $X$ верно почти наверное". И эта формулировка уже не параметризована ничем случайным.

[vicvolf]

Евгений Машеров в сообщении #1256092 писал(а):

Если конкретно о Теореме Эрдёша — Каца, то в 1940 году было дано не доказательство в строгом смысле, а некая "эвристика Каца". А в доказательстве 1958 года, насколько я способен его понять, эвристические соображения не используются.
http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa417.pdf

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

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

Чтобы хотя бы сформулировать, что значит "утверждение справедливо с вероятностью $1$", нужно задавать вероятностное пространство.
Например, есть ЗБЧ: для любого вероятностного пространства определенной структуры, определенная последовательность случайных величин сходится к чему нужно почти наверное.
Говорят "доказано, что $X$ верно почти наверное". И эта формулировка уже не параметризована ничем случайным.

Согласен. Я понимаю вероятностное доказательство именно в этом смысле.

[Евгений Машеров]

Если читать внимательнее, видно, что это относится к теореме Харди-Раманужана, причём в следующем параграфе поясняется, что существует доказательство чисто аналитическими методами. Но дело в том, что неравенство Чебышева широко используется в теории вероятностей, но имеет более широкое значение, и может быть доказано без вероятностных соображений, как результат теории меры.

[mihaild]

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

Согласен. Я понимаю вероятностное доказательство именно в этом смысле.

Тогда я совсем не понимаю, в чем вопрос. Да, мы вместо утверждений вида $\forall x \in X: P(x)$ доказываем $\mu\{x \in X| P(x)\} = 1$. Чем теоремы такого вида хуже любого другого?

Евгений Машеров в сообщении #1256103 писал(а):

и может быть доказано без вероятностных соображений, как результат теории меры

А есть что-то из тервера, что не может быть доказано "как результат теории меры"? (понятно, что определение независимости в терминах просто меры выглядит несколько неестественно, но всё равно же формулируется)

[grizzly]

Есть ещё так называемый вероятностный метод в комбинаторных дисциплинах:

Алон Н., Спенсер Д. в книге "Вероятностный метод" писал(а):

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

[vicvolf]

Евгений Машеров в сообщении #1256103 писал(а):

причём в следующем параграфе поясняется, что существует доказательство чисто аналитическими методами.

На стр. 78 указанной Вами статьи сказано, что величина $S(n,u)/n$ является характеристической функцией вероятностного распределения случайной величины, которая принимает значения:$V(1),V(2),...,V(n)$ с вероятностью $1/n$. Далее сказано, что в соответствии с теоремой 1 (Крамер "Математические методы статистики") на стр. 96-98, которая говорит о сходимости по распределению, в качестве предельного распределения (для указанной случайной величины) получают нормальное распределение.

[Евгений Машеров]

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

А есть что-то из тервера, что не может быть доказано "как результат теории меры"? (понятно, что определение независимости в терминах просто меры выглядит несколько неестественно, но всё равно же формулируется)

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

[Евгений Машеров]

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

На стр. 78 указанной Вами статьи сказано, что величина $S(n,u)/n$ является характеристической функцией вероятностного распределения случайной величины, которая принимает значения:$V(1),V(2),...,V(n)$ с вероятностью $1/n$.

Насколько я понял это место, там не используется предположение о равнораспределённости. Это "замечание по поводу", позволяющее воспользоваться уже готовыми выкладками, сделанными для решения вероятностной задачи.

[vicvolf]

Евгений Машеров в сообщении #1256300 писал(а):

сделанными для решения вероятностной задачи.

Значит данная теорема и ее доказательство все таки вероятностные! Хочется разобраться в сути самого утверждения https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 1%86%D0%B0.
Кратко его можно сформулировать так. Предельное распределение количества простых делителей $\omega(n)$ является нормальным.
При доказательстве этого утверждения в работе http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa417.pdf, как я уже говорил, вводится случайная величина, которая имеет характеристическую функцию $S(n,u)/n$ и показывается, что ее распределение сходится к нормальному. Следовательно, сходится к нормальному не распределение $\omega(n)$, а распределение введенной случайной величины. Как это понять?

[RIP]

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

Значит данная теорема и ее доказательство все таки вероятностные!

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

Любой начальный отрезок натурального ряда $\{1,2,\dotsc,n\}$ можно естественным образом превратить в вероятностное пространство $\left(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}\right)$, взяв $\Omega_{n}=\{1,2,\dotsc,n\}$, $\mathcal{A}_{n}$ — все подмножества $\Omega_{n}$, $\mathbb{P}_{n}(A)=\frac{|A|}{n}$. Тогда произвольную (вещественно- или даже комплекснозначную) функцию $f(k)$ натурального аргумента (а точнее, её ограничение на $\Omega_{n}$) можно рассматривать как случайную величину $\xi_{n}$ на этом вероятностном пространстве: $\xi_{n}(k)=f(k)$, $1\leqslant k\leqslant n$. В частности, можно говорить о мат. ожидании $\mathbb{E}\xi_{n}=\frac{1}{n}\sum_{k=1}^{n}f(k)$ и дисперсии $\mathbb{D}\xi_{n}=\mathbb{E}\left\lvert\xi_{n}-\mathbb{E}\xi_{n}\right\rvert^{2}=\mathbb{E}\left\lvert\xi_{n}\right\rvert^{2}-\left\lvert\mathbb{E}\xi_{n}\right\rvert^{2}=\frac{1}{n}\sum_{k=1}^{n}\bigl\lvert f(k)\bigr\rvert^{2}-\left\lvert\frac{1}{n}\sum_{k=1}^{n}f(k)\right\rvert^{2}$, а для вещественной $f$ — о функции распределения $F_{\xi_{n}}(x)=\frac{1}{n}\bigl\lvert\{k\leqslant n:f(k)\leqslant x\}\bigr\rvert$ и характеристической функции $\varphi_{\xi_{n}}(t)=\mathbb{E}\mathrm{e}^{\mathrm{i}t\xi_{n}}=\frac{1}{n}\sum_{k=1}^{n}\mathrm{e}^{\mathrm{i}tf(k)}$.

Таким образом, каждой арифметической функции $f(k)$ можно сопоставить последовательность случайных величин $\xi_{n}$ (живущих на разных вероятностных пространствах). Если взять $f(k)=\omega(k)$ (в статье рассуждения проводятся для $f(k)=\Omega(k)$), то несложно, например, показать, что $\mathbb{E}\xi_{n}=\ln\ln n+O(1)$, то есть

$$\sum_{k=1}^{n}\omega(k)=n\ln\ln n+O(n).$$

С дисперсией посложнее, но нетрудно доказать, что $\mathbb{D}\xi_{n}=O(\ln\ln n)$. Применяя неравенство Чебышёва из теории вероятностей, отсюда легко получить теорему Харди–Рамануджана:

$$\mathbb{P}_{n}\left\{\left\lvert\xi_{n}-\mathbb{E}\xi_{n}\right\rvert\geqslant c\right\}\leqslant\frac{\mathbb{D}\xi_{n}}{c^2}\implies\left\lvert\left\{k\leqslant n:\bigl\lvert\omega(k)-\ln\ln n\bigr\rvert\geqslant\sqrt{a(n)\ln\ln n}\right\}\right\rvert=O\left(\frac{n}{a(n)}\right).$$

Чтобы изучать предельное распределение, удобно использовать стандартный трюк (как в центральной предельной теореме). Если с.в. $\xi$ имеет нормальное распределение с мат. ожиданием $\mu$ и дисперсией $\sigma^{2}$, то случайная величина $\eta=\frac{\xi-\mu}{\sigma}$ имеет стандартное нормальное распределение (и наоборот). Поэтому вместо последовательности с.в. $\xi_{n}$ удобно рассмотреть «отнормированную» последовательность с.в. $\eta_{n}=\frac{\xi_{n}-\ln\ln n}{\sqrt{\ln\ln n}}$, то есть

$$\eta_{n}(k)=\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}},\quad1\leqslant k\leqslant n.$$

(Вместо точных значений мат. ожидания и дисперсии используются приближения.) Полученная последовательность отличается от той, которая приведена в Википедии, но она лучше соответствует вероятностному смыслу теоремы (и в статье рассматривается именно она), а формулировку из Википедии можно получить из тех соображений, что $\ln\ln n$ очень медленно меняется, так что $\ln\ln k$ и $\ln\ln n$ — это «почти одно и то же» для «почти всех» $k\in\{1,2,\dotsc,n\}$.

Так вот, теорема Эрдёша–Каца утверждает, что последовательность $\eta_{n}$ слабо сходится к стандартному нормальному распределению, то есть для любого $x\in\mathbb{R}$ выполнено

$$\lim_{n\to\infty}F_{\eta_{n}}(x)=\lim_{n\to\infty}\frac{1}{n}\left\lvert\left\{k\leqslant n:\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\leqslant x\right\}\right\rvert=\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}\mathrm{e}^{-t^{2}/2}\mathrm{d}t.$$

Согласно теореме Леви, это равносильно (поточечной) сходимости для характеристических функций, то есть для произвольного $t\in\mathbb{R}$ верно

$$\lim_{n\to\infty}\varphi_{\eta_{n}}(t)=\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp\left(\mathrm{i}t\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\right)=\mathrm{e}^{-t^{2}/2}.$$

Последнее предельное соотношение и доказывается в статье (вместе с оценкой скорости сходимости, откуда с помощью неравенства Эссеена получается скорость сходимости в теореме Эрдёша–Каца).

В предельных равенствах

\[\begin{gathered} \lim_{n\to\infty}\frac{1}{n}\left\lvert\left\{k\leqslant n:\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\leqslant x\right\}\right\rvert=\Phi(x),\quad x\in\mathbb{R},\\ \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp\left(\mathrm{i}t\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\right)=\mathrm{e}^{-t^{2}/2},\quad t\in\mathbb{R}, \end{gathered}\]

нет никаких вероятностей и случайных величин. Это просто утверждения о сходимости некоторых функциональных последовательностей (в первом случае сходимость равномерная на $\mathbb{R}$, поскольку рассматриваются функции распределения и предельная функция непрерывна). Случайные величины упоминаются только для того, чтобы вывести первое равенство из второго. И никаких «доказательств с вероятностью 1» (что бы это ни значило) тут нет.

[vicvolf]

RIP Больщое спасибо за подробный ответ!!!

RIP в сообщении #1256452 писал(а):

Тогда произвольную (вещественно- или даже комплекснозначную) функцию $f(k)$ натурального аргумента (а точнее, её ограничение на $\Omega_{n}$) можно рассматривать как случайную величину $\xi_{n}$ на этом вероятностном пространстве: $\xi_{n}(k)=f(k)$, $1\leqslant k\leqslant n$.

Немного возражу. Не произвольную числовую функцию, а только инъективную, чтобы не повторялись значения. Например, функция Мертенса $M(n)$ не подходит, а функция количества простых делителей $w(n)$ подходит.

Цитата:

Таким образом, каждой арифметической функции $f(k)$ можно сопоставить последовательность случайных величин $\xi_{n}$ (живущих на разных вероятностных пространствах).

А чем отличаются вероятностные пространства для $\xi_{n}$ и $f(n)$?

Цитата:

Применяя неравенство Чебышёва из теории вероятностей, отсюда легко получить теорему Харди–Рамануджана:

$$\mathbb{P}_{n}\left\{\left\lvert\xi_{n}-\mathbb{E}\xi_{n}\right\rvert\geqslant c\right\}\leqslant\frac{\mathbb{D}\xi_{n}}{c^2}\implies\left\lvert\left\{k\leqslant n:\bigl\lvert\omega(k)-\ln\ln n\bigr\rvert\geqslant\sqrt{a(n)\ln\ln n}\right\}\right\rvert=O\left(\frac{n}{a(n)}\right).$$

Наверное

$$\mathbb{P}_{n}\left\{\left\lvert\xi_{n}-\mathbb{E}\xi_{n}\right\rvert\geqslant c\right\}\leqslant\frac{\mathbb{D}\xi_{n}}{c^2}\implies\left\lvert\left\{k\leqslant n:\bigl\lvert\omega(k)-\ln\ln n\bigr\rvert\geqslant\sqrt{a(n)\ln\ln n}\right\}\right\rvert=O\left(\frac{1}{a(n)}\right).$$

Цитата:

Так вот, теорема Эрдёша–Каца утверждает, что последовательность $\eta_{n}$ слабо сходится к стандартному нормальному распределению, то есть для любого $x\in\mathbb{R}$ выполнено

$$\lim_{n\to\infty}F_{\eta_{n}}(x)=\lim_{n\to\infty}\frac{1}{n}\left\lvert\left\{k\leqslant n:\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\leqslant x\right\}\right\rvert=\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}\mathrm{e}^{-t^{2}/2}\mathrm{d}t.$$

Значит теорема Эрдёша–Каца о слабой сходимости с вероятностью меньше 1.

Цитата:

В предельных равенствах

\[\begin{gathered} \lim_{n\to\infty}\frac{1}{n}\left\lvert\left\{k\leqslant n:\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\leqslant x\right\}\right\rvert=\Phi(x),\quad x\in\mathbb{R},\\ \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp\left(\mathrm{i}t\frac{\omega(k)-\ln\ln n}{\sqrt{\ln\ln n}}\right)=\mathrm{e}^{-t^{2}/2},\quad t\in\mathbb{R}, \end{gathered}\]

нет никаких вероятностей и случайных величин. Это просто утверждения о сходимости некоторых функциональных последовательностей (в первом случае сходимость равномерная на $\mathbb{R}$, поскольку рассматриваются функции распределения и предельная функция непрерывна). Случайные величины упоминаются только для того, чтобы вывести первое равенство из второго. И никаких «доказательств с вероятностью 1» (что бы это ни значило) тут нет.

Доказывается действительно второе указанное предельное равенство для характеристической функции, как сходимость некоторой функциональной последовательности. А вот для получения первого равенства из второго вводится случайная величина, которая имеет другое вероятностное пространство. Поэтому, как Вы писали выше, теорема Эрдёша–Каца о слабой сходимости к нормальному распределению.