Мат. ожидание модуля дискретной случайной величины

[ihq.pl]

мог бы предложить самое непосредственное с моей точки зрения док-во. Пусть $A$ - это то, что в тождестве слева. Тогда

$$A=2\sum\limits_{k=0}^{n}(n-k)C_{2n+1}^{k}+\sum\limits_{k=0}^{n}C_{2n+1}^{k}=(2n+1)\sum\limits_{k=0}^{n}C_{2n+1}^{k} - 2(2n+1)\sum\limits_{k=0}^{n-1}C_{2n}^{k}=(2n+1)B$$

Дальше надо воспользоваться тождеством

$$C_{2n+1}^k-C_{2n}^k = C_{2n}^{k-1}$$

[Alexander Evnin]

ihq.pl в сообщении #1392822 писал(а):

мог бы предложить самое непосредственное с моей точки зрения док-во. Пусть $A$ - это то, что в тождестве слева. Тогда

$$A=2\sum\limits_{k=0}^{n}(n-k)C_{2n+1}^{k}+\sum\limits_{k=0}^{n}C_{2n+1}^{k}=(2n+1)\sum\limits_{k=0}^{n}C_{2n+1}^{k} - 2(2n+1)\sum\limits_{k=0}^{n-1}C_{2n}^{k}=(2n+1)B$$

Дальше надо воспользоваться тождеством

$$C_{2n+1}^k-C_{2n}^k = C_{2n}^{k-1}$$

Поясните, пожалуйста, переход

$$2\sum\limits_{k=0}^{n}(n-k)C_{2n+1}^{k}+\sum\limits_{k=0}^{n}C_{2n+1}^{k}=(2n+1)\sum\limits_{k=0}^{n}C_{2n+1}^{k} - 2(2n+1)\sum\limits_{k=0}^{n-1}C_{2n}^{k}$$

[ihq.pl]

Первую сумму в левой части последнего выражения представляем в виде

$$2n\sum\limits_{k=0}^{n}C_{2n+1}^{k} - 2\sum\limits_{k=0}^{n}kC_{2n+1}^{k}$$

и потом преобразовываем член содержащий множитель $k$ под знаком суммы:

$$\sum\limits_{k=0}^{n}kC_{2n+1}^{k} = \sum\limits_{k=1}^{n}kC_{2n+1}^{k} = (2n+1)\sum\limits_{k=1}^{n}C_{2n}^{k-1}.$$

Здесь я использовал тождество

$$kC_n^k = nC_{n-1}^{k-1}$$

[Alexander Evnin]

ihq.pl в сообщении #1392907 писал(а):

Первую сумму в левой части последнего выражения представляем в виде

$$2n\sum\limits_{k=0}^{n}C_{2n+1}^{k} - 2\sum\limits_{k=0}^{n}kC_{2n+1}^{k}$$

и потом преобразовываем член содержащий множитель $k$ под знаком суммы:

$$\sum\limits_{k=0}^{n}kC_{2n+1}^{k} = \sum\limits_{k=1}^{n}kC_{2n+1}^{k} = (2n-1)\sum\limits_{k=1}^{n}C_{2n}^{k-1}.$$

Здесь я использовал тождество

$$kC_n^k = nC_{n-1}^{k-1}$$

Стало понятно. Большое спасибо!

[Random Drifter]

Любопытно, никому не пришло в голову воспользоваться рекуррентной формулой (впрочем, быть может, Sergic Primazon пришло в голову, но я его доказательства не понял).
Формула выглядит так:

$M[|X_{N+1}|]=M[|X_{N}|]+1-2P(X_{N}<0)$

Ее доказательство не то что бы слишком сложное, но довольно громоздкое и состоит из нескольких этапов (у меня, по крайней мере: там еще и для четного, и для нечетного N пришлось по отдельности доказывать). Впрочем, я так думаю, на экзамене доказывать такое обычно и не требуется. Требуется просто знать наизусть подобные формулы.

Дальше надо получить нерекуррентную формулу. Для этого я записываю следующие уравнения:

$M[|X_{2}|]-M[|X_{1}|]=1-2P(X_{1}<0)$\\ $M[|X_{3}|]-M[|X_{2}|]=1-2P(X_{2}<0)$\\ ...\\ $M[|X_{N}|]-M[|X_{N-1}|]=1-2P(X_{N-1}<0)$

Складываю их все и получаю $M[|X_{N}|]-M[|X_{1}|]=(N-1)-2(P(X_{1}<0)+...+P(X_{N-1}<0))$.

