Случайная перестановка.

[kirill94]

Пусть задано некоторое множество ${1, \ldots n}$. Выберем на нем случайную перестановку $\xi$(взаимно-однозначное отображение множества в себя, перестановки равновероятны).

1. Выберем дополнительно случайный элемент $\omega$ из этого же множества и рассмотрим последовательность $\omega, \xi(\omega), \xi^2(\omega), \ldots$. Найти математическое ожидание длины цикла.

Насколько это тривиально? Пока что даже не знаю, в какую сторону думать.

[mihaild]

Начать стоит с выписывания определения мат. ожидания для данного случая и попытки вычислить явно входящие в него величины.

[Munin]

kirill94 в сообщении #1236535 писал(а):

Насколько это тривиально?

Смотря, это для какого класса задача. Для какого она была поставлена?

[Munin]

О!

[kotenok gav]

Munin в сообщении #1236568 писал(а):

О!

И?

[alcoholist]

kirill94
1) Выясните, ЧТО является в данном случае случайной величиной $X_\xi$
2) выясните, какие значения она может принимать $\{k:P(X_\xi=k)\ne 0\}$
3) вычислите эти самые $P(X_\xi=k)$
Hint. От выбора элемента $\omega$ ничего не зависит

-- Сб июл 29, 2017 16:44:48 --

Я так прикинул, получилось $\frac{n+1}{2}$(считая длину тривиального цикла равной 1).

[Munin]

kotenok gav в сообщении #1236604 писал(а):

И?

Я добрался до ответа, и он меня изумил.

[svv]

Аналогично.

[alcoholist]

Munin, svv
я неправильно прикинул?

[svv]

Правильно.

Я понял, откуда сомнения: Вас смутило, что мы испытали изумление, а Вы почему-то нет.

Ну, мне, например, сначала не было очевидно, что искомая вероятность не зависит от длины цикла (для тех длин, которые возможны при данном $n$). Кстати, не случилось ли так, что Вы каким-то образом получили результат, но прошли мимо этого факта?

[alcoholist]

svv в сообщении #1236705 писал(а):

искомая вероятность не зависит от длины цикла

svv в сообщении #1236705 писал(а):

прошли мимо этого факта?

не прошел... когда получилось на бумаге, я хмыкнул, конечно, но особо не удивился)

(Оффтоп)

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

[svv]

alcoholist в сообщении #1236706 писал(а):

я хмыкнул, конечно

Зачёт.