Вероятностный метод

[grizzly]

[upd: текст этого сообщения был полностью переделан ниже с учётом замечаний, теперь уже нет смысла его смотреть здесь]
Просьба подсказать, всё ли корректно и понятно в следующем тексте. Достаточно ли подробно аргументирован ответ на вопрос в конце текста?

Пусть $\Omega $ -- совокупность случайных точек из $\{0,1\}^n$ (то есть случайных последовательностей из 0 и 1 длины $n$). Всё равновероятно, как при бросании монетки в схеме Бернулли.
Для любого $\omega \in \Omega , \omega = \{x_1,...,x_n\}$ рассмотрим все возможные пары непересекающихся подмножеств $a=\{x_{i_1},...,x_{i_s}\}$ и $b=\{x_{j_1},...,x_{j_t}\}$. Множество всех таких [неупорядоченных] пар обозначим $Q_n(\omega )$, а его мощность $q_n$ (подсчёт $q_n$ -- простая комбинаторная задача, но сейчас это не существенно). Для любых $(a,b)\in Q_n(\omega )$ вычислим их "цифровые корни" -- сумму всех координат по модулю 2. То есть цифровой корень $a$ равен $\sum_{m=1}^s x_{i_m}$ (сумма по модулю 2).

Рассмотрим случайную величину $\xi (\omega)$, равную количеству пар $(a,b)\in Q_n (\omega)$, у которых цифровые корни $a$ и $b$ совпадают.

Вопрос: чему равно мат.ожидание $\xi$?
Ответ: мат.ожидание $\xi$ равно $q_n/2$, поскольку все "биты" выбраны равновероятно и поэтому все 4 исхода для цифровых корней $a$ и $b$ также равновероятны.

[Padawan]

grizzly в сообщении #1446016 писал(а):

все возможные пары непересекающихся подмножеств $a=\{x_{i_1},...,x_{i_s}\}$ и $b=\{x_{j_1},...,x_{j_t}\}$.

Непонятно написано. Кто не пересекается? Наборы индексов или "множества". И это не множества, а упорядоченные наборы. Что значит, что они не пересекаются? И я бы ставил круглые скобки $\omega=(x_1,\ldots,x_n)$, а не фигурные. Из-за этого дополнительная путаница.

-- Сб мар 21, 2020 12:05:51 --

В общем, написано совершенно непонятно. Можно только догадываться, чего хочет автор.

[grizzly]

Padawan,
Спасибо за полезную критику. $a$ и $b$ у меня действительно подмножества, лучше переформулировать это в терминах множества и подмножества индексов. Надеюсь, что теперь будет формально понятно. Объяснить же неформально, что я хочу, было бы несложно на словах, но здесь потребует, боюсь, слишком много текста.

Ниже полностью обновлённый вариант текста.
____________
Выберем случайным образом (0-1)-вектор $\omega \in \{0,1\}^n , \omega = (x_1,...,x_n)$; при этом координаты этого вектора выбираем независимо, с вероятностью $P(x_i=0)=P(x_i=1) = 1/2, i=1,\ldots, n$.

Обозначим через $R_n$ множество индексов: $R_n=\{1,\ldots, n\}$. Выберем любые два непересекающиеся подмножества $a$ и $b$ этого множества: $a=\{i_1,...,i_s\}, b=\{j_1,...,j_t\}, i_k\ne j_l, k=1,\ldots, s, l=1,\ldots, t$. Мощность множества всех возможных таких [неупорядоченных] пар обозначим $q_n$.

Для выбранного $\omega $ и для некоторой пары $(a,b)$ вычислим по модулю 2 суммы $s_a$ и $s_b$: $s_a(\omega )=\sum_{k=1}^s x_{i_k}$, $s_b(\omega )=\sum_{l=1}^t x_{i_l}$. Рассмотрим случайную величину $\xi (\omega)$, равную количеству пар $(a,b)$, у которых $s_a=s_b$.

Вопрос: чему равно мат.ожидание $\xi$?
Ответ: мат.ожидание $\xi$ равно $q_n/2$, поскольку все координаты выбраны равновероятно и поэтому все 4 исхода $s_a$ и $s_b$ также равновероятны.

[Padawan]