Если еще учесть, что $M[|X_{1}|]=1$, окончательно можно записать $M[|X_{N}|]=N-2(P(X_{1}<0)+...+P(X_{N-1}<0))$.

Для симметричного блуждания можно попытаться свернуть эту сумму в замкнутую формулу - если это вообще требовалось по условию данной задачи, в чем я вовсе не уверен.
Заметим, что в силу симметричности блуждания верно

$P(X_{N}<0)=(1-P(X_{N}=0))/2$,

причем, для нечетных индексов $P(X_{N}=0)=0$, для четных индексов $P(X_{N}=0)=\frac{1}{2^N}\binom{N}{N/2}$.
Дальше нужно воспользоваться тождеством $2xf(x)=$$\sum\limits_{k=0}^{x-1}f(k)$$$, где $f(x)=\frac{1}{2^{2x}}\binom{2x}{x}$.
(Тождество легко доказывается по индукции.)

[Random Drifter]

Sergic Primazon, интересно, а с чего вы взяли, что производящей функцией для последовательности $\frac{C_{2k}^k}{4^k}$ будет $\frac{1}{\sqrt{1-t}}$? (Тем более что это не так.)

[RIP]

Random Drifter в сообщении #1570104 писал(а):

Sergic Primazon, интересно, а с чего вы взяли, что производящей функцией для последовательности $\frac{C_{2k}^k}{4^k}$ будет $\frac{1}{\sqrt{1-t}}$? (Тем более что это не так.)

Это так. Проверяется в лоб через бином Ньютона: $(1-t)^{-1/2}=\sum_{k=0}^{\infty}(-1)^k\binom{-1/2}{k}t^k=\sum_{k=0}^{\infty}\frac{C_{2k}^k}{4^k}\,t^k$.

[Random Drifter]

RIP, ладно, вы правы. Должно быть, я где-то ошибся в вычислениях, когда проверял эту функцию.
И да, нашлось готовое тождество $\binom{-1/2}{n}=\frac{-1}{4}^n\binom{2n}{n}$ в книге Арнольда "Конкретная математика", формула 5.37. Хотя я ничего очевидного в нём не вижу. Это тождество относится к каким-то "специальным приемам", конкретно к приёму "выполовинивание". И не сказать, что оно легко доказывается. Можно доказать более-менее коротко. Но Арнольд доказывает с использованием каких-то других тождеств, которые он выводил на предыдущих 10 страницах. Короче, нет тут ничего элементарного.

Самое главное, вопрос остался без ответа: откуда взялась эта производящая функция? Не с потолка же! Я имею в виду, само использование производящих функций предполагает наличие некоего метода получения такой функции из любой последовательности. Допустим, для данной конкретной последовательности существует известная готовая производящая функция. Можно считать, повезло. А в общем случае я угадывать, что ли, должен? Почему бы тогда не "угадать" и не записать сразу готовую формулу, как это сделал я, а потом не предложить просто доказать ее по индукции? К чему это бессмысленное наукообразие?
Формулу хотя бы проверить можно. А как проверить производящую функцию? Можно доказать, что она не верна - если в ряду Тейлора сразу какие-то другие коэффициенты начали получаться. Но чтобы доказать верность, надо проверить бесконечное количество коэффициентов, что в принципе невозможно.

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

[Doctor Boom]

Для больших $n$ вышло $E=\sqrt{\frac{2n}{\pi}}$, интересно та общая формула в пределе к этому стремится

[svv]

Random Drifter в сообщении #1570174 писал(а):

Но Арнольд доказывает с использованием каких-то других тождеств, которые он выводил на предыдущих 10 страницах.

На следующей странице авторы проверяют эту формулу для $n=4$. Проверка подробно расписана, и её легко превратить в короткое доказательство для произвольного натурального $n$.

[Random Drifter]

svv, вы, наверное, не совсем верно меня поняли. С доказательством я уж как-нибудь справлюсь (худо-бедно). Важнее то, откуда взялась эта формула. Я не знаю, кто в здравом уме будет учить такое наизусть - на тот случай, если на экзамене попадется ряд, который надо будет свернуть. Это же не таблица интегралов, всё-таки.

