Стопка карт (теор. вер)

[id]

Есть стопка из $n$ карт, пронумерованы снизу от $1$ до $n$.

На каждом шаге берут карту сверху и вставляют её в любое из $n$ мест в колоде (т.е. она может остаться и на месте, и в самом низу) с равной вероятностью.
Это продолжается до тех пор, пока карта снизу не окажется на самом верху колоды.

Требутся найти мат. ожидание числа операций указанного типа необходимых для этого.


Ясно, что минимальное число операций равно $n-1$, и это можно осуществить только одним способом.
Несколько труднее посчитать для $n$ - но тоже можно (тут надо выбрать карту, которая оказывается над нижней после "вставки"; для разных карт будут разные вероятности).
И как вывести общую формулу - не совсем понятно.

Может быть, есть какой-нибудь удобный для этого прием?

[ИСН]

Интересующая нас карта либо перемещается вверх, либо стоит на месте? Какая-то нехитрая рекуррентная формула должна получаться. Матожидание для n-1 плюс что-то там.

[Alexey1]

Попробуйте использовать формулу $E[N_n]=E[N_n|A]P(A)+E[N_n|\bar A]P(\bar A)$, где $N_n$ - число операций когда в колоде $n$ карт, а $A$ - событие состоящее в том, что верхнюю карту положили на место первой.

[--mS--]

id в сообщении #350176 писал(а):

Может быть, есть какой-нибудь удобный для этого прием?

Безусловно. Сначала ждём, пока нижняя карта не окажется второй снизу. Для этого нужно, чтобы какая-то из поднятых карт легла на $n$-е место. Вероятность успеха в каждом из независимых испытаний - $1/n$, среднее время ожидания этого события - $n$. Дальше ждём, пока вторая снизу карта не станет третьей снизу. Для этого нужно, чтобы какая-то из поднятых карт легда на места $n-1$ и $n$. Среднее время ожидания этого события есть $n/2$. Ну и т.д.

[lel0lel]

Я так посчитал: минимальному числу карт соответствует вероятность $P (k = 0) = n^{-n + 1} (n - 1)!$ здесь k - число карт, вытащенных вхолостую. Тогда $P(1)=P (0) \left({1\over n} + {2\over n} + ... + {n -1\over n}\right) = {n - 1\over2} P (0) $.
Далее $P (2) = P (0)\left (\frac {\left ({1\over n} + {2\over n} + ... + {n - 1\over n} \right)^2} {2} + \frac {1} {2}\sum\limits_ {i = 1}^{n - 1}\frac {i^2} {n^2} \right) = P (0)\left (\frac {1} {4} (n - 1)^2 + \frac {(2 n - 1) (n - 1)} {12 n} \right) $.
Общая формула :

$$P (k) = P (0)\sum\limits _ {c (0) = 0}^ k\sum\limits_ {c (1) = 0}^{k - c (0)} ...\sum\limits _ {c (n - 2) = 0}^{k - \sum\limits _ {j = 0}^{n - 3} c (j)}\prod _ {i = 1}^{n - 2}\left(\frac {i} {n} \right)^{c (i)}\left(\frac {n - 1} {n} \right)^{k - \sum\limits _{j = 0}^{n - 2} c (j)} $$

Мат ожидание: $M=\sum\limits_{k=0}^{\infty} (n-1+k) P(k)$.
Случай $n=2$ легко посчитать без машины, соответствующее мат. ожидание равно $2$.
Для $n>2$ удобно воспользоваться ЭВМ. Если я не проврался, то имеют место быть следующие результаты: $M_{n=3}=4.5$, $M_{n=4}=\frac{22}{3}$, $M_{n=5}=10.416$, $M_{n=6}=13.697$.

[ИСН]

--mS-- сказал то же самое, только не устраивая нагрузочного тестирования для редактора формул.

[Alexey1]

А почему нельзя через условные математические ожидания?

[id]

Гм, странно, я попробовал делать примерно по методу Alexey1 и получил формулу $\mathbb E [n] = \mathbb E[n-1] + n$. Неужели наврал?

