Задачка по терверу

[pierrevanstulov]

Есть конечное множество $A$. Каждому его подмножеству $a_i$ приписано некоторое целое число $f(a_i)$ от 1 до 5. Известно, что числа приписаны так, что если для подмножеств $a_i$ и $a_j$ выполняется $a_i \subseteq a_j$, то $f(a_i) \ge f(a_j)$. Также задано, что выбрав случайным образом некоторое подмножество из $A$ и проверив приписанное ему число, мы с равной вероятностью можем получить любое число из множества {1,2,3,4,5}. Можно ли найти найти функцию распределения числа для каждого заданного подмножества?

[gris]

Вот тут вопрос. Входят ли в число подмножеств пустое и само?
Ведь по $2^N$ подмножествам мы не можем равномерно распределить пять чисел. Как и по $2^N-2$. То есть в число подмножеств обязательно входит только одно из них. Какое?

[pierrevanstulov]

Само входит, пустое - не входит. Простите, что сразу не уточнил. Хотя, ведь если убрать первое условие (на упорядоченность по числам) и принять, что число соответствующее каждому подмножеству равновероятно распоеделено на множества {1,2,3,4,5}, то хоть пустое с полным входит, хоть не входят - мы вытянем любое число с равной вероятностью.

[gris]

Ну вот тогда возьмём простейший случай минимального по мощности множества, для которого можно расставить пять "уровней" по подмножествам поровну.
$A=\{a,b,c,d\}$

Вот пример расстановки:

$F(\{a,b,c,d\})=1$
$F(\{a,b,c\})= 1$
$F(\{a,b,d\})= 1$
$F(\{a,c,d\})= 2$
$F(\{b,c,d\})= 2$
$F(\{c,d\})= 2$
$F(\{b,d\})= 3$
$F(\{b,c\})= 3$
$F(\{a,d\})= 3$
$F(\{a,c\})= 4$
$F(\{a,b\})= 4$
$F(\{a\})= 4$
$F(\{b\})=5$
$F(\{c\})=5$
$F(\{d\})=5$

В это имели в виду, я не ошибся?

Я всё-таки не понял Вы сказали, что числа уже распределены, причём при случайном выборе подмножества мы каждое число получаем равновероятно.
Число подмножеств конечно. Я понимаю, что каждое выбирается тоже равновероятно. Тогда равновероятность чисел можно получить, когда их поровну. Я привёл пример такой расстановки и, в общем, то вижу, как получить любую возможную.
Но не ошибаюсь ли я с самого начала?

[pierrevanstulov]

Эм, я наверное не совсем понятно объяснил, что в моей задаче является пространством элементарных событий. Давайте, чтобы было еще проще рассмотрим множество {1,2} и пусть уровней будет всего два. Тогда возможны такие исходы:

F({1})=0,
F({1})=1,
F({1,2})=0,
F({1,2})=1,
F({2})=0,
F({2})=1,
F({})=0,
F({})=1.

То есть если "оценка" каждого подмножества распределена равновероятно на {0,1}, то условие №2 выполняется (так как мы можем вытянуть каждое подмножество с равной вероятностью). Однако не выполняется условие №1: F{1,2}=1 и F{1}=0 не могут реализоваться одновременно и это нужно както учесть. Можно ли задать распределения "оценки" каждого подмножества так, чтобы выполнялись оба условия? Тут надо что-то мутить с условной вероятностью, но что, я никак не пойму.

[gris]

Так сколько уровней? Не обязательно пять? Ну а для пяти я привёл правильную расстановку?

[pierrevanstulov]

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

Вы привели пример одной реализации, для которой выполняется условие №1 на упорядочивание.

Исходная проблема
Можно ли для любого заданного подмножества ответить на вопрос: с какой вероятностью его оценка реализуется как 1, как 2, как 3, как 4, как 5 ПРИ услови, что оценки реализуются так, что выполняется условие №1 (на упорядочивание оценок) и условие №2 (на вероятность вытягивания)? Повторю, что мы считаем вероятность вытягивания И по случайности реализации оценок, И по случайности вытягивания.

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

P.S. Да пожалуй так. Ведь если считать, что ВСЕГДА (с вероятностью 1) будет реализовываться распределение чисел от одного до 5, которое привели Вы. То будет выполняться и условие 2 и условие 1. И по крайней мере одним ответом на задачу будет, что с вероятностью 1 такое-то подмножество равно такому-то числу, а остальным числам оно равно с вероятностью 0.

НО тогда возникает вотрой, не менее интересный вопрос. Мы тут рассмотрели случай, что ваше распределение оценок реализуется с вероятностью 1 (это один из возможных случаев). А можно ли придумать другие реализации "оценок" с соответствующими им вероятностями не равными 1, чтобы выполнялись оба условия? Или их не существует?

[gris]

Я привёл пример возможной расстановки оценок. На самом деле, если мы произведём произвольные перестановки в группах, содержащих подмножества одинаковой мощности, то мы получим также возможную расстановку оценок.
То есть правая сторона таблицы остаётся неизменной:
$5 5 5 4 4 4 3 3 3 2 2 2 1 1 1$
Мне кажется, что прочие расстановки оценок не удовлетворяют условию №1.

То есть для 5-ти уровневой случайно правильной расстановки оценок для 4-х элементного подмножества имеем:

Подмножество из четырёх элементов имеет оценку 1 с вероятностью $1$.

Подмножество из трёх элементов имеет оценку 1 с вероятностью $1/2$ и 2 с вероятностью $1/2$.

Подмножество из двух элементов имеет оценку 2 с вероятностью $1/6$ и 3 с вероятностью $1/2$ и 4 с вероятностью $1/3$.

Подмножество из одного элементов имеет оценку 4 с вероятностью $1/4$ и 5 с вероятностью $3/4$.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены ТеХом

pierrevanstulov, не поленитесь, наберите формулы ТеХом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Фигурные скобки набираются так: \{,\} $\{,\}$
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.