Матожидание числа различных результатов

Ian · Сообщение **Ian** » 01 апр 2020, 18:23

Некоторое испытание может давать n равновероятных результатов. Проводится n испытаний. Пусть k-случайная величина, число различных результатов в n испытаниях . Найти матожидание отношения k/n
Для n=100 сегодня задача об этом была предложена на некоторой IT- олимпиаде. Может, хотели чтобы численно нашли. У меня ответ 0,6339676587
А как она ведет при n, асимптотика, форма распределения

zykov · Сообщение **zykov** » 01 апр 2020, 21:00

Можно решать через Марковские процессы, аналогично теме Вероятность определённой последовательности.
Пусть у нас вектор $p$

- вектор длины 100 содержащий вероятности того что было такое-то количество различных результатов.
После первого испытания у нас 100% вероятности, что есть ровно 1 различный результат. Т.е. вектор везде равен нулю, кроме первого элемента равного единице (вектор $p_1$

).
Если после какого-то количества испытания у нас $m$

разных результатов, то после ещё одного испытания будет $m$

разных результатов с вероятность $m/n$

, и будет

разных результатов с вероятность $(n-m)/n$

.
Т.е. столбец вектор $p$

слева умножается на матрицу $A$

, в которой ненулевые только главная диагональ и её соседняя диагональ снизу.
$A_{i,i}=\frac i n$
$A_{i+1,i}=\frac {n-i} {n}$

После 100 испытаний вектор вероятностей будет:
$p_{100}=A^{99}p_1$
Зная вектор вероятностей легко найти матожидание количества $k$

- просто умножить его слева на строку $(1,2,...,100)$

.
(Видимо то, что имелось ввиду на IT- олимпиаде.)

zykov · Сообщение **zykov** » 01 апр 2020, 21:51

В Maxima посчитал точное значение матожидания количества $k$

(точная десятичная дробь):

Код: Выбрать все

63.396765872677049506938397342748261381028792336107630859404262730068295524927525181280345648997304959933843089934715672528176430319820058414289464550829242572610964993901729162885021780083239150509999

zykov · Сообщение **zykov** » 01 апр 2020, 23:42

Забавно. Получилось найти точную формулу.
Матожидание $k/n$

точно равно $1-(1-\frac 1 n)^n$ .

Матрица $A$

имеет простые собственные значения и собственные вектора.
Собственные значения: 1, $(n-1)/n$

,

, ...,

.
Им соотвествуют собственные вектора с ненулевыми значениями в конце равными биномиальным коэффициентам $(1-1)^{l-1}$ .
Например первый вектор в конце имеет 1. Второй имеет (1, -1). Третий - (1, -2, 1). Четвертый - (1, -3, 3, -1). И т.д..
Удобно, чтобы знак единицы в последней строке чередовался. Тогда, если объединить эти столбцы в матрицу $V$

, то ей обратная матрица $V^{-1}$ тоже имеет простую форму. Её первый столбец состоит из биномиальных коэффициентов $(1+1)^{n-1}$ . Начало второго столбца состоит из биномиальных коэффициентов $(1+1)^{n-2}$ . И т.д.. Последний столбец имеет только один ненулевой элемент - 1 в начале.

Умножение столбца $p_1$

слева на матрицу $V^{-1}$ даёт её первый столбец - столбец состоящий из биномиальных коэффициентов $(1+1)^{n-1}$ .
Интересно, что умножение строки $(1, 2, 3, ..., n)$

справа на матрицу $V$

даёт строку в которой только первые два элемента ненулевые и равны $(n, -1)$

.
Это позволяет найти точный ответ для матожидания количества разных результатов в виде:
$\begin{pmatrix} n & -1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 \\ 0 & (1-\frac 1 n)^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1 \\ n-1 \end{pmatrix}$

zykov · Сообщение **zykov** » 01 апр 2020, 23:50

Ian писал(а):Source of the post А как она ведет при n, асимптотика, форма распределения

В пределе, понятно, будет $1-e^{-1}$ .
Ряд Лорана на бесконечности будет $1-e^{-1} + \frac 1 {2 e n} + \frac 5 {24 e n^2} + \frac 5 {48 e n^3} + O(n^{-4})$ .

zykov · Сообщение **zykov** » 02 апр 2020, 00:00

zykov писал(а):Source of the post Матожидание точно равно $1-(1-\frac 1 n)^n$ .

Вот вопрос, как просто найти этот простой ответ?

Ian · Сообщение **Ian** » 02 апр 2020, 00:03

