2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 limsup
Сообщение04.12.2006, 15:50 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Скажите, как подсчитать на компьютере верхний предел случайной числовой последовательности?

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

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

 Профиль  
                  
 
 
Сообщение04.12.2006, 19:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: limsup
Сообщение05.12.2006, 02:41 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение05.12.2006, 15:16 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Из закона повторного логарифма следует, что верхний предел некоторым образом нормированной суммы случайной последовательности нулей и единиц равен с вероятностью 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$, т.е. для последовательности его цифр в двоичной записи (полученной непосредственно или из записи десятичной).

 Профиль  
                  
 
 
Сообщение05.12.2006, 17:26 


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

Если всё-таки хочется экспериментально пощупать $\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$ через обычный предел и максимум по конечному множеству.

 Профиль  
                  
 
 
Сообщение08.12.2006, 15:32 
Аватара пользователя


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

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

Цитата:
Если всё-таки хочется экспериментально пощупать $\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$ к корню из двух не наблюдается. :(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group