grizzly в сообщении #1446036 писал(а):

любые два непересекающиеся подмножества $a$ и $b$

Непустых?

grizzly в сообщении #1446036 писал(а):

$s_b(\omega )=\sum_{l=1}^t x_{i_l}$.

$x_{j_l}$ или лучше $\sum_{j\in b} x_j$

grizzly в сообщении #1446036 писал(а):

Ответ: мат.ожидание $\xi$ равно $q_n/2$, поскольку все координаты выбраны равновероятно и поэтому все 4 исхода $s_a$ и $s_b$ также равновероятны.

Вообще не очевидно. Хотя, возможно, я туплю.

[mihaild]

Явно нужно что-то сказать про непустоту, иначе получающееся утверждение просто неверно, т.к. для пары $(\varnothing, \varnothing)$ суммы всегда равны.

На какой уровень это рассчитано? Если первая-вторая пара по терверу у студентов, то ИМХО стоит явно расписать $\xi$ как сумму индикаторов и сказать что у каждого индикатора ожидание $\frac{1}{2}$.

[grizzly]

Padawan в сообщении #1446039 писал(а):

Непустых?

Да.

Padawan в сообщении #1446039 писал(а):

$x_{j_l}$ или лучше $\sum_{j\in b} x_j$

Конечно, спасибо.

Padawan в сообщении #1446039 писал(а):

grizzly в сообщении #1446036 писал(а):

Ответ: мат.ожидание $\xi$ равно $q_n/2$, поскольку все координаты выбраны равновероятно и поэтому все 4 исхода $s_a$ и $s_b$ также равновероятны.

Вообще не очевидно. Хотя, возможно, я туплю.

Это, собственно, для меня главное. Исходы равновероятны, я уверен. В похожих местах другие авторы смело утверждают подобное. Но единственное, чего я опасаюсь, это того, что $a$ и $b$ у меня зависимы и это как-то может помешать ссылаться на них. Хотя и не вижу как, но здесь у меня явно не та квалификация, чтобы чувствовать себя уверенно.

mihaild в сообщении #1446041 писал(а):

На какой уровень это рассчитано?

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

(Оффтоп)

Кстати, в качестве подтверждения, что "координатный" подход не был замечен классиками, я приведу ссылку на одно своё доказательство, о котором уже писал здесь на форуме и таки не поленился опубликовать его:
https://mathoverflow.net/questions/3097 ... conjecture

[mihaild]

Если исходы равновероятны при каждой паре $(a, b)$ то они равновероятны и относительно любого случайного выбора пары (т.к. вероятность относительно случайной пары будет выпуклой комбинацией вероятностей при парах).

[grizzly]

mihaild в сообщении #1446051 писал(а):

относительно любого случайного выбора пары

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

[mihaild]

grizzly в сообщении #1446053 писал(а):

это ничего, что приходится говорить "случайный выбор непересекающейся пары"

Ничего. Хотя написал я это зря (повелся на ваше "$a$ и $b$ зависимы"), никакого распределения на парах вообще не нужно.
По определению, $\xi(\omega) = \sum\limits_{(a, b)} \mathbb \delta_{s_a(\omega), s_b(\omega)}$. Ожидание каждого слагаемого справа равно $\frac{1}{2}$, значит ожидание величины справа равно $\frac{1}{2}$, умноженной на число слагаемых.
(и правда же что $q_n$ более известно как $\frac{3^n - 1}{2}$?)

[grizzly]

mihaild в сообщении #1446066 писал(а):

(и правда же что $q_n$ более известно как $\frac{3^n - 1}{2}$?)

Почти. В других терминах это просто количество прямых углов в каждой вершине $n$-мерного куба: $q_n=\frac{3^n-2^{n+1}+1}{2}$. (Эта формула проходит простую проверку и в терминах множеств, и в терминах углов для $n=2$ и $n=3$.)

А подсчёт в виде пар подмножеств имеет простой геометрический смысл. Единичная матрица $n\times n$ генерирует (путём всех возможных линейных комбинаций строк) все вершины единичного куба, а две вершины куба образуют прямой угол с вершиной в нулевой точке, если и только если генерирующие их комбинации не пересекаются (не содержат общих строк генерирующей матрицы).