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

[Alexey1]

Не надо её выписывать. Из каждого состояния можно попать только в $n$ состояний с равными вероятностями. Кроме того, в каждое состояние можно попать только из $n$ состояний. То есть сумма по строчкам и сумма по столбцам даст 1, значит матрица является двоякостохастической. А для таких матриц предельные распределения равномерные.

[id]

Цитата:

То есть сумма по строчкам и сумма по столбцам даст 1, значит матрица является двоякостохастической

Это понятно, да.

Но что есть предельные распределения и почему они равномерны (и в каком смысле - равномерны)? И, конечно, следует ли отсюда решение исходной задачи?
(посмотрел в Ширяеве, что был под рукой - сразу не обнаружил ничего похожего; но в английской вики что-то вроде бы есть; это будет, получается, irreducible aperiodic homogeneous chain?)

[Alexey1]

Это можно доказать, а именно, для двоякостохастической, неприводимой и апериодической матрицы с $n$ состояниями, предельные распределения $\pi_i=\frac{1}{n}, \ i=1,...,n$. Это означает, что если процесс перемешивания карт продолжать бесконечно долго, то вероятности нахождения цепи в каждом из состояний равны.

[id]

Гм, но ведь спрашивается про равновероятность некоторых исходов в некоторый определенный конечный момент перемешивания? Или нет?

Хотя мне уже кажется, что я не вполне понимаю формулировку. Если взять за условие именно состояние, когда исходная карта находится на $k$-й позиции (или когда снизу под ней именно эти $k$ карт), то в предельном распределении оно в самом деле будет равновероятно, как Вы и говорите.

В оригинале было

Цитата:

Suppose at some point there are $k$ cards beneath the one that was originally on the bottom of the deck. Given this set of $k$ cards explain why each of the possible $k!$ orderings is equally likely to be the ordering of the last $k$ cards

[Alexey1]

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

[id]

Приведенная формулировка (на англ. которая) есть пункт a); пункт b) есть в оригинале

Цитата:

Conclude that the final ordering is equally likely to be any of n! orderings

То есть все-таки, применимо ли это рассуждения к пунктам а), b)?

[Alexey1]

Считаю, что к пункту б) применимо. С пунктом а) надо отдельно разбираться. А что Вас смущает?

[id]

Меня смущало "Final ordering" и вытекающие отсюда представления о процессе, что он вроде как останавливается.

И казалось, что пункт b) следует из a).

[Alexey1]

Насчёт остановки, ничего не сказано. Если остановим процес после первого вытаскивания карты, то понятно, что утверждение не верно, не могут все состояния быть равновероятностными, например, 2 карта не может оказаться после 3.

[id]

Хм, ну не знаю. "Final ordering". Мне казалось, что процесс повторяется столько, сколько нужно для того, чтобы исходная карта оказалась сверху+1 раз. И все конечные размещения реализуемы.

Само условие в оригинале звучит так:

Цитата:

Consider the following method of shuffling a deck of $n$ playing cards numbered $1$ through $n$. Take the top card from the deck and then replace it so that it is equally likely to be put under exactly $k$ cards for $k=0, 1, \dots,n-1$. Continue doing this operation until the card that was initially on the bottom of the deck is now on top. Then do it one more time and stop.

[Alexey1]

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

[id]

Вот:

Цитата:

Consider the following method of shuffling a deck of $n$ playing cards numbered $1$ through $n$. Take the top card from the deck and then replace it so that it is equally likely to be put under exactly $k$ cards for $k=0, 1, \dots,n-1$. Continue doing this operation until the card that was initially on the bottom of the deck is now on top. Then do it one more time and stop.
a) Suppose that at some point there are $k$ cards beneath the one that was originally on the bottom of the deck. Given this set of $k$ cards explain why each of the possible $k!$ orderings is equally likely to be the ordering of the last $k$ cards
b) Conclude that the final ordering is equally likely to be any of n! orderings
c) Find the expectation ... .

[id]

Гм, так в какую же сторону подумать?
Мне казалось, что надо просто аккуратно выписать условную вероятность, вот только не совсем ясно, по какому условию и как это использовать.

[Alexey1]

Не совсем понятная формулировка. В первой части задачи понятно, что процесс останавливается. Во второй части "Suppose that at some point..." (допустим в какой-то момент времени...), то есть процесс не остановился.
Также обратите внимание, что требуется "explain", а не "prove" или "show". То есть может достаточно просто объяснить, почему должно выполняться утверждение задачи. Что в принципе не сложно, так как все те карты которые находятся под $k$-ой с равной вероятностью могли занять любое место.

[id]

Цитата:

Что в принципе не сложно, так как все те карты которые находятся под $k$-ой с равной вероятностью могли занять любое место.

Здесь я как раз и хотел использовать индукцию. Пусть доказано для $k-1$.
Тогда в момент перед тем, как под исходную карту подложат $k$-ю карту, все $(k-1)!$ размещений равновероятны.

Но это нестрого же, строго - если четко условия записать.

Цитата:

В первой части задачи понятно, что процесс останавливается.Во второй части "Suppose that at some point..." (допустим в какой-то момент времени...)

Видимо, в некоторый момент времени до того, как процесс остановился.