limsup

[geomath]

Скажите, как подсчитать на компьютере верхний предел случайной числовой последовательности?

Верхний предел последовательности - это ее наибольшее предельное значение, вообще говоря, бесконечное. С другой стороны, например, для последовательности 1/n ее верхний (он же обычный) предел 0 меньше любого ее члена.

Обычный предел последовательности подсчитать довольно просто: нужно либо взять ее член с максимально доступным номером, либо производить сравнение (вычисление) ее членов до тех пор, пока они не стабилизируются с заданной степенью точности. А в случае верхнего предела как?

[worm2]

Попробуйте найти предел подпоследовательности $\{a_{p_k}\}$ чисел, являющихся локальными максимумами: $a_{p_k}>a_{p_k-1}$, $a_{p_k}>a_{p_k+1}$.
Т.е. взять локальный максимум с наибольшим возможным номером.
Если начиная с некоторого (небольшого по сравнению с максимально доступным) номера последовательность монотонна, то это повод для сомнений, а не монотонна ли она вообще? Если да, то предел либо не существует, либо единственен.

[maxal]

Сформулируйте четче задачу. Что значит "случайная числовая последовательность" и что значит "вычисление" ее членов.

[geomath]

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

Точнее, рассмотрим последовательность равновероятных нулей и единиц (подбрасывая симметричную монетку). Их сумма $S_n$ (взятая до номера $n$) будет с.в. со средним $n/2$ и дисперсией $n/4$, а нормированная сумма $\hat{S_n} = (S_n - n/2)/(\sqrt{n}/2)$ при больших $n$ будет практически нормальной с.в. с нулевым средним и единичной дисперсией. Более того, почти наверное

$\limsup \hat{S_n}/\sqrt{\ln\ln n} = \sqrt2.$

Хотелось бы проверить это равенство для самого $\sqrt2$, т.е. для последовательности его цифр в двоичной записи (полученной непосредственно или из записи десятичной).

[Егор]

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

Если всё-таки хочется экспериментально пощупать $\limsup$, то можно, например, рассмотреть последовательность
$\displaystyle b_k=\sup_{2^k\le n<2^{k+1}}a_n.$
Легко видеть, что
$\displaystyle\limsup_{n\to\infty}a_n=\lim_{k\to\infty}b_k.$
Вычисляя значения последовательности $b_k$, можно высказать предположение о том, чему равен её предел.

P. S. Виноват, ошибся. Хотя во многих случаях будет
$\displaystyle\limsup_{n\to\infty}a_n=\lim_{k\to\infty}b_k,$
легко построить последовательность, для которой это не так. Похоже, что нет общего способа выразить $\limsup$ через обычный предел и максимум по конечному множеству.

[geomath]

Егор писал(а):

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

Я думаю, это типичная ситуация для численных методов вообще... так что надо исходить "из прецедентов".

Цитата:

Если всё-таки хочется экспериментально пощупать $\limsup$, то можно, например, рассмотреть последовательность
$\displaystyle b_k=\sup_{2^k\le n<2^{k+1}}a_n.$
Легко видеть, что
$\displaystyle\limsup_{n\to\infty}a_n=\lim_{k\to\infty}b_k.$
Вычисляя значения последовательности $b_k$, можно высказать предположение о том, чему равен её предел.

P. S. Виноват, ошибся. Хотя во многих случаях будет
$\displaystyle\limsup_{n\to\infty}a_n=\lim_{k\to\infty}b_k,$
легко построить последовательность, для которой это не так. Похоже, что нет общего способа выразить $\limsup$ через обычный предел и максимум по конечному множеству.

Да, ничего у меня не получается. Правда, в основном по другой причине. Никак не удается дойти даже до длинного целого n, т.е. до k + 1 = 32, - настолько медленно работает генератор случайных чисел, да и компьютер у меня слабоват. А по тем k, до которых дойти удается, никакой сходимости $b_k$ к корню из двух не наблюдается.