Чему равна вероятность того, что распределение -- данное?

[Dims]

Пусть есть алфавит длиной $M$ символов. Вероятность встречания символа в цепочке определяется неким распределением $P(a_i)$, причём эти вероятности независимы ни от чего.

Пусть мы проверили $N$ первых символов в цепочке и подсчитали частость встречания каждого из них, получили числа $N(a_i)$.

Какова вероятность того, что эти символы представляют распределение $P$?

Или направьте меня, как конкретно называется эта задача в статистике?

[Alexey1]

Это задача оценивания параметров распределения (в Вашем случае параметрами являются вероятности). Как это делается можно посмотреть в Ширяеве "Оценка вероятности упеха в схеме Бернулли" (там случай проще чем Ваш, так как рассматривается схема Бернулли). Ну а насчёт вероятности, то тут наверное вопрос должен быть о доверительном интервале, то есть с какой вероятностью оценённые параметры попадут в заданный интервал.

[Архипов]

Dims в сообщении #354127 писал(а):

Пусть есть алфавит длиной M символов. Вероятность встречания символа в цепочке определяется неким распределением P(a_i), причём эти вероятности независимы ни от чего.
Пусть мы проверили N первых символов в цепочке и подсчитали частость встречания каждого из них, получили числа N(a_i).
Какова вероятность того, что эти символы представляют распределение P?
Или направьте меня, как конкретно называется эта задача в статистике?

Немножко поправлю (на мой взгляд):
1)Если задан алфавит длиной M, то длина цепочки N должна быть значительно больше М (иначе мы не сможем выявить закономерность появления тех символов, которые не окажутся в цепочке).
2)Если "некое распределение Р(a_i)" задано (у Вас в тексте написано - "определяется"), то вероятности Р(i) зависят от этого распределения, а в тексте - "не зависят ни от чего". Противоречие в одном предложении.
3) В статистике подобная задача называется "Оценка вероятности (надежности) гипотез о характере распределения вероятностей в генеральной сувокупности по данной выборке".

[epros]

Dims в сообщении #354127 писал(а):

Какова вероятность того, что эти символы представляют распределение $P$?

Или направьте меня, как конкретно называется эта задача в статистике?

Если доопределить задачу семейством возможных распределений $P_{\alpha}(x)$, где $\alpha$ - произвольный параметр (не обязательно целочисленный), то получим задачу Байесовского оценивания:
$P(\alpha | a_1, \dots , a_N) = \frac{P(\alpha) \cdot \prod\limits_{i=1}^{N} P_{\alpha}(a_i)}{\sum\limits_{\beta} P(\beta) \cdot \prod\limits_{i=1}^{N} P_{\beta}(a_i)}$

Здесь $P(\alpha)$ (функция без индекса) - некое априорное распределение параметра $\alpha$, которое тоже должно быть задано. Слева - апостериорное распределение параметра, полученное для соответствующей выпавшей последовательности символов $a_1, \dots , a_N$. Отсюда итоговое апостериорное распределение:
$P(x | a_1, \dots , a_N) = \sum\limits_{\beta} P_{\beta}(x) \cdot P(\beta | a_1, \dots , a_N)$

Указанные Вами в условиях априорные распределения символов избыточны, ибо могут быть рассчитаны как $\sum\limits_{\beta} P(\beta) \cdot P_{\beta}(x)$.

[alex1910]

Dims в сообщении #354127 писал(а):

Пусть есть алфавит длиной $M$ символов. Вероятность встречания символа в цепочке определяется неким распределением $P(a_i)$, причём эти вероятности независимы ни от чего.

Пусть мы проверили $N$ первых символов в цепочке и подсчитали частость встречания каждого из них, получили числа $N(a_i)$.

Какова вероятность того, что эти символы представляют распределение $P$?

Или направьте меня, как конкретно называется эта задача в статистике?

Частость - еще не вероятность

[epros]

alex1910 в сообщении #354320 писал(а):

Частость - еще не вероятность

Абсолютно верное замечание. Связь частоты с вероятностью хорошо видна в том случае, если в описанной мною выше задаче Байесовского оценивания задать следующие исходные распределения вероятностей:

$P_{\vec{\alpha}}(a_i) = \alpha_i$
(здесь $i$ - номер символа в алфавите, а не в последовательности, а параметр $\vec{\alpha}$ понимается как $M$-размерный вектор, такой, что $\alpha_i \ge 0$ и $\sum\limits_{i=1}^{M} \alpha_i = 1$).

и

$P(\vec{\alpha}) = const$ (т.е. все значения параметра $\vec{\alpha}$ априорно равновероятны).

Любопытно посмотреть во что при этом превращается приведённая выше формула для оценивания апостериорного распределения вероятностей $P({x | a_1, \dots , a_N)$. А именно, в данном случае мы получим:

$P(\vec{\alpha} | a_1, \dots , a_N) = r \cdot \prod\limits_{i=1}^{M} (\alpha_i)^{K_i}$, где $r$ - нормировочный коэффициент, а $K_i$ - количество выпадений $i$-того символа алфавита в последовательности (учитываем, что $\sum\limits_{i=1}^{M} K_i = N$).

Нетрудно заметить, что максимум этой вероятности находится в точке:

$\alpha_{i}^{max} = \frac{K_i}{N}$

что соответствует частотам выпадения символов.

[Dims]

Правильны ли нижеследующие мои рассуждения.

Переопределяю условия.

1) Дано распределение выпадения символов $p(i)$, где $i=1...M$ - номер символа, причём $\sum^{M}_{i=1} {p(i)}=1$

2) Дана гистограмма фактически выпавших символов $H(i)$, причём $\sum^{M}_{i=1} {H(i)}=N$ -- количество проверенных символов.

3) Вопрос: какова вероятность $P(H|p)$ выпадения данной гистограммы при условии данного распределения вероятностей (ответ -- это одно число)?

Мой ответ:

$P(H|p) = \prod^{N}_{i=1} f(H(i);N,p(i))$, где $f(k;n,p)$ - биномиальное распределение с $n$ степенями свободы и вероятностью успеха $p$.

Смущает: независимы ли вероятности под суммой и можно ли их потому перемножать?

-- Пн сен 20, 2010 16:11:53 --

А, может, количество степеней свободы биномиального распределения нужно уменьшать с каждым бином гистограммы?

То есть, $P(H|p) = \prod^{N}_{i=1} f\left(H(i);N-\sum^i_{j=0}{H(j)},p(i)\right)$?

Это, по крайней мере, приравняет единице последний множитель...

[epros]

Dims в сообщении #354360 писал(а):

биномиальное распределение с $n$ степенями свободы и вероятностью успеха $p$

Причём тут биномиальное распределение? У Вас же не два символа, а, возможно, больше.

[Dims]

epros в сообщении #354370 писал(а):

Причём тут биномиальное распределение? У Вас же не два символа, а, возможно, больше.

Любое количество символов можно рассматривать и как два. Например, все буквы русского алфавита можно рассматривать как два символа: "А" и "не А".

[epros]

Dims в сообщении #354452 писал(а):

Любое количество символов можно рассматривать и как два. Например, все буквы русского алфавита можно рассматривать как два символа: "А" и "не А".

Но Вы же рассматриваете не как два, а как $M$. И зачем Вам нужна эта вероятность $P(\vec{H} | \vec{p})$? Посчитать-то её нетрудно, но как это поможет ответить на исходный вопрос - оценить распределение?

[Dims]

epros в сообщении #354496 писал(а):

Но Вы же рассматриваете не как два, а как $M$.

В конечную формулу входит $M$, рассмотрение как двух происходит только в отдельном её члене.

Цитата:

Посчитать-то её нетрудно,

Как?

Цитата:

но как это поможет ответить на исходный вопрос - оценить распределение?

Так она и будет оценкой.

[epros]

Dims в сообщении #354549 писал(а):

Цитата:

Посчитать-то её нетрудно,

Как?

$P(\vec{H} | \vec{p}) = \frac{N!}{\prod\limits_{i=1}^{M}H_i !} \cdot \prod\limits_{i=1}^{M} (p_i)^{H_i}$

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

Dims в сообщении #354549 писал(а):

Цитата:

но как это поможет ответить на исходный вопрос - оценить распределение?

Так она и будет оценкой.

Нет, неверно. Оценка должна быть нормирована по $\vec{p}$, а не по $\vec{H}$. Я же Вам выше на пару постов записал выражение для оценки $P(\vec{\alpha} | a_1, \dots , a_N)$. Вы просто переобозначили параметры $\alpha_i$ как $p(i)$.

[Dims]

А, Вы имеете в виду, что мне нужна вероятность $P(p|H)$, а не $P(H|p)$? Да, действительно, это совершенно верно!

[epros]

Dims в сообщении #354750 писал(а):

А, Вы имеете в виду, что мне нужна вероятность $P(p|H)$, а не $P(H|p)$? Да, действительно, это совершенно верно!

Я бы даже сказал, что нужна вероятность $P(\vec{p} | a_1, \dots , a_N)$, где $a_1, \dots , a_N$ - последовательность выпавших символов. В смысле, если выпали два "А", а потом одно "Б", то это не то же самое, что выпало "А", потом "Б", а потом "А" (хотя вероятности и одинаковые). Нет никакого смысла объединять все возможные перестановки выпавших символов в одно событие $\vec{H}$, т.е. нет никакого смысла считать вероятность именно $\vec{H}$ и ради этого добавлять множитель $\frac{N!}{\prod\limits_{i=1}^{M} H_i !}$.

[Dims]

epros в сообщении #354606 писал(а):

Dims в сообщении #354549 писал(а):

Цитата:

Посчитать-то её нетрудно,

Как?

$P(\vec{H} | \vec{p}) = \frac{N!}{\prod\limits_{i=1}^{M}H_i !} \cdot \prod\limits_{i=1}^{M} (p_i)^{H_i}$

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

В общем виде этого доказать не могу, но эта формула совпадает с моей (с биномиальным распределением, но немного поправленной -- там надо и вероятность p перенормировать для каждого столбца гистограммы) в нескольких проверенных мною частных случаях.

-- Вт сен 21, 2010 18:01:34 --

epros в сообщении #354756 писал(а):

Я бы даже сказал, что нужна вероятность $P(\vec{p} | a_1, \dots , a_N)$, где $a_1, \dots , a_N$ - последовательность выпавших символов. В смысле, если выпали два "А", а потом одно "Б", то это не то же самое, что выпало "А", потом "Б", а потом "А" (хотя вероятности и одинаковые).

В моём случае это неразличимые ситуации -- то есть, вывод должен быть сделан один и тот же.

-- Вт сен 21, 2010 18:04:41 --

epros в сообщении #354314 писал(а):

Здесь $P(\alpha)$ (функция без индекса) - некое априорное распределение параметра $\alpha$, которое тоже должно быть задано.

То есть, фактически, это вероятности того, что мы столкнёмся с тем или иным распределением, которое нужно распознать. Так?

А что такое величина с буквой бета?

-- Вт сен 21, 2010 18:21:02 --

По формуле Байеса

$P(p|H) = \frac{P(H|p) \cdot P(p)}{P(H)}$

Здесь $P(p)$ совпадает с Вашей величиной с альфа. А $P(H)$, наверное, с бета?

Ну вот, теперь задача проясняется.

Если у нас выпала определённая гистограмма, то наша задача -- сравнить между собой все вероятности $P(p|H)$ для каждого из распознаваемых распределений $p$ и выбрать из них максимальное. Это и будет результатом работы программы. Величина $P(H)$ для решения задачи не нужна, так как она одна и та же у всех сравниваемых величин.

А вот величина $P(p)$ желательна.

Однако, возможно, что разумного предположения о ней сделать нельзя, поэтому нужно будет положить это распределение равномерным, то есть, $P(p) = const$. В этом случае задача сведётся к изначальной, то есть, к выбору согласно величине $P(H|p)$.

Роль величины $P(p)$ сводится к тому, что она может перебить $P(H|p)$ в некоторых случаях.

Однако, если статистики достаточно много, то величина $P(H|p)$ будет сильно дифференцирована для разных p и, в этом случае, дополнительный учёт $P(p)$ вообще ничего не даст.