Необычный предел и бинарная энтропия

[grizzly]

Вводная часть.

Возьмём массив чисел $a[i]^{(0)}(n)=a[i]^{(0)}=C_n^i, i=0,\ldots, n, n\in \mathbb N$. ($(0)$ здесь номер итерации, $C_n^i$ -- число сочетаний из $n$ по $i$).
Преобразуем его по формулам:

$$ a[i]^{(1)}=\frac{a[i]^{(0)}+a[i+1]^{(0)}}{2}, \qquad i=0,\ldots, n. $$

(За границами массива всё равно нулю.) Продолжим аналогичные итерации, пока не получим в первый раз $a[0]^{(k)}<1$. Понятно, что $k$ зависит от $n$. По косвенным аргументам и результатам численных проверок я предполагаю, что предел $k_0:=\lim_{n\to \infty} \frac{k(n)}{n}$ связан с корнем $x_0$ следующего уравнения:

$$ x \log_2 (x) + (1-x)\log_2 (1-x)-x+1=0 $$

таким образом:

$$ k_0=\frac {1}{x_0}-1. $$

(Наверняка это несложно доказать строго, но сейчас вопрос не в этом.)

Суть вопроса.
Теперь я хочу строить итерации чуть иначе, но похожим образом:

$$ a[i]^{(1)}=a[i]^{(0)}\frac{2^i+1}{2^{i+1}}+a[i+1]^{(0)}\frac{2^{i+1}-1}{2^{i+2}}. $$

При больших $i$ это почти то же. Но не при малых. Например, $a[0]$ здесь со временем не уменьшается, а растёт до $2^n$ (весь массив постепенно перетекает в $a[0]$), $a[1]$ медленно уменьшается до 0, а вот $a[2]$, похоже, становится меньше 1 за то же количество шагов (асимптотически), что и в вводной части, то есть аналогичный предел $k_2=\lim_{n\to \infty} \frac{k(n)}{n}$ для него такой же: $k_2=k_0$.

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

[xagiwo]

Предел во вводной части, кажется, не зависит от $i$. Может, во второй тоже? Вроде для этого достаточно $a[i] / a[i+1] = 2^{o(n)}$ (тогда при $a[i+1] \approx 1$ либо $a[i] \approx a[i+1]$ и всё понятно, либо $a[i] >> a[i+1]$, и $a[i]$ каждую итерацию примерно домножается на $\frac{2^i+1}{2^{i+1}}$ и чтобы достигнуть единицы хватит o(n) итераций)

Во вводной части, кстати, $a[i]^{(t)}(n) = C_{n+t}^{i+t}/2^t$ и $a[i]/a[i+1] = \frac{i+t+1}{n-i}$, что стремится к константе при $t \approx k_0n$. При больших $t\; a[i]/a[i+1]$ может быть больше любой функции от $n$, но, думаю, можно принять $t = O(n)$

(Оффтоп)

grizzly в сообщении #1523362 писал(а):

$a[i]^{(0)}(n)=a[i]^{(0)}=C_n^i, i=1,\ldots, n, n\in \mathbb N$

$i$ от 0 до n

[grizzly]

xagiwo в сообщении #1523376 писал(а):

Предел во вводной части, кажется, не зависит от $i$.

Да, конечно.

xagiwo в сообщении #1523376 писал(а):

Может, во второй тоже?

Ну, для $a[1]$ предел будет равен $\log_{4/3}3$, что чуть больше. А вот начиная с $a[2]$ я надеюсь, что не зависит. Но прецедент с $a[1]$ меня смущает (вдруг окажется, что не зависит, но всегда на йоту больше, чем в вводной части).

(Оффтоп)

xagiwo в сообщении #1523376 писал(а):

$i$ от 0 до n

Спасибо, исправил.

[lel0lel]

Можно представить итерационную процедуру в матричном виде $\vec{A}^{(k)}=M^k\vec{A}^{(0)}$. Для первой итерационной процедуры получим что $M$ это $(n+1)\times(n+1)$ матрица с двумя ненулевыми диагоналями, на которых стоят половинки. Например при $n=3$ получим

$$M=\left( \begin{array}{cccc} 1/2 & 1/2 & 0 & 0 \\ 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 1/2 \\ \end{array} \right)$$

Несложно найти замкнутую формулу для $M^k$ (можно использовать теорему Гамильтона--Кэли). Получается что