Кстати, в той книге Арнольда (которая, как выяснилось, на самом деле не Арнольда, а Грэхема и Кнута) в седьмой главе есть методы решения рекуррентных уравнений с помощью производящих функций. И там встретился ряд с биномиальным коэффициентом, записанный в довольно общем виде (с параметрами), и соответствующая ему производящая функция: $\[\frac{a}{{{{(1 - \rho z)}^{m + 1}}}} = \sum\limits_{n \ge 0} {\left( {\begin{array}{*{20}{c}} {m + n}\\ n \end{array}} \right)a{\rho ^n}{z^n}} \]$
Написано, что "имеется один вид рациональных функций с особенно хорошими коэффициентами, а именно..." (и приводится эта производящая функция). Видимо, предполагается, что надо подобрать параметры этого общего ряда таким образом, чтобы получился ряд, который требуется свернуть. И сразу получить для него готовую производящую функцию. Вот это уже действительно похоже на метод (типа метода неопределенных коэффициентов - в таком же духе).

Самое забавное, что формулу $(1-t)^{-1/2}=\sum_{k=0}^{\infty}\frac{C_{2k}^k}{4^k}\,t^k$ с помощью этого ряда всё равно не получить! Не прямой подстановкой параметров, во всяком случае. Видимо, опять придется делать "выполовинивание", и т.д. И опять-таки, не знаю, кто станет запоминать всё это наизусть.

$$$***$$$

На всякий случай напишу свой собственный метод, чтобы все оценили его простоту. Пусть имеется ряд $\sum\limits_{k=0}^{n-1}f(k)$, где $f(k)=\frac{1}{2^{2k}}\binom{2k}{k}$, который требуется свернуть в замкнутую форму. Чему он равен, я, предполагается, заранее не знаю. Обозначу $g(n)=\sum\limits_{k=0}^{n-1}f(k)$. Здесь $g(n)$ - это n-я частичная сумма ряда. И действительно, в данном случае она состоит ровно из $n$ слагаемых (хоть это и не принципиально).

Очевидно, что $g(n+1)-g(n)=f(n)$. Это называется линейное неоднородное разностное уравнение первого порядка. Про такие уравнения известно, что в "однородном" случае они решаются легко и просто. Потому что существует метод их решения (и даже не один метод). Про неоднородные же уравнения можно сказать, что общее решение неоднородного уравнения получается как сумма общего решения однородного уравнения и какого-либо частного решения неоднородного уравнения. Однако же общих способов определения частного решения не существует! Не существует или не открыто - точно не знаю, но не буду сейчас на этом останавливаться (это довольно философский вопрос).

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

На самом деле, это не совсем так. Существуют, например, т.н. телескопические ряды, у которых функция $f(n)$ легко "раскладывается" на две половины $g(n+1)-g(n)$. Например, если $f(n)=1/n/(n+1)$, то $f(n)$ можно представить в виде $f(n)=1/n-1/(n+1)$. Конечно, никакого метода перехода к этой формуле нет, о ней нужно просто догадаться (благо, в данном случае это сделать довольно просто). Как нет и метода доказать, что какой-то конкретный ряд является телескопическим - это своего рода искусство. В принципе, любой ряд, чья частичная сумма сворачивается в замкнутую формулу, можно считать телескопическим. Я веду к тому, что функция $f(n)$ может и не быть какого-то конкретного вида, а ряд все равно будет телескопическим. Короче, я собираюсь свернуть этот ряд, не зная заранее, для каких функций $f(n)$ он вообще может быть свернут.

В данном случае я предлагаю попробовать выразить $f(n+1)$ через $f(n)$. А вдруг эта зависимость окажется линейной! Ведь в этом случае ряд можно будет просто свести к сумме геометрической прогрессии. Короче, стоит попытаться выяснить $f(n+1)$, поскольку это самое первое и простое, что вообще можно сделать в данном случае.

Выше я попытался обосновать, почему стоит попробовать получить $f(n+1)$. А теперь непосредственно этим и займусь:
$\[\begin{array}{l} f(n + 1) = \frac{1}{{{2^{2(n + 1)}}}}\left( {\begin{array}{*{20}{c}} {2(n + 1)}\\ {n + 1} \end{array}} \right) = \frac{1}{4}\frac{1}{{{2^{2n}}}}\frac{{(2(n + 1))!}}{{(n + 1)!(n + 1)!}} = \frac{1}{4}\frac{1}{{{2^{2n}}}}\frac{{(2n)!(2n + 1)(2n + 2)}}{{n!n!{{(n + 1)}^2}}} = \\ = \frac{1}{2}\frac{1}{{{2^{2n}}}}\frac{{(2n)!(2n + 1)}}{{n!n!(n + 1)}} = \frac{1}{2}\frac{{(2n + 1)}}{{(n + 1)}}f(n) = \left( {1 - \frac{1}{{2(n + 1)}}} \right)f(n) \end{array}\]$

