Happy Meal

и задачки для интервью.
Forum rules
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Happy Meal

Post by venco »

В каждом из Хэппи Милов - по одной игрушке из N вариантов, равномерно случайно.
Покупаем их по одному, пока не соберём все N разных игрушек.
Сколько в среднем придётся купить Хэппи Милов?
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Re: Happy Meal

Post by Ворона »

venco wrote:В каждом из Хэппи Милов - по одной игрушке из N вариантов, равномерно случайно.
Покупаем их по одному, пока не соберём все N разных игрушек.
Сколько в среднем придётся купить Хэппи Милов?

venco, у Вас условия, как всегда, которые я догоняю не сразу. Разве это отличается от получения N одинаковых игрушек ?
Тогда это – всего лишь Negative binomial distribution и его mean равен N(N-1).
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

А меня такие вопросы ставят в тупик. :)
Та же задача математическим языком:
есть последовательность Xk (k>=1) независимых равномерно случайных целых чисел из [1,N]. Вычислить среднее значение минимального числа T, такого, что для любого целого A из [1,N] найдется k из [1,T], для которого Xk = A.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Да, забыл сказать, что ваш ответ неверен.
Top
voyager
Новичок
Posts: 99
Joined: 06 Feb 2007 05:22
Location: 1980-s

Post by voyager »

1+N*[1/(N-1) + 1/(N-2) + ... +1]
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

venco wrote:А меня такие вопросы ставят в тупик. :)

Виноват...
Но вряд ли исправлюсь.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

[quote="voyager"][/quote]
Правильно.
Top
User avatar
FireFox
Уже с Приветом
Posts: 317
Joined: 09 May 2005 13:49
Location: US

Re: Happy Meal

Post by FireFox »

Ворона wrote:
venco wrote:В каждом из Хэппи Милов - по одной игрушке из N вариантов, равномерно случайно.
Покупаем их по одному, пока не соберём все N разных игрушек.
Сколько в среднем придётся купить Хэппи Милов?

venco, у Вас условия, как всегда, которые я догоняю не сразу. Разве это отличается от получения N одинаковых игрушек ?
Тогда это – всего лишь Negative binomial distribution и его mean равен N(N-1).

Почему binomial??
Здесь возможных исходов у каждого эксперимента не 2, а N (может выпасть любая из N игрушек!).

Распределение всех возможных исходов k экспериментов это multinomial distribution, а не binomial.

Т.е. распределение числа k экспериментов до достижения определенной конфигурации описывается чем-то вроде "negative multinomial distribution" :mrgreen:
Top

Return to “Головоломки”