Полное описание двух бернуллиевских величин тремя числами?

[Dims]

Есть две случайные величины a и b, которые могут принимать значения 0 или 1 каждая.

Ясно, что для полной информации о них, достаточно задать 4 вероятности: 00, 01, 10 и 11. Эти 4 вероятности не независимы, должно выполняться условие нормировки: 00 + 01 + 10 + 11 = 1.

Вопрос: можно ли как-то охарактеризовать данное распределение ТРЕМЯ независимыми числами, меняющимися от 0 до 1?

Ясно, например, что три вероятности 00, 01 и 10 таковыми не являются, так как каждая в отдельности может принимать значения до 1, но даже две одновременно -- не могут. Не подходят и вероятности P(A), P(B), P(AB), так как P(AB) имеет ограничения, определяемые первыми двумя.

[PAV]

Возьмем две величины: $x=P\{a=0\}$ и $y=P\{b=0\}$. Они независимо друг от друга могут принимать любые значения от 0 до 1.

При этом совместная вероятность $P\{00\}$ может принимать любое значение от 0 до $\min\{x,y\}$.

Введите величину $z$, принимающую любое значение от 0 до 1, и положите $P\{00\}=z\cdot\min\{x,y\}$.

Тройка $(x,y,z)$ удовлетворяет Вашим условиям и однозначно задает распределение.

[Dims]

PAV писал(а):

При этом совместная вероятность $P\{00\}$ может принимать любое значение от 0 до $\min\{x,y\}$.

Неправильно! Если вероятности отдельных величин в сумме больше единицы, то они не могут не встречаться вместе. То есть, совместная вероятность обязана быть больше нуля.

Вообще, у меня получилось, что нижнее ограничение на совместную вероятность равно $p_{ab, min} := max(0, -1+p_a+p_b)$.

[PAV]

Да, разумеется, я ошибся. Есть и нижнее ограничение, указанное Вами. Все равно можно использовать тот же принцип, используя третью независимую переменную от 0 до 1 как индикатор значения на полученном отрезке. Правда, если он сворачивается в точку (например, если $p_a=p_b=1$), то значение третьей переменной ни на что не влияет, так что построенное отображение не взаимно-однозначно.

Можно сделать немного по-другому. Зададим $x=P(00)$, произвольно от 0 до 1. Теперь вероятность $P(01)$ меняется от 0 до $1-x$, положим $P(01)=y(1-x)$, где $y$ меняется от 0 до 1. По тому же принципу вводим третью переменную $z$, с помощью которой получаем $P(10)$. Правда, так построенное отображение также не взаимно-однозначно.

Но вопрос - зачем это все нужно? Зависимые переменные, однозначно задающие нашу систему, геометрически представляют собой симплекс, задающийся неравествами $x+y+z\le 1$, $x\ge0$, $y\ge0$, $z\ge0$. Вы хотите преобразовать его в единичный куб. Это можно сделать тем или иным способом. Но естественного вероятностного смысла новые переменные уже иметь не будут. Зачем тогда это надо?

[Dims]

PAV писал(а):

Все равно можно использовать тот же принцип, используя третью независимую переменную от 0 до 1 как индикатор значения на полученном отрезке.

Да, я это понимаю, я не отрицал Вашего метода. Просто думаю, как сформулировать, чем он мне не нравится. Или понять, что нравится.

Цитата:

Можно сделать немного по-другому.

Да, вот этот метод мне больше нравится. Как Вы их выдумываете?

Цитата:

Но вопрос - зачем это все нужно?

Мне нужно хранить эти данные в памяти компьютера, хочу, чтоб было оптимальнее.

Цитата:

Зависимые переменные, однозначно задающие нашу систему, геометрически представляют собой симплекс,

А что такое "симплекс"?

Цитата:

Вы хотите преобразовать его в единичный куб.

Да, мне приходил в голову образ этого куба.

Цитата:

Это можно сделать тем или иным способом. Но естественного вероятностного смысла новые переменные уже иметь не будут.

А точно не будут? Мне как раз интересны были бы не искусственные, а более-менее общепризнанные описания. Значит, таких нет?

[PAV]

Цитата:

А что такое "симплекс"?

