Асимптотика для суммы биномиальных коэффициентов

[Хорхе]

Посмотрел методом седловой точки - довольно противно получается, но что-то получается. Если надо, могу написать.

[ewert]

Хорхе в сообщении #402437 писал(а):

Посмотрел методом седловой точки

Да какие ещё перевалы, когда всё вполне очевидно и вещественно.

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

[Хорхе]

(Оффтоп)

Вот обязательно Вам надо показать, что Вы всех умнее.

Я пишу по формуле Коши, оттуда и перевалы:

$$ \frac{1}{2\pi i} \oint \frac{(1+z)^n}{(1-z)z^{[\lambda n]+1}}dz. $$

[ewert]

(Оффтоп)

Хорхе в сообщении #402450 писал(а):

Вот обязательно Вам надо показать, что Вы всех умнее.

Вовсе нет, я просто не понимаю, зачем ломиться в открытую дверь. Всем ежам понятно (не только мне, вообще всем), что если на промежутке $[a;b]$ функция имеет абсолютный максимум в точке $b$, то при интегрировании многократной степени этой функции лишь малая окрестность того максимума и имеет значение. В самой же окрестности существенную роль играет лишь первый член разложения в формулу Тейлора (первый после константы, естественно).

Да, а при чём тут Коши -- и вовсе непонятно. Переход от контура к отрезку -- в любом случае уж как минимум нетривиален.

[Хорхе]

(Оффтоп)

ewert в сообщении #402458 писал(а):

Да, а при чём тут Коши -- и вовсе непонятно.

Даже ежикам, не только мне, понятно
А как вот Вы получаете формулу Стирлинга? Разве не из формулы Коши?

Цитата:

Переход от контура к отрезку -- в любом случае уж как минимум нетривиален.

Мммм. Замена $z=r e^{i\theta}$ лично мне нетривиальной не кажется.

[ewert]

(Оффтоп)

Хорхе в сообщении #402467 писал(а):

А как вот Вы получаете формулу Стирлинга? Разве не из формулы Коши?

Нет, естественно. Чистый метод Лапласа, уж тут-то стерильно чистый. Из интегрального представления факториала (в смысле вообще определения гамма-функции). Всё прозрачно и вполне очевидно.

[Хорхе]

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

Ну ладно, на вкус и цвет товарищей нет. Будет топикстартеру интересно - напишу, что там за перевалы, а эту дискуссию о вкусах предлагаю закрыть.

[ewert]

(Оффтоп)

Хорхе в сообщении #402474 писал(а):

Ну и дверь мне не кажется такой уж открытой.

Куда: в просто Стирлинга?...

$n!=\int\limits_0^{+\infty}x^ne^{-x}dx=\Big[x=nt\Big]=n^{n+1}\int\limits_0^{+\infty}t^ne^{-nt}dt=n^{n+1}\int\limits_0^{+\infty}e^{-n(t-\ln t)}dt\sim\ldots$

дальше надо продолжать?...

Хорхе в сообщении #402474 писал(а):

Допустим, все хорошо.

Не допустим. Сперва надобно задачу поставить. Так что там с верхним пределом суммирования?...

[sup]

Метод с формулой Стирлинга, предложенный ewert, вполне рабочий. Только его надо немножко "подрихтовать". Прежде всего, можно считать, что $k<n/2$. Из всех слагаемых "вытащим" самое большое (последнее) как сомножитель, и суммировать начнем "с другой стороны"
$f(n,k)=C_n^k \sum \limits_{m \leqslant k} \frac {C_n^{k-m}}{C_n^k}$
Легко видеть, что слагаемые в этой сумме мажорируются геометрической прогрессией ${\mu}^m$, где $\mu = k/(n-k)$. Отсюда простая оценка сверху
$f(n,k) < C_n^k /(1- \mu)$. Из это оценки легко вытекает, что в этой сумме играют какую то роль лишь логарифмическое кол-во первых слагаемых (хвост "мал"). Для них уже можно применять асимптотическую формулу для Г-функции, вкупе с фомулой суммирования Маклорена-Эйлера. Занятие утомительное, но для пары членов асимптотики вполне проходимое. Поэтому также согласен с Хорхе - неплохо бы получить интегральное представление и применить метод перевала. Но вот беда, в тех, что у меня получались, присутствует сильная осцилляция - проблемы.

[ewert]

sup в сообщении #402556 писал(а):

Легко видеть, что слагаемые в этой сумме мажорируются геометрической прогрессией

Зачем?... Вполне достаточно того, что все вообще факториалы двусторонне оцениваются формулой Стирлинга. Кроме самого первого слагаемого, но оно не имеет значения.

sup в сообщении #402556 писал(а):

Прежде всего, можно считать, что $k<n/2$.

Нельзя, нужен запас вниз. При $k\sim n/2$ асимптотика всё-таки другая.

sup в сообщении #402556 писал(а):

Занятие утомительное, но для пары членов асимптотики вполне проходимое.

Для пары -- утомительное, для одного -- тривиальное.

[sup]

kavahox в сообщении #402143 писал(а):

Есть Задача: найти хотя-бы первые два члена в асимптотическом ряде $f(n,\lambda n),\; n\to\infty$. Где $0<\lambda<1$

