[Trotil]

Придумал задачу.

Пусть имеется N различных пронумерованных от 1 до N камней в ящике.
Человек за один ход вытаскивает 1 случайный камень, кладёт обратно, записывает его номер. Если его номер был записан ранее, ничего не записывает.
Игра прекращается, когда человек выпишет все номера от 1 до N.
Найти вероятность победить на i-том ходе.
Найти матожидание количества ходов до остановки игры.


У меня получился ответ (в комментариях). Хочется узнать, правильный ли он.

@темы: Теория вероятностей, Порешаем?!

Comments

[Trotil]

Хотя очевидно, что неправильный - дробь стремится к нулю.

Но ошибки пока не вижу.

Ошибка была в коэффициенте. Но ткперь матожидание - бесконечность.

[вейко]

матожидания чего?

[Trotil]

количества ходов до вытаскивания всех камней хотя бы по одному разу.

[вейко]

1+n/(n-1)+n/(n-2)....+n
вроде так

[All_ex]

вейко так количество ходов в описанном процессе может быть бесконечно...

[вейко]

All_ex, ну да оно может быть бесконечно и при 2 камнях
и что?
вы имеете ввиду сложность расчета?

[All_ex]

Я как бы спросил, что такое `n`... И вроде спросил глупость - это число камней написанное маленькой буквой...
Но не понятны рассуждения приведшие к такой сумме...

[All_ex]

А сумма таких вероятностей будет равна 1?

[_ТошА_]

Ой, это я не то набрал, там поделить надо. А то вероятность больше единицы у меня вылезла.

[вейко]

пусть n=2 на втором ходу закончить вероятность 0,5
а у тебя 2/3

[Trotil]

Вот мое выражение для суммы, но оно расходится при n=3 и выше:

sum(k*n!/n^n * (1/n+2/n+...(n-1)/n)^(k-n),k=n..infinity)

[Trotil]

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



Каждая стрелочка - это один ход.
Завершить игру можно за n ходов, двигавшись всё время вправо.
А можем где-нибудь застрять, и вытащить камень, который у нас уже есть. Это петля.

А матожиданию по картинке соответствует формула выше, но она расходится.
Ошибка либо в картинке, либо в формуле, либо еще в чём-то.

[_ТошА_]

бред

[_ТошА_]

бред

[All_ex]

А если зацикливание на месте более продолжительное?...

[Trotil]

All_ex, а там степень ведь. Степень = 3 - зацикливание 3 раза в любом месте.

[All_ex]

_ТошА_ Я так понимаю `(N!)/(N^N)*sum_(k = N)^(oo) C_(k)^(k - N)` это сумма вероятностей? но она `!=1`.

[_ТошА_]

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

[All_ex]

Картинка логичная, но имел ввиду зацикливание на одном месте...По моему вероятность сделать `n`попыток вычисляется так
`P(X=n) = sum_(k_1+...+k_{N-1} = n-N} (N/N)*(1/N)^{k_1}*((N-1)/N)*(2/N)^{k_2}*...*((N-1)/N)^{k_{N-1}}*(1/N)`, естественно, что`k_i>=0`

[Trotil]

Я еще завтра подумаю.

[All_ex]

Но возможно я потерял `N!`...

[CD_Eater]

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

[All_ex]

CD_Eater открытие первого нового камня И открытие второго нового камня с момента открытия первого...
Насколько я понимаю это так... НО "И" - это логическое произведение., а матожидание произведения зависимых событий не равно произведению матожиданий...
или я не прав?...

[CD_Eater]

представьте, что игра состоит из n последовательных игр

[All_ex]

CD_Eater Наверное, Вы правы...
но интересно как это посчитать в лоб при помощи вероятностей...

[CD_Eater]

пожалейте свой лоб и считайте как проще

[Trotil]

CD_Eater, я добавил пункт про вероятность победы на i-том ходе.

All_ex, а у нас одно и тоже написано!

Пусть, например, n-N=2
Тогда будут всевозможные множители (i/N)*(j/N) - N^2 штук
они же получаются, если раскрыть скобки в (1/N + ... (N-1)/N)^2.

_ТошА_, у тебя биномиальная сумма расходится.

[All_ex]

они же получаются, если раскрыть скобки в (1/N + ... (N-1)/N)^2.

Trotil Но у меня эти множители стоят в со множителем 1, а у Вас с коэффициентами, возникающими при раскрытии "бинома"...

[Trotil]

удалено

[Trotil]

Да...
А какой вариант правильный?
Вот мы можем заскочить в i-тую петлю, затем в j-тую, если i < j.
А вот сначала в j-тую, затем в i-тую - не можем, так как возврата нет.
Да, действительно, только один раз.
Отлично.

Теперь встаёт задача свернуть эту сумму.