Легко видеть, что полученное тождество можно переписать в виде:
$\[\begin{array}{l} f(n + 1) - f(n)= \left( { - \frac{1}{{2(n + 1)}}} \right)f(n) \end{array}\]$

Умножаем обе части на $2(n+1)$:
$2(n+1)f(n+1)-2(n+1)f(n)=-f(n)$

Делаем заключительное приведение подобных членов:
$2(n+1)f(n+1)-2nf(n)=f(n)$

Значит, $g(n)=2nf(n)$.

ГОТОВО!!! :)

$$$***$$$

PS

Doctor Boom в сообщении #1570342 писал(а):

Для больших $n$ вышло $E=\sqrt{\frac{2n}{\pi}}$, интересно та общая формула в пределе к этому стремится

Doctor Boom, конечно же нет! Представьте себе блуждающую частицу, которая всегда прыгает только вверх, и никогда - вниз. В этом случае за $n$ шагов она удалится от стартовой точки ровно на расстояние $n$. А значит, и $M[|X|]$ будет равно $n$. Зато можно доказать, что величина $M[|X|]$ будет наименьшей именно в случае симметричного блуждания. Т.е. в общем случае $M[|X|]$ всегда находится где-то между $n$ и $0,8\sqrt{n}$.

[Doctor Boom]

Random Drifter в сообщении #1570587 писал(а):

Doctor Boom, конечно же нет!

Как это нет, когда да Погуглите центральную предельную теорему.

Random Drifter в сообщении #1570587 писал(а):

Представьте себе блуждающую частицу, которая всегда прыгает только вверх, и никогда - вниз. В этом случае за $n$ шагов она удалится от стартовой точки ровно на расстояние $n$. А значит, и $M[|X|]$ будет равно $n$.

Какое это имеет отношение к задаче? У нас частица равновероятностно может прыгать и вверх, и вниз.

Random Drifter в сообщении #1570587 писал(а):

Зато можно доказать, что величина $M[|X|]$ будет наименьшей именно в случае симметричного блуждания.

Так вы уже выше ее "нашли", по какому параметру минимизируете? По вероятности пойти вверх?

Random Drifter в сообщении #1570587 писал(а):

Т.е. в общем случае $M[|X|]$ всегда находится где-то между $n$ и $0,8\sqrt{n}$.

Моя формула точнее приближает минимум

-- 21.11.2022, 03:50 --

Random Drifter в сообщении #1570587 писал(а):

Т.е. в общем случае $M[|X|]$ всегда находится где-то между $n$ и $0,8\sqrt{n}$

Вот вы посчитайте мою

Doctor Boom в сообщении #1570342 писал(а):

$E=\sqrt{\frac{2n}{\pi}}$

там примерно $0.798\sqrt{n}$

[Random Drifter]

Я просто хочу сказать, что для неоднородного разностного уравнения не существует общего метода решения. А значит, угадывать придется в любом случае. Вот только моя догадка гораздо более простая и интуитивно понятная, чем притаскивание сюда за уши "метода" производящей функции. Функция $f(x)=\frac{1}{2^{2n}}\binom{2n}{n}$ состоит из произведения биномиального коэффициента на степень двойки. Биномиальный коэффициент состоит в свою очередь из одних только факториалов, известных своим свойством рекуррентности. Поэтому здесь получается практически одна сплошная рекуррентность, и поэтому просто грех было бы не попытаться выразить f(n+1) через f(n), чтобы потом посмотреть, к чему это приведет. Напротив, производящая функция, даже если она задана в явном, так сказать, эксплицитном виде, даже тогда я не знал, как ее проверить хотя бы, пока мне тут не подсказали. По индукции ее не проверишь, а раскладывать в ряд Тейлора - тоже дело безнадежное, поскольку бесконечное число коэффициентов не проверишь, хоть ты тресни. И откуда ее взять - тоже непонятно. Короче, производящая функция в данном конкретном случае больше мешает, чем помогает.

А тем, кто считает, что метод производящей функции позволяет в общем случае решить неоднородное разностное уравнение, предлагаю попробовать свернуть в замкнутую формулу вот такую сумму: $\sum\limits_{k=0}^{n}\frac{1}{k!}$.

PS
Doctor Boom, тогда я не понял, о чем речь. Какая "та общая формула"? Вот эту свою формулу $M[|X_{N+1}|]=M[|X_{N}|]+1-2P(X_{N}<0)$ я выводил для общего случая. Т.е. она верна и для несимметричного блуждания. 0,8 - это и есть ваше число $\sqrt{\frac{2}{\pi}}$ (мне просто лень было его набивать).