2 ewert
Обращаю Ваше внимание на слова "хотя-бы". Вы предлагаете лишь "главный" сомножитель в искомой формуле. А что дальше? Вот я и предложил, как можно Ваш же подход применить для дальнейших оценок. (Кстати, вместо жутковатых $\lambda^{\lambda}$ и $(1-\lambda)^{(1-\lambda)}$ лучше (да и точнее) использовать просто $C_n^k$)
Оценка сверху нужна лишь для того, чтобы более или менее точно оценить "пренебрежимо малый" кусок ряда, который можно отбросить.
Неравенство $k<n/2$ возникает лишь из соображений симметрии, и соответствует $\lambda <1/2$.
Готов согласиться, что при $k \sim n/2$ ($\lambda =1/2$) асимптотика другая. Для неё надо оценить сумму $\sum \limits_{m=k+1}^{n/2}C_n^m$. (скорее всего аналогично Вашим оценкам)

[kavahox]

ewert в сообщении #402293 писал(а):

Кроме того, тут есть ещё одна проблема. Ведь запись $\sum\limits_{k=0}^{\lambda n}$ -- строго говоря, незаконна, вверху на самом деле целая часть. Пока речь идёт толко о главном члене асимптотики, это не имеет значения. А во втором приближении -- эти перескоки будут давать поправку того же порядка, что и остальные. Так что, строго говоря, непонятно вообще, что имеется в виду под "вторым членом".

Да, на самом деле тут такая петрушка, что $k$ даже может иметь форму $k=\lambda n + \kappa \sqrt{n}$. Тут важно, чтобы $k$ было главным образом порядка $n$. Однако я подумал, что сначала надо хотя-бы эту решить

Хорхе в сообщении #402474 писал(а):

Ну ладно, на вкус и цвет товарищей нет. Будет топикстартеру интересно - напишу, что там за перевалы, а эту дискуссию о вкусах предлагаю закрыть.

Напишите пожалуйста :)

sup в сообщении #402556 писал(а):

Метод с формулой Стирлинга, предложенный ewert, вполне рабочий. Только его надо немножко "подрихтовать". Прежде всего, можно считать, что $k<n/2$. Из всех слагаемых "вытащим" самое большое (последнее) как сомножитель, и суммировать начнем "с другой стороны"
$f(n,k)=C_n^k \sum \limits_{m \leqslant k} \frac {C_n^{k-m}}{C_n^k}$
Легко видеть, что слагаемые в этой сумме мажорируются геометрической прогрессией ${\mu}^m$, где $\mu = k/(n-k)$. Отсюда простая оценка сверху
$f(n,k) < C_n^k /(1- \mu)$. Из это оценки легко вытекает, что в этой сумме играют какую то роль лишь логарифмическое кол-во первых слагаемых (хвост "мал"). Для них уже можно применять асимптотическую формулу для Г-функции, вкупе с фомулой суммирования Маклорена-Эйлера. Занятие утомительное, но для пары членов асимптотики вполне проходимое. Поэтому также согласен с Хорхе - неплохо бы получить интегральное представление и применить метод перевала. Но вот беда, в тех, что у меня получались, присутствует сильная осцилляция - проблемы.

Звучит крайне заманчиво.. но где и как прервать хвост, чтобы не потерять ни одного сушественного члена?

[ИСН]

Последнее "даже может" представляет проблему в радикально новом свете. "Ах да, чуть не забыл - яхта будет использоваться на Юпитере, должна плавать в жидком аммиаке".

[sup]

Ну так об том речь и шла.
$f(n,k)=f(n,l) + \sum \limits_{m=l+1}^{k} C_n^m$
При этом $f(n,l) < C_n^l/(1-\mu)$, где $\mu=l/(n-l)$. При этом $C_n^l <C_n^k\gamma ^{k-l}$, и $\gamma = k/(n-k)=\lambda / (1-\lambda)$.
Пусть нужна ошибка порядка $f(n,k)O(1/n^A)$. Тогда, очевидно, достаточно, чтобы
$\gamma ^{k-l}/(1-\mu) = O(1/n^A)$, а значит $k-l \sim A \ln (n)$
(ну там еще кое что ...). Наверное, нет особого смысла возиться с $\mu$, а достаточно использовать неравенство $\mu < \lambda$. Все это неплохо работает, когда $\lambda$ "заметно" отходит от $1/2$. Для оставшегося куска ряда уже "по Стирлингу". Результат должен получиться примерно как и указывал ewert. Отклонение от интеграла - формула Маклорена-Эйлера. Повозиться придется, но вроде бы работа обозримая. Я ожидаю, что получится что-то типа $f(n,k)=C_n^k(a_0(n,\lambda) +a_1(n,\lambda)/n + ...)$, где все $a_j(n,\lambda)$ уже более или менее "аналитические".
К слову сказать, с изумлением обнаружил, что эти суммы как и биномиальные коэффициенты удовлетворяют тождеству $f(n,k)=f(n-1,k-1) + f(n-1,k)$. Но вот пристроить это дело куда-нибудь не сумел.

[Хорхе]

kavahox в сообщении #402631 писал(а):

Да, на самом деле тут такая петрушка, что $k$ даже может иметь форму $k=\lambda n + \kappa \sqrt{n}$.

Нет, Вы уж определитесь, это очень существенно. Не хочется писать что-то впустую, тем более, что тут это довольно муторно.