наиболее вероятный исход

[malin]

Всем доброго времени суток.
Помогите, пожалуйста, решить задачу(я что-то совсем закопался, даже ссылок никаких не нашел).
Исходная задача такая: Рассмотрим 2 множества известной мощности $|A| = m, |B| = l$.
Во множестве A выделим некоторое неизвестное собственное подмножество известной мощности $\Theta\subset A, |\Theta| = k < m$. Выделим далее в $B$ неизвестный элемент $g$.

Теперь рассмотрим множество всех отображений $\mathbb{F} = \{f:A\rightarrow B| f(\Theta) = g \}$. Из этого множества случайно выберем функцию $f$ и произведем выборку
$\xi_1 = f(a_1), ... , \xi_N = f(a_N)$, где $a_1, ... , a_N$ - случайная выборка элементов множества A с возвращением.
Требуется по этой выборке найти элемент g.

Попытки решения: Если рассматривать немного не такую задачу, а еще на каждом шаге выбирать случайно функции $f_1, ...., f_N$, получим выбоку $\xi_1 = f_1(a_1), ... , \xi_N = f_N(a_N)$. И легко посчитать вероятность появления элемента $g$: $P(g) = \frac{|\Theta|}{|A|} + (1-\frac{|\Theta|}{|A|})\frac{1}{|B|}$
В принципе, если $B = {0, 1}$, имеем простую гипотезу против простой альтернативы
$H_0: \xi \sim Be(P(g)), H_1: \xi \sim Be(1-P(g))$ И строим наиболее мощный критерий.
А вот как быть, если $|B| > 2$? Есть вариант найти самый частый элемент выборки, и построить простую гипотезу против сложной альтернативы, но это не совсем правильно и непонятно, как считать вероятность ошибки.

[_hum_]

Наверное, все-таки $f(\Theta) = \{g\}$?
С тестированием что-то явно напутано (не видно решающего правила, да и с вычислением $P(g)$ какие-то махинации).
Возможно, стоит использовать напрямую точечную оценку (вместо тестирования). В вашей задаче можно вычислить матожидание $\mathbf{E} \xi_1$ через $g$?

[malin]

Задача сформулирована полностью. Насчет мат. ожидания $E\xi_1$ - Ну, тут возникают проблемы. $P(g)$ известно, вероятности появления остальных элементов равны между собой, т.е. $P(a) = \frac{1 - P(g)}{l-1}$. Вот только чтобы вычислить мат. ожижание, необходимо знать $g$.

[_hum_]

malin в сообщении #435435 писал(а):

$P(g)$ известно

Что такое вообще $P(g)$? Вероятность какого события ("появление хотя бы одного $g$ среди значений выборки", "появление ровно одного $g$ среди значений выборки", "появление $g$ в качестве первого значения выборки")?.

Цитата:

вероятности появления остальных элементов равны между собой

Это из каких соображений?

Цитата:

Вот только чтобы вычислить мат. ожидание, необходимо знать $g$

Считайте, что знаете. Формулу, выражающую $\mathbf{E}\xi_1$ через $g$ можете получить?
Для этого резонно ввести случайную величину $\zeta$, отвечающую номеру вытягиваемой из $\mathbb{F}$ функции (считаем, что все функции в $\mathbb{F}$ занумерованы s = 1 до $|\mathbb{F}|$). Тогда
\begin{multline*} \mathbf{E}\xi_1 = \sum_{s=1}^{|\mathbb{F}|}\mathbf{P}(\zeta = s)\mathbf{E}(\xi_1 | \zeta = s) = \sum_{s=1}^{|\mathbb{F}|}\mathbf{P}(\zeta = s)\sum_{x=1}^{|B|}x \mathbf{P}(\xi_1 = x | \zeta = s) = ? \end{multline*}
Понятно, что если функции выбираются "равновозможно", то $\mathbf{P}(\zeta = s) = 1/|\mathbb{F}|$. Также понятно, что если $f_s|_{(A\setminus\Theta)}$ -- сюрьекция, то $ \mathbf{P}(\xi_1 = g | \zeta = s) = |\Theta|/|A|$. А вот в общем случае с вероятностями $ \mathbf{P}(\xi_1 = x | \zeta = s) $ не все так ясно. Их нужно пытаться считать.

[malin]

$P(g) = P\{\xi_1 = g\}$, т.е. это вероятность того, что при случайном выборе элемента $a\in A$, функции $f\in \mathbb F$ $f(a) = g$.

Вероятности появления элементов равны между собой из соображений случайности выбора функции $f$. Это следует из очевидных рассуждений типа: количество функций, переводящих $a\in A$ в $h\in B \setminus g$ не зависит от $h$.

Поэтому $P(g) = \frac{|\Theta|}{|A|} + (1-\frac{|\Theta|}{|A|})\frac{1}{|B|} $, обозначим эту вероятность $p$.
$P(h) = \frac{1 - P(g)}{l-1}$, обозначим эту вероятность $q$.

Теперь найдем м.о. $E\xi_1 = \sum\limits_{i = 1}^{|B|}iP(i) = q(\frac{|B|(|B|+1)}{2}) - gq + gp = q(\frac{l(l+1)}{2}) - gq + gp$

[_hum_]

Ну, если все верно, то для построения состоятельной оценки достаточно выразить из вашего уравнения $g$ через матожидание и вместо последнего подставить средневыборочное.

[malin]

Еще один совсем маленький вопрос возник: Выразил я этот элемент через м.о. получил оценку, на практике уже все испробовал....
Верно же что, вероятность ошибиться при нахождении элемента $g$ напрямую выражается через вероятность ошибиться, заменяя м.о. эмпирическим средним?

Элемент $g$ я беру, как ближайшее целое к статистике. Как бы посчитать вероятность ошибки...

Даже фиг с ним со всем, как решить такую задачу:

Пусть $\vec\nu = (\nu_1,...,\nu_g,....,\nu_k) \sim Poly(n, \vec p)$. Чему равна веротность:
$P\{\nu_g > \nu_1, ..., \nu_g > \nu_k \}$, т.е. что $g$ встретился чаще всех?

[_hum_]

malin в сообщении #455468 писал(а):

...Верно же что, вероятность ошибиться при нахождении элемента $g$ напрямую выражается через вероятность ошибиться, заменяя м.о. эмпирическим средним?

Да, но тут ньюанс - в общем случае эта вероятность зависит от самого неизвестного $g$. Поэтому, если вам принципиально помимо оценки иметь еще и какую-то вероятностную гарантию (не зависящую от $g$), придется чем-то поступиться, например, точностью - и вместо точечной оценки $g^*$ использовать доверительные интервалы $\Big(G^-(\xi_1,\dots,\xi_n,\varepsilon), G^+(\xi_1,\dots,\xi_n,\varepsilon)\Big)$ с уже гарантированной вероятностью $\geq 1-\varepsilon$ попадания $g$ в эти интервалы. (Кстати, асимптотический вариант доверительных интервалов легко строится на базе ранее найденной оценки $g^*$).