Игра с карточками

[Guliashik]

Есть $n$ типов карточек. Самих карточек бесконечно много. Будем строить последовательность из карточек следующим образом. Известны вероятности $b_i$ того, что первой в последовательности будет карточка типа $i$. Также известны условные вероятности того, что если предыдущая карточка типа $i$, то карточка типа $j$ появляется с вероятностью $q(x_{k}=j|x_{k - 1}=i)$ (безразлично на какой позиции). Если в последовательности появилась карточка типа $n$, то генерация последовательности прекращается.

Найти математическое ожидание длины последовательности.

Как найти вероятность того, что последовательность заканчивается в позиции $k$ типом $j$, вроде бы понятно.
$P_{k,j}=\sum \limits_{i} (P_{k-1,i}\cdot q(x_{k}=j|x_{k-1}=i))$
Но возникает ситуация, когда условные вероятности того, что карточка типа $n$ появится следующей, очень малы. Очевидно что ожидание будет бесконечно большим. И простой подсчёт ожидания на компьютере будет давать, наоборот, малые величины. Как понять когда ожидание бесконечно, а когда конечно?

P.S. Если вероятность просчитывается не так, то просто скажите что, мол, не так. Только не пишите формулы, пожалуйста. Хочу сам найти, в таком случае, ответ.

[svv]

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

[provincialka]

Guliashik в сообщении #853461 писал(а):

Но возникает ситуация, когда условные вероятности того, что карточка типа $n$ появится следующей, очень малы. Очевидно что ожидание будет бесконечно большим.

Что значит "возникает ситуация"? После нескольких шагов, что ли? Или с самого начала?
Если вероятности уменьшаются с увеличением числа шагов, это означает, что ряд, порождающий матожидание, сходится.

[Shadow]

Если правильно понял условие, задачу можно решить с помощью системмы из n уравнений с n неизвестными. (если повезет, совместимая). Неизвестные - $M_k$ - мат ожидание длины после того, как выбрана карточка типа "k". Даны $q_{ij}$ - вероятность выбрать карточку типа j, если предыдущая карточка типа i.

$\\M_n=b_1(1+M_1)+b_2(1+M_2)+\cdots +b_{n-1}(1+M_{n-1})+b_n\\ M_1=q_{11}(1+M_1)+q_{12}(1+M_2)+\cdots +q_{1n}\\ \cdots $

UPD будет совместимая

[Guliashik]

provincialka, с самого начала.

[Shadow]

не будет совместимая, если $q_{ii}=1$ или да, когда есть возможность попасть в петлю.

[Guliashik]

Странно. Рассчитываю по приведённой мною формуле $P_{k,i}$, и они после некоторого числа шагов становятся больше 1.

[svv]

Наверное, это означает, что событие более чем вероятно.

[--mS--]

А Ваши вероятности в сумме $\sum_{j=1}^n q_{ij}$ (при каждом отдельном $i$) единицу дают? Или больше?

[Guliashik]

svv, --mS--, сумма была больше единицы:)

[mustitz]

Guliashik в сообщении #853461 писал(а):

Но возникает ситуация, когда условные вероятности того, что карточка типа $n$ появится следующей, очень малы.

Обычно логарифмы суммируют, например, в байесовских сетях