$$M^k=2^{-k}\left( \begin{array}{cccc} C_k^0 & C_k^1 & C_k^2 & C_k^3 \\ 0 & C_k^0 & C_k^1 & C_k^2 \\ 0 & 0 & C_k^0 & C_k^1 \\ 0 & 0 & 0 & C_k^0 \\ \end{array}\right)$$

Для больших значений $n$ структура матрицы аналогичная. Тогда

$$a_0^{(k)}=\frac{1}{2^k}\sum _{i=0}^{n} \binom{k}{i} \binom{n}{i}=\frac{(k+n)!}{2^k k! n!}$$

Уравнение $\frac{(k+n)!}{2^k k! n!}=1$ можно приближённо решать так: cделаем замену $k=\alpha n$ и раскладываем в ряд в окрестности $n=\infty$, получим:

$$e^{(-\alpha\ln \alpha+(\alpha+1)\ln{(\alpha+1)}-\alpha\ln 2)n}\sqrt{\frac{\alpha+1}{2\pi \alpha n}}=1$$

При $n\to\infty$ корень уравнения относительно $\alpha$ будет бесконечно близок к корню уравнения

$$-\alpha\ln \alpha+(\alpha+1)\ln{(\alpha+1)}-\alpha\ln 2=0.$$

Вроде это согласуется с

grizzly в сообщении #1523362 писал(а):

По косвенным аргументам и результатам численных проверок я предполагаю, что предел $k_0:=\lim_{n\to \infty} \frac{k(n)}{n}$ связан с корнем $x_0$ следующего уравнения:

$$ x \log_2 (x) + (1-x)\log_2 (1-x)-x+1=0 $$

таким образом:

$$ k_0=\frac {1}{x_0}-1. $$

[grizzly]

lel0lel в сообщении #1523394 писал(а):

Вроде это согласуется с

Да, точно!
Спасибо! Красиво получилось: технично и не так уж сложно. Мне это может пригодиться.

[DeBill]

grizzly
1. Для первой задачи:
по набору чисел $\{c_n\}_{n\in \mathbb{Z}}$ составим, как обычно, производящую функцию $ \varphi(x)=\sum\limits_{}^{}c_nx^n$. Тогда, если $\varphi_k$ - производящая для $k$-го набора, то, из правила их формирования имеем: $\varphi_{k+1}(x)=\frac{1+x}{2}\varphi_k(x)$, а $\varphi_0(x)=(1+x)^n$. Значит, $\varphi_k(x)=\frac{(1+x)^{n+k}}{2^kx^k}$. Ейный свободный член равен - как и было показано lel0lel - $\frac{(k+n)!}{2^kk!n!}$. Считая $k$ и $n$ большими, по Стирлингу получим то самое уравнение.
2. Тут все плохо...
Для производящих функций также можно получить уравнение
$\varphi_{k+1}(x)= \frac{1}{2}(\varphi_k(x)+\varphi_k(\frac{x}{2}))+\frac{1}{2x}(\varphi_k(x)-\varphi_k(\frac{x}{2}))$, и $\varphi_0(x)=(1+x)^n$ , но радости от этого - никакой (уж очень плохо они размножаются: оператор "уполовинивания" не коммутирует с оператором умножения)...
Можно посмотреть с другой стороны: это - Марковская цепь (начальные вероятности состояний распределены биноминально, стрелочки - только налево, состояние "0" - сток). Может, отсюда что-то получится? Типа, так: найдем собственный базис для матрицы переходов; разложим начальный вектор состояний по нему; второе собственное значение (первое равно 1, и соответствует стоку) определит асимптотику сходимости...
Я посмотрел начальные векторочки - там непонятно, но красиво:
($v_i$ - собственные вектора, $e_i$ - стандартный базис в $\mathbb{R}^{n+1}$):
$\lambda_0=1, v_0=e_0$

$\lambda_1=\frac{3}{4}, v_1=(-1,1,0,..), e_1=v_1+v_0$

$\lambda_2=\frac{5}{8}, v_2=(2,-3,1,0,...), e_2=v_2+3v_1+v_0$

$\lambda_3=\frac{9}{16}, v_3=(-8,14,-7,1,0...), e_3=v_3+7v_2+7v_1+v_0$

$\lambda_4=\frac{17}{32}, v_4=(64,-120,70,-15,1,0...), e_4=v_4+15v_3+35v_2+15v_1+v_0 $

$\lambda_5=\frac{33}{64}, v_5=(-1024,31\cdot64,-40\cdot31,10\cdot31,-31,1,0...),$
$e_5=v_5+31v_4+5\cdot31v_3+5\cdot31v_2+31v_1+v_0 $

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