Это исходя из того, что
$\mathbb E [n] = (\frac 1 n (\mathbb E [n-1]+1) + \frac {n-1} n \frac 1 n (\mathbb E[n-1] +2) + (\frac {n-1} n)^2 \frac 1 n (\mathbb E[n-1] +3)+\dots)$

[lel0lel]

Да у меня такая же формула вначале получалась, но тут такая тонкость, что $\mathbb E[n-i]$ в формуле
$\mathbb E [n] = (\frac 1 n (\mathbb E [n-1]+1) + \frac {n-1} n \frac 1 n (\mathbb E[n-1] +2) + (\frac {n-1} n)^2 \frac 1 n (\mathbb E[n-1] +3)+\dots)$
это мат. ожидания числа операций не колоды из $n-i$ карт, а колоды из тех же $n$ карт, только требуемая карта снизу $i+1$.

Как верно заметил ИСН, способ --mS-- простой и позволяет несложно считать требуемые мат. ожидания, без использования подручных средств .

[Alexey1]

Здесь действительно надо быть аккуратнее. Используем формулу $E[N_n]=E[N_n|A]P(A)+E[N_n| \bar A]P(\bar A)$. Но запись $E[N_n]=(1+E[N_{n-1}])P(A)+(1+E[N_n])P(\bar A)$ не правильная, так как $E[N_{n-1}]$ это математическое ожидание сделанных операций пока нижняя карта не будет на верху в колоде из $n-1$ карты, но в задаче количество карт $n$.
Поэтому для удобства, пусть $N_n^{n-k}$ - количество сделанных операций если требуемая карта находится на $n-k$-ом месте в колоде из $n$ карт (нумерация сверху вниз). Тогда $E[N_n^n]=(1+E[N_n^{n-1}}])\frac{1}{n}+(1+E[N_n^n])\frac{n-1}{n}$. Отсюда получаем $E[N_n^n]=E[N_n^{n-1}]+n$ и в общем виде $E[N_n^{n-k}]=E[N_n^{n-(k+1)}]+\frac{n}{k+1}$ и $E[N_n^2]=\frac{n}{n-1}$. Используя все эти формулы получаем $E[N_n^n]=\sum\limits_{k=1}^{n-1}\frac{n}{k}$.

[id]

Хорошо, теперь понятно. Спасибо!

Пара доп. пунктиков. Пусть теперь после того, как исходная карта оказывается на верхушке, ее втыкают в случайное место в колоде (т.е. как на предыдущих шагах).

а) Пусть на определенном шаге под исходной картой $k$ карт. Показать, что все $k!$ размещений равновероятны.

Тут можно вроде как по индукции.
Основание индукции - для $k=2$.
Но вот по какому условию следует брать условные м.о.?
$P(X_1 | (X_1 \cup X_2)) = P(X_2 | (X_1 \cup X_2))$, где $X_1$ - событие "под исходной картой упорядочено лежат карты $a, b$", $X_2$ - событие "под исходной картой упорядочено лежат карты $b, a$"?

Ну и далее - пусть доказано для $k-1$, но условие тут тоже нужно какое-то брать.

б) Показать, что все $n!$ конечных размещений равновероятны.
Это следует из пункта 1.
Все $(n-1)!$ размещений равновероятны перед тем, как исходную карту поместят куда-то в колоде.

[Alexey1]

А через цепи Маркова не пробовали?

[id]

Гм, нет (в этом примере вроде бы не считается, что они неизвестны, хотя...); утверждение-то кажется интуитивным.

А это что-нибудь даст? То есть надо для начала построить эту самую цепь Маркова (пока не вижу, какие $\xi_n$ следует брать и как будет вытекать отсюда марковское свойство); и использовать какое-то специальное свойство?

[Alexey1]

В качестве состояний можно взять все возможные комбинации, то есть $n!$ состояний. Затем, составить матрицу переходных вероятностей, она должна быть простой. Ну и посмотреть на предельные распределения.

[id]

Цитата:

посмотреть на предельные распределения.

Что Вы имеете ввиду?

Я как понял, Вы предлагаете выписать матрицу $(p_{ij})$ размером $n! \times n!$ (у которой в ячейках будут $0$ либо $\frac 1 n$), сколько-то раз ее скомпонировать с собой, и ... .