[Doctor Boom]

Random Drifter
Ок, тогда вопросов нет, я просто решал задачу из стартового поста ТС

[Random Drifter]

В одной методичке я видел следующее решение уравнения $g(n+1)-g(n)=f(n)$:

$$g(n)=g(0)+\sum\limits_{k=0}^{n-1}f(k)$$

И ВСЁ! Считается, что этого достаточно. Ничего там дальше сворачивать не требуется. Спрашивается, а зачем же тогда нужны все эти производящие функции, и т.д.? Я так понимаю, только затем, чтобы получить хоть какой-то определенный ответ после записи "$g(n)=$" - хоть сумму, хоть что-то. Хоть в каком-нибудь, но явном виде. Обычно только такой ответ производящие функции и могут предоставить.

Просто когда я вижу вот такое:

Sergic Primazon в сообщении #1392533 писал(а):

$M_{2n+1}=p_0+M_{2n}\ , \ M_{2n+2}=M_{2n+1}\ $ , где $\ p_0=\dfrac{C_{2n}^n}{4^n}$ - вероятность вернуться в $0$.

$$M_{2n+1}=\sum\limits_{k=0}^{n} \dfrac{C_{2k}^k}{4^k}= \dfrac{(2n+1)C_{2n}^n}{4^n}$$

- коэффициент при $t^n$ в разложении $f(t)= \dfrac{1}{\sqrt{1-t}}(1+t+t^2 + ...)$

мне хочется ответить: а сумма $\sum\limits_{k=0}^{n}\frac{1}{k!}$ является коэффициентом при $t^n$ в разложении $\frac{e^t}{1-t}$. Ну и, дальше-то что? Как этот факт поможет мне свернуть эту сумму? Понятно, что никак.

Правда, в случае с последовательностью $\{\dfrac{C_{2k}^k}{4^k}\}$ ее "новая" производящая функция (уже поделенная на $1-t$), судя по всему, связана со своим рядом Тейлора тем же способом, что и "старая" производящая функция: т.е. с помощью бинома Ньютона. Фактически, бином Ньютона - это в данном случае и есть та замкнутая форма, в которую нужно свернуть этот ряд. И только потому это и возможно сделать в данном случае, что эта форма тут имеется. Вот только автор почему-то "забыл" об этом упомянуть. Всё самое важное он опустил или пропустил.

По большому счету, можно было вовсе не морочить голову производящими функциями, а сразу сказать, что $\binom{-1/2}{k}=\frac{-1}{4}^k\binom{2k}{k}$, и поэтому сворачиваемый ряд можно привести к виду \sum\limits_{k=0}^{n}(-1)^k\binom{-1/2}{k}. А это сумма биномиальных коэффициентов. Только не совсем обычная сумма, поскольку коэффициенты берутся от дробного аргумента. Ну и дальше... как-нибудь так?

\[\sum\limits_{k = 0}^n {{{( - 1)}^k}\left( {\begin{array}{*{20}{c}} { - 1/2}\\ k \end{array}} \right)} = \left( {\begin{array}{*{20}{c}} { - 1/2}\\ 0 \end{array}} \right) - \left( {\begin{array}{*{20}{c}} { - 1/2}\\ 1 \end{array}} \right) + \left( {\begin{array}{*{20}{c}} { - 1/2}\\ 2 \end{array}} \right) - \left( {\begin{array}{*{20}{c}} { - 1/2}\\ 3 \end{array}} \right) + ...\]

Не знаю, короче. Я так думаю, что должна быть формула и на этот случай. Даже странно, что Грэхем с Кнутом ее не привели. Если уж вводить биномиальные коэффициенты с дробными аргументами, надо тогда заодно объяснить и как их складывать (кстати, в целочисленном случае тут должен был получиться ноль).


Короче, вы если хотите что-то сказать, то говорите! Почему я каждого должен за язык тянуть в попытке понять, что он имел в виду? Или я должен был сам догадаться, что означает сей коан? (Да, видимо, на то и был расчет.)
Получается как в том анекдоте:

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

Только в данном случае даже не смешно. Потому что складывается превратное впечатление, будто производящие функции являются общим методом свернуть произвольный ряд в замкнутую формулу. (А это не так.)

PS
Ладно, короче. Мне уже надоело мусолить эту тему. И я уже понял всё, что хотел понять. Спасибо всем, кто помогал разобраться!