(по мотивам предыдущей задачи, только с другим вопросом)

Есть выборка $%\{a_1, a_2, ..., a_n\}$% из $%n$% различных объектов. Из нее составляют новую выборку размера $%n$% поочередно беря и копируя элементы из старой выборки в новую выборку. Элементы из старой выборки берутся с возвращением, т.е. в новой выборке могут быть повторы.

Вопрос: какое ожидаемое число различных элементов в новой выборке?

задан 4 Сен 23:16

изменен 4 Сен 23:17

1

Будет $%n\left(1-\left(1-\frac{1}{n}\right)^{n}\right)$%, т.е. в $%n$% раз больше вероятности того, что $%a_1$% появится в новой выборке. Тот же метод.

(4 Сен 23:53) Rene

@Rene, какие индикаторы в данной задаче? в предудщей было $%I(a_i)$% - индикатор того что $%a_i$% уникален. И это значило что надо найти $%E[I(a_1) + ... + I(a_n)]$%, а как здесь?

(5 Сен 0:34) Квантиль
1

@Квантиль: разница только в том, что при уникальности мы сравнивали a(i) со всеми остальными, а при новизне сравниваем только с предыдущими.

(5 Сен 0:49) falcao
10|600 символов нужно символов осталось
2

Да, ответ именно такой, как у @Rene, и всё делается схожим способом. Но я хочу для начала "причесать" формулировку. Прежде всего, есть алфавит из n символов. Вряд ли его следует называть "выборкой". Далее формируется случайная строка из n символов, где на каждом шаге случайно и независимо выбирается один из символов алфавита с равной вероятностью. Такой объект выборкой называть уже правомерно, хотя я бы не стал (это обычный случайный вектор, не более того). И вот про такой объект мы спрашиваем, сколько в нём в среднем будет различных символов задействовано.

Здесь также полагаем X(i)=1, если i-й символ в строке является новым, то есть не равным никакому из предыдущих; в противном случае X(i)=0. Ясно, что нас интересует MX, где X=X(1)+...+X(n). Достаточно найти MX(i)=P(X(i)=1). Эти величины уже не будут одинаковыми. Но подсчёт простой: фиксируем i-й символ, и находим вероятность того, что ни один предыдущий ему не равен. Ясно, что будет q^{i-1}, где q=1-1/n. Тогда MX есть сумма геометрической прогрессии 1+q+...+q^{n-1}=(1-q^n)/(1-q)=n(1-(1-1/n)^n), то есть примерно n(1-1/e), хотя это приближение и не совсем точное ввиду наличия умножения на n. Разница, правда, невелика, и примерно равна 1/(2e).

ссылка

отвечен 5 Сен 0:48

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,353
×1,462

задан
4 Сен 23:16

показан
54 раза

обновлен
5 Сен 0:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru