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

[Alexander Evnin]

В начальный момент времени $X=0$. Каждую секунду к $X$ равновероятно прибавляют 1 или $-1$. Найти $E(|X|)$ через $n$ секунд.

Это переформулировка задачи из вступительного экзамена в ШАД 21 мая 2016 г.

Пусть $a_n$ - искомая величина. Я нашёл, что

$$a_{2n+2}=a_{2n+1}=\frac{C_{2n}^n(2n+1)}{2^{2n}}.$$

Для решения задачи понадобилось тождество

$$\sum_{k=0}^nC_{2n+1}^{n-k}(2k+1)=C_{2n}^n(2n+1),$$

обнаруженное с помощью oeis.org.
Наверняка у этой задачи есть короткое комбинаторное решение...

-- 11.05.2019, 21:42 --

ihq.pl
Вы невнимательно прочитали условие!
Речь идёт о модуле с.в.
То, что $E(X)=0$, очевидно. А нужно найти $E(|X|)$.

[Connector]

В обозначениях В. Феллера ожидание равно

$$\sum\limits_{0}^{n}2xp_{n,x}$$

. (Здесь «$p_{n,x}$» — вероятность того, что в момент времени $n$ величина принимает значение $x$) Я ошибаюсь?

[Otta]

Connector
Какая величина?

[Connector]

Цитата:

Какая величина?

Величина $X$. Вероятность того, что модуль $X$ принимает значение $x$ равна сумме вероятности того, что $X$ равна $x$ и того, что $X$ равна $-x$. Две последние вероятности совпадают и равны $p_{n,x}$.

(Считаю, что здесь удобно применить модель случайного блуждания).
UPD Как указал arseniiv, здесь мы и имеем целочисленное случайное блуждание.

[arseniiv]

Не просто удобно, это и есть случайное блуждание по $\mathbb Z$.

[Alexander Evnin]

Connector
Вопрос в том, как свернуть вашу сумму.
И можно ли получить окончательный результат из каких-либо иных комбинаторных соображений?

[Connector]

Как вариант: найти вероятность того, что в момент $n$ значение $X$ лежит между $x$ и $-x$. Обозначим эту вероятность через $p_{x}$; тогда модуль $X$ равен $x$ с вероятностью $p_{x+1}-p_{x}$... Но как найти $p_{x}$ (это ещё, думаю, несложно) и что делать дальше?

[ihq.pl]

Alexander Evnin в сообщении #1392377 писал(а):

ihq.pl
Вы невнимательно прочитали условие!
Речь идёт о модуле с.в.
То, что $E(X)=0$, очевидно. А нужно найти $E(|X|)$.

ой..
Проделал с модулем, взяв за исходное вот это

$$2^nE(|X|) = \sum\limits_{k=0}^m(n-2k)C_n^k + \sum\limits_{k=m+1}^{n}(2k-n)C_n^k, \quad m=\lfloor n/2\rfloor$$

и получил другой результат: если $n=2m$ то

$$E(|X|) = \frac{nC_n^m}{2^n}$$

хотя, надо проверить еще раз...

[ihq.pl]

проверил. Если исходное верно, то всё вроде получается неплохо

$$2^nE(|X|) = nA + 2B,$$

где

$$A = \sum\limits_{k=0}^mC_n^k - \sum\limits_{k=m+1}^{n}C_n^k, \quad B = \sum\limits_{k=m+1}^{n}kC_n^k- \sum\limits_{k=0}^mkC_n^k.$$

Переписываем $A$:

$$A = \sum\limits_{k=0}^mC_n^{m-k} - \sum\limits_{k=1}^{n-m}C_n^{m+k}.$$

Если $n=2m$, то

$$A = C_n^m+\sum\limits_{k=1}^mC_n^{m-k} - \sum\limits_{k=1}^{m}C_n^{m+k}=C_n^m,$$

а $B=0$, потому что

$$B = n\left(\sum\limits_{k=m+1}^{n}C_{n-1}^{k-1}- \sum\limits_{k=1}^mC_{n-1}^{k-1}\right) = n\left(\sum\limits_{k=0}^{m-1}C_{n-1}^{m+k}- \sum\limits_{k=0}^{m-1}C_{n-1}^{m-1-k}\right)$$

[Sergic Primazon]

$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 + ...)$

[ozheredov]

(Оффтоп)

Alexander Evnin я правильно понимаю, что вот такие вот «простенькие» задачки дают на вступительных экзаменах в ШАД? На кого это рассчитано?!

[Pphantom]

(Оффтоп)

ozheredov в сообщении #1392551 писал(а):

что вот такие вот «простенькие» задачки дают на вступительных экзаменах в ШАД? На кого это рассчитано?!

Одномерные дискретные случайные блуждания нередко обсуждают на школьных кружках, для сильных математических и околоСS'ных кружков это почти стандартный элемент.

[ozheredov]

(Оффтоп)

Pphantom Задачи по одномерным дискретным блужданиям, такие как расчёт вероятностей поглощения на границах, не говоря уже о чем то более тривиальном, могу решить даже я. Но вот эта конкретно задача, как мне кажется, это уже перебор в плане сложности. Или нет?

[Alexander Evnin]

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 + ...)$

Я думал в этом же направлении...
Поучительно, как Вы от производящей функции для последовательности $(a_n)$ перешли
к производящей функции для последовательности $(S_n)$, где $S_n=\sum_{k=0}^n a_n$.
Оказывается, достаточно производящую функцию первой последовательности умножить на $\dfrac1{1-x}$.
Спасибо!

-- 13.05.2019, 10:02 --

(Оффтоп)

ozheredov в сообщении #1392574 писал(а):

[off]Pphantom Задачи по одномерным дискретным блужданиям, такие как расчёт вероятностей поглощения на границах, не говоря уже о чем то более тривиальном, могу решить даже я. Но вот эта конкретно задача, как мне кажется, это уже перебор в плане сложности. Или нет?

(Оффтоп)

На вступительных экзаменах в ШАД встречаются и более сложные задачи. Посмотрите, например, на 5 задачу экзамена от 27 мая 2017 г. https://efiminem.github.io/supershad/27-05-2017/ Хотя там ответ получить легко, но сложность решения зашкаливает!

[Alexander Evnin]

Как всё-таки непосредственно доказать тождество

$$\sum_{k=0}^nC_{2n+1}^{n-k}(2k+1)=C_{2n}^n(2n+1)?$$