|
(по мотивам предыдущей задачи, только с другим вопросом) Есть выборка $%\{a_1, a_2, ..., a_n\}$% из $%n$% различных объектов. Из нее составляют новую выборку размера $%n$% поочередно беря и копируя элементы из старой выборки в новую выборку. Элементы из старой выборки берутся с возвращением, т.е. в новой выборке могут быть повторы. Вопрос: какое ожидаемое число различных элементов в новой выборке? задан 4 Сен '21 23:16 
Квантиль |
|
Да, ответ именно такой, как у @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 Сен '21 0:48 
falcao |
Будет $%n\left(1-\left(1-\frac{1}{n}\right)^{n}\right)$%, т.е. в $%n$% раз больше вероятности того, что $%a_1$% появится в новой выборке. Тот же метод.
@Rene, какие индикаторы в данной задаче? в предудщей было $%I(a_i)$% - индикатор того что $%a_i$% уникален. И это значило что надо найти $%E[I(a_1) + ... + I(a_n)]$%, а как здесь?
@Квантиль: разница только в том, что при уникальности мы сравнивали a(i) со всеми остальными, а при новизне сравниваем только с предыдущими.