2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Вероятностный метод
Сообщение21.03.2020, 09:22 
Заслуженный участник
Аватара пользователя


09/09/14
6328
[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$ также равновероятны.

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 10:02 
Заслуженный участник


13/12/05
4518
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 --

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

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 12:18 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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$ также равновероятны.

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 12:38 
Заслуженный участник


13/12/05
4518
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$ также равновероятны.

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

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 13:05 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 13:58 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 14:17 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 14:52 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 17:21 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
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}$?)

 Профиль  
                  
 
 Re: Вероятностный метод
Сообщение21.03.2020, 17:44 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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$ генерирует (путём всех возможных линейных комбинаций строк) все вершины единичного куба, а две вершины куба образуют прямой угол с вершиной в нулевой точке, если и только если генерирующие их комбинации не пересекаются (не содержат общих строк генерирующей матрицы).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group