Сходимость Монте-Карло: корень или экспонента

[Gortaur]

Везде читал, что сходимость метода Монте-Карло для счета МО имеет скорость порядка $\sqrt{N}$.

С другой стороны, недавно наткнулся на факт, что имеет место сходимость по вероятности экспоненциальна по $N$. А именно, из неравенства Хоэфдинга следует, что

$$ \mathrm{P}(|\mathrm{E}[x] -\hat{\mathrm{E}}[x] |\geq \varepsilon)\leq 2\mathrm{e}^{-cN\varepsilon^2}. $$

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

[ИСН]

Я тут не спец, но по-моему, это одно и то же разными словами. Возьмём N=100; какой $\varepsilon$ это нам обеспечит для, скажем, P=0.01? а если N=10000? а если...

[Gortaur]

То есть Вы имеете ввиду, что если зафикисровать значение справа то меняя $N$, у нас $\varepsilon$ слева будет уменьшаться как корень? Логично. То есть если зафиксировать вероятность нежелательного события, то абсолютная разность между данными величинами уменьшается как корень...

[ИСН]

Именно.

[_hum_]

А разве тут не такая же ситуация, как с применением к случайной величине $\Hat{E}[x]$ неравенства Чебышева v.s. неравенства Бернштейна (первое дает грубую оценку, но в более общем случае - для применения достаточно конечности дисперсии, второе же более точную, но при более сильных ограничениях на случайную величну)?

[--mS--]

Gortaur в сообщении #407389 писал(а):

Везде читал, что сходимость метода Монте-Карло для счета МО имеет скорость порядка $\sqrt{N}$.
Тогда я не понимаю, какая сходимость имеется ввиду в первом случае - и когда полез искать в интернет, ничего толкового кроме общих фраз не нашел.

Вставлю-таки свои пять копеек :) Не касаясь Хёфдинга - там про скорость ИСН всё разъяснил, а вот по поводу последней фразы.

Под "скоростью сходимости порядка $\sqrt{N}$" (скорее, $\frac{1}{\sqrt{N}}$) имеется в виду типичная скорость сходимости среднего к матожиданию в силу ЦПТ.

Пусть дисперсия есть, тогда последовательность с.в.

$$\sqrt{N}\left(\frac{X_1+\ldots+X_N}{N}-\mathsf EX_1\right)\rightarrow \xi\sim \textrm{N}_{0, \mathsf DX_1}$$

(слабо сходится). Грубо говоря, в некотором (только что указанном) смысле, $\frac{X_1+\ldots+X_N}{N}-\mathsf EX_1$ есть при больших $N$ что-то вроде $\dfrac{\xi}{\sqrt{N}}$.

Если говорить точнее, то

$$\mathsf P\left(\left|\frac{X_1+\ldots+X_N}{N}-\mathsf EX_1\right|\geqslant \frac{\varepsilon}{\sqrt{N}}\right)\to \textrm{const} = \mathsf P(|\xi| > \varepsilon).$$

Вот $\frac{\varepsilon}{\sqrt{N}}$ и показывает скорость сходимости. Кабы вероятность стремилась к нулю, это означало бы, что среднее к матожиданию сходится быстрее, чем нечто делить на корень из $N$. Кабы к единице - медленнее. А к ненулевой постоянной - аккурат с такой скоростью.

(Оффтоп)

Вообще, любопытная какая-то система образования: марковские процессы, мартингалы и т.п. ужастики. А тервер и математическая статистика как будто где-то в стороне остались? Ну, там, асимптотическая нормальность оценок, асимптотическая нормальность основных статистик вроде выборочного среднего, та же ЦПТ?

[Gortaur]

(Оффтоп)

Все просто, второму меня учили в России на основе аксиоматического подхода и без единого рисунка на доске. Первое я начал изучать самостоятельно, а затем получил магистра в Европе по фин. математике. Там особо глубоко (до собственно теор. вера как он ведется в России) не копали - квадртическими вариациями процессов Ито можно просто по формулам оперировать. Теперь, когда начал "всерьез" заниматься наукой, ощущается небольшой недостаток практики использования теории в некоторых областях - собственно по ним и вопросы. Как бы это ни было кощунственно, я не жалею что в свое время не учил изо всех сил данную область - на том уровне, на котором она тогда преподавалась, я начинаю использовать только сейчас, и именно сейчас у меня есть интерес к данным понятиям. Зачем нужно было включать их на втором курсе - не понимаю. Лучше бы дали меньше, но лучше и практичнее. Теор. вер. слишком красив, чтобы аксиоматику Колмогорова подавать только как аксиоматическую систему (ну может быть еще шарики и урны - но это... вот только что видел смайл, которого тошнит, ну да ладно... )

[--mS--]

(Оффтоп)

Спасибо, тогда картина понятна, а то одно с другим у меня плохо связывалось :)

[Gortaur]

_hum_
Что за история с неравенствами Чебышева и Берштейна?

[--mS--]

Gortaur в сообщении #407523 писал(а):

_hum_
Что за история с неравенствами Чебышева и Берштейна?

Объяснения написаны в скобках. Чем больше есть моментов у случайной величины, тем быстрее убывает $\mathsf P(|\xi| > x)$ на бесконечности. А неравенство Хёфдинга - оно и вовсе для сумм ограниченных с.в. А для ограниченных с.в. можно рисовать любые оценки (нуля) сверху: хоть $\mathsf P(|\xi|>x)\leqslant C\cdot {137}^{-x^{92}}$.

[_hum_]

Да, только справедливости ради надо сказать, что я не совcем правильно оценил ситуацию - "история с неравенствами Чебышева и Бернштейна" объясняла бы противоречие между разными скоростями сходимости к нулю вероятностей отклонения среднего от матожидания. В методе же Монте-Карло, действительно, интересуются не скоростью убывания вероятностей при заданной величине отклонения, а скоростью убывания отклонения для заданной гарантированной вероятности. А в этом случае и Бернштейн, и Чебышев дают одно и то же $\sim n^{-1/2}$.

[--mS--]

_hum_ в сообщении #407611 писал(а):

Да, только справедливости ради надо сказать, что я не совcем правильно оценил ситуацию

Аккурат перед Вашим сообщением я написала аналогичное, а потом, прочтя ИСН, снесла :)