Симплекс - $n$-мерный многогранник, являющийся выпуклой оболочкой $n+1$ точкек, лежащих в общем положении (т.е. не лежащих в одной $n-1$-мерной гиперплоскости.

Посмотрите тему http://dxdy.ru/viewtopic.php?p=28121#28121. Здесь можно применить ту же идею, которую я там предложил. Рассмотрим на примере двух переменных. Пусть имеется $(x,y)$ с ограничениями $x\ge0$, $y\ge0$, $x+y\le 1$. Геометрически эта область представляет собой прямоугольный равнобедренный треугольник. Мы хотим более-менее естественно преобразовать его в единичный квадрат. Для этого применим растяжение вдоль каждого луча, выходящего из начала координат, причем коэффициент растяжения выбирается так, чтобы точка на гипотенузе перешла в границу единичного квадрата. В частности, в середине гипотенузы произойдет излом, растяжение там будет максимальным (в два раза).

Чтобы точно посчитать растяжение вдоль луча, нужно вычислить координаты точки $(x_0,y_0)$ на этом луче, в которой он выходит из единичного квадрата. Растяжение будет с коэффициентом $k=x_0+y_0$. При этом точка на гипотенузе, для которой сумма координат равна 1, в точности перейдет в точку $(x_0,y_0)$.

Обратное преобразование осуществляется, соответственно, сжатием.

Ровно то же самое делается и в трехмерном случае.

Цитата:

Мне нужно хранить эти данные в памяти компьютера, хочу, чтоб было оптимальнее.

Этого я не понимаю. Ведь Вы же наверняка храните каждое значение как одно float или double, в чем выражается оптимальность? И неужели есть задача, где это хоть сколько-нибудь критично?

[Dims]

PAV писал(а):

Ведь Вы же наверняка храните каждое значение как одно float или double,

В виде целого, причем p=n/(n_max-1)! Естественно, приходится огрублять значение.

Цитата:

И неужели есть задача, где это хоть сколько-нибудь критично?

Очень много значений, многие миллионы.

Возможно, я и неправ, я ведь просто думаю пока.

[G^a]

Добречко!

Dims писал(а):

Очень много значений, многие миллионы.

И много не хватает? ( в смысле объёма оперативной памяти).

Может имеет смысл пересмотреть алгоритмическое построение программы, или распараллелить и решить на кластере, или отправить на суперкомпьютер.

Ибо огрублять (тем более вероятности) как-то не очень хорошо, тогда придётся проверять, что ошибкой огрубления можно пренебречь и она не накапливается и не влияет, значимо, на промежуточные и конечные результаты расчётов.

Что скажите, Dims?

[Someone]

Dims писал(а):

Есть две случайные величины a и b, которые могут принимать значения 0 или 1 каждая.

Ясно, что для полной информации о них, достаточно задать 4 вероятности: 00, 01, 10 и 11. Эти 4 вероятности не независимы, должно выполняться условие нормировки: 00 + 01 + 10 + 11 = 1.

Вопрос: можно ли как-то охарактеризовать данное распределение ТРЕМЯ независимыми числами, меняющимися от 0 до 1?

А зачем нужна эта независимость? Чем Вас не устраивает простейший набор трёх неотрицательных чисел $p_{00}$, $p_{01}$, $p_{10}$, удовлетворяющих неравенству $p_{00}+p_{01}+p_{10}\leqslant 1$? Всякое хитрое кодирование приведёт к снижению эффективности алгоритма.

Но идею преобразования PAV уже указал. Практически её можно осуществить так.
Тройку $(p_{00},p_{01},p_{10})=(0,0,0)$ оставляем неизменной. Для ненулевой тройки находим $s=p_{00}+p_{01}+p_{10}$ и $r=\frac{\max\{p_{00},p_{01},p_{10}\}}s$, после чего полагаем $q_{00}=\frac{p_{00}}r$, $q_{01}=\frac{p_{01}}r$, $q_{10}=\frac{p_{10}}r$. Очевидно, $0\leqslant q_{00}\leqslant 1$, $0\leqslant q_{01}\leqslant 1$, $0\leqslant q_{10}\leqslant 1$.
Для обращения преобразования снова тройку $(q_{00},q_{01},q_{10})=(0,0,0)$ оставляем неизменной, а для ненулевой тройки заметим, что $\max\{q_{00},q_{01},q_{10}\}=\frac{\max\{p_{00},p_{01},p_{10}\}}r=s$ и $q_{00}+q_{01}+q_{10}=\frac{p_{00}+p_{01}+p_{10}}r=\frac sr$, откуда получаем $r=\frac{\max\{q_{00},q_{01},q_{10}\}}{q_{00}+q_{01}+q_{10}}$ и, наконец, $p_{00}=rq_{00}$, $p_{01}=rq_{01}$, $p_{10}=rq_{10}$.

[PAV]

Вопрос переместился в плоскость Computer Science, а именно - как компактнее записать некоторую информацию.

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

Правльный вопрос задал G^a - насколько допустима погрешность в задании вероятностей. Допустим, что нам достаточно трех знаков после запятой. Тогда это равносильно заданию трех целых неотрицательных чисел, сумма которых не превосходит 1000. Для записи числа от 0 до 1000 достаточно 10 бит. Так что все эти три числа можно загнать в стандартные 4 байта. Здесь мы зависимости между значениями не использовали.

Другой вариант, использующий зависимости, заключается в следующем. Запишем первую вероятность. Тогда диапазон значений следующей уже сужается и возможно для нее можно использовать меньше бит. Для третьей - возможно, еще меньше.

Для этого подхода особенно удачно, если числа будут задаваться в порядке убывания. При этом, правда, придется отдельно указывать, в каком порядке они следуют, на что потребуется 3 бита.

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

Можно придумать массу других способов упаковать имеющиеся данные. Главный вопрос - насколько это оправдано. Ведь возрастает время доступа к данным... Неужели и вправду в задаче объем данных настолько критичен?

[G^a]

Могу добавить, что из опыта численного решения задач массивных с точки зрения объёма промежуточных данных получается следующее:

- при настоящем развитии вычислительной техники биться за упаковку данных имеет смысл в бортовых мобильных системах.

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

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

- при разовых расчётах производимых на стационарных системах, рентабелен метод грубой силы. Если не хватает 4ГБ ОЗУ обычного ПК, задействуйте вытесняемую память (файл подкачки). К примеру алгоритм виртуальной памяти на Linux очень неплохо реализован (надо только ядро перекомпилировать).

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

Если доступ к данным в программе случайный (например метод Монте-Карло), то однозначно так не скажешь, надо вопрос исследовать.

И в качестве резюме. Если задача серьёзная и программа предварительно обкатана на ПК на меньших размерностях, то можно обратиться к суперкомпьютерным мощностям, или если задача допускает эффективное распараллеливание, то решить её на тех же самых Linux-кластерах (это проще, так как подобные аппаратно-программные платформы есть уже во многих ВУЗах).

[Dims]

G^a писал(а):

Dims писал(а):

Очень много значений, многие миллионы.

И много не хватает? ( в смысле объёма оперативной памяти).

Как таковой нехватки нет, просто прищла в голову мысль изначально сделать пооптимальнее.

Цитата:

Может имеет смысл пересмотреть алгоритмическое построение программы, или распараллелить и решить на кластере, или отправить на суперкомпьютер.

Ну, суперкомпьютер это слишком. А пересмотреть, наверное, надо.

[PAV]

Dims писал(а):

Как таковой нехватки нет, просто прищла в голову мысль изначально сделать пооптимальнее.

Это в принципе не очень правильно. Оптимизацией, тем более такой нетривиальной, надо заниматься тогда, когда известны тонкие места.

А в чем, собственно, состоит прикладная задача?

[G^a]

Dims писал(а):

Как таковой нехватки нет, просто прищла в голову мысль изначально сделать пооптимальнее.

Пооптимальнее? Нехватки памяти ещё нет, а погрешность и потенциальная ошибка округления уже есть! Где же здесь оптимальность, что за специфический критерий оптимальности такой?

Dims, задачу в студию! Может народ что коллективно подскажет.

[Dims]

Ребят, это громко сказано "задача". Просто была некая полуальтернативная идея по статистическому распознаванию образов. Начал думать над ней, автоматически стараться оптимизировать, даже пару строчек написал. Но потом охладел.

А теперь мне стал интересен уже сам теоретический вопрос.

Допустим, каждое событие обозначается вектором в многомерном пространстве. Длина вектора означает вероятность события или какую-либо однозначную её функцию.

Направление вектора означает его корреляцию с другими векторами. Так, если вектора перпендикулярны, то описываемые ими события независимы. Если угол отличается от 90 градусов, то между событиями есть зависимость. Если вектора полностью противоположны, то они антикоррелируют.

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

Видно, что в такой модели есть ряд особенностей и нестыковок.

Например, произведение перпендикулярных векторов не равно нулю и не перпендикулярно им, так что оно отличается и от векторного и от скаларного произведений.

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

И так далее.

Вопрос: существует ли такая какая-нибудь векторная модель теорвера?