zykov писал(а):Забавно. Получилось найти точную формулу.
Матожидание точно равно $1-(1-\frac 1 n)^n$ .

Особенно забавен путь которым она найдена. Должно же быть вероятностное доказательство этого.
Также дисперсию распределения k считаю численно, она в разы меньше чем у биномиального распределения с таким матожиданием (пик острее)
P.S.
Это можно принять за определение числа e: пусть разбрасывается огромное число n предметов по n ячейкам: ожидаемое отношение n к числу пустых ячеек

zykov · Сообщение **zykov** » 02 апр 2020, 00:47

Ian писал(а):Source of the post Также дисперсию распределения k считаю численно, она в разы меньше чем у биномиального распределения с таким матожиданием (пик острее)

Через матрицу можно посчитать матожидание для $k^2$

. Получается:
$-2 {{( 1-\frac{1}{n}) }^{n}}\, {{n}^{2}}+{{( 1-\frac{2}{n}) }^{n}}\, {{n}^{2}}+{{n}^{2}}+{{( 1-\frac{1}{n}) }^{n}} n-{{( 1-\frac{2}{n}) }^{n}} n$

Отсюда для дисперсии $k/n$

получается:
$\frac{{( 1-\frac{1}{n})^{n} - ( 1-\frac{2}{n})^{n}}}{n}-{{( 1-\frac{1}{n}) }^{2 n}}+{{( 1-\frac{2}{n}) }^{n}}$
(примерно $10^{-3}$ при $n=100$

.)

Ряд Лорана на бесконечности:
$\frac{e - 2}{e^2 n} - \frac{e - 3}{2 e^2 n^2} + \frac{16 - 5 e}{24 e^2 n^3} + \frac{22 - 5 e}{48 e^2 n^4} + O(n^{-5})$
(Т.е. примерно $0.1n^{-1}$ .)

zykov · Сообщение **zykov** » 02 апр 2020, 09:25

Ian писал(а):Source of the post Должно же быть вероятностное доказательство этого.

Ну это доказательство вполне вероятностное...
Исходя из вероятностных рассуждений мы получили связь в матричной форме. Потом провели алгебраические преобразования в этой форме. Интересно, что результат сам собой сильно упростился. Наверно тут должна быть какая-то причина...

zykov писал(а):Source of the post Это позволяет найти точный ответ для матожидания количества разных результатов в виде:
$\begin{pmatrix} n & -1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 \\ 0 & (1-\frac 1 n)^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1 \\ n-1 \end{pmatrix}$

Для полноты, этот результат справедлив для любого количества испытаний (не только для $n$

).
Для

испытаний будет:
$\begin{pmatrix} n & -1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 \\ 0 & (1-\frac 1 n)^{m-1} \end{pmatrix} \cdot \begin{pmatrix} 1 \\ n-1 \end{pmatrix}=n(1-(1-\frac 1 n)^m)$

Например, если брать $m=\alpha n$ , то предел $k/n$

будет $1-e^{-\alpha}$ .

Ian · Сообщение **Ian** » 02 апр 2020, 09:37

Ой какое простое рассуждение

M(k)=\sum_{m=1}^nM\xi_m, где случайная величина

\xi_m=1 тогда и только тогда, когда m-й из результатов получен хоть в одном испытании, иначе 0

M\xi_m=P(\xi_m=1)=1-\left(1-\frac 1n\right)^n- как у начинающих

открывая тему, я почему-то верил , что доля k/n стремится к 0, интуиция подвела

Ian · Сообщение **Ian** » 02 апр 2020, 10:01

Там многие задачи на рекуррентности, и поэтому я тоже не сомневаясь начал с них и нашел ответ. Его сложность и сбила с толку
Вот например viewtopic.php?f=4&t=1160 пришлось открыть другую тему

zykov · Сообщение **zykov** » 02 апр 2020, 10:06

Да, верно.
Хотя разные случайные величины $\xi_{m_1}$ и $\xi_{m_2}$ не являются независимыми, но это никак не влияет на то что матожидание суммы равно сумме матожиданий.

Ian · Сообщение **Ian** » 02 апр 2020, 10:16

zykov писал(а):Отсюда для дисперсии получается:
$\frac{{( 1-\frac{1}{n})^{n} - ( 1-\frac{2}{n})^{n}}}{n}-{{( 1-\frac{1}{n}) }^{2 n}}+{{( 1-\frac{2}{n}) }^{n}}$
(примерно $10^{-3}$ при .)

А вот эту дисперсию уже иначе было не найти

Портал Естественных Наук, версия 1.1