Генерация распределений

[RSNR90]

Привет,
есть такая задача - случайный вектор $(x_1, x_2, ..., x_n)$, где $x_i=\left\{0,1\right\}$. Для него задано распределение, такое что
$\sum_{\bar{x}\in\left\{0,1\right\}^n} P(\bar{x})= 1$ и $\sum_{\bar{x}: \bar{x_i} = 1} P(\bar{x}) = a_i$, где $a_i$ - заданные числа. Такие распределения можно задавать как вектор в $R^{2^n}$, на который наложено n+1 ограничение. Необходимо сгенерить несколько десятков векторов в $R^{2^n}$, удовлетворяющих этим условиям. Понятно, что можно искать вершины полиэдра, потом брать некоторые их выпуклые комбинации, но хотелось бы получить более-менее равномерную выборку таких точек. Что можете посоветовать? Какой метод существует для семплирования на границе полиэдра? наверняка ведь подобные задачи уже решены и существуют различные методы.
Спасибо.

[PAV]

Значение $P(\mathbf{0})$ (вероятность нулевого вектора) входит только в первое ограничение нормировки, поэтому его нужно задать самым последним так, чтобы превратить его в равенство. Аналогично, значения $P(\mathbf{1}_i)$ (одна единица на $i$-й позиции) участвует только в одном из заданных ограничений, поэтому оно также должно задаваться последним исходя из условия соответствующего равенства.

Поэтому можно попробовать сделать так: перебирать в произвольном порядке остальные значения, задавая их достаточно произвольно так, чтобы выполнялись все требуемые ограничения в виде неравенств. А в конце задать указанные значения так, чтобы неравенства превратились в равенства. Правда, это все равно не всегда гарантирует успех процедуры. Можно попробовать расписать все более аккуратно так, чтобы учитывать условия и сверху, и снизу, и всегда гарантировать существование хотя бы одного такого распределения.

-- Чт мар 22, 2012 08:09:56 --

Впрочем, есть идея проще и нагляднее. Фактически Вы задали все маргинальные распределения компонент вектора. Если потребовать, чтобы они были независимы, то тем самым мы задаем одно совместное распределение. Другие распределения будут получаться, если от условия независимости отказаться.

Похоже, что строить распределение легче и нагляднее всего последовательно увеличивая $n$. Допустим, Вы задали каким-то образом вероятности для $n-1$, то есть все числа $P(x_1,\ldots,x_{n-1})$. Перейти к $n$ - это означает разбить каждое такое число в сумму двух $P(x_1,\ldots,x_{n-1},0)$ и $P(x_1,\ldots,x_{n-1},1)$. При этом все существующие условия не нарушаются, и нужно только следить за тем, которое соответствует новой компоненте. Это всегда можно сделать, потребовав независимости этой компоненты от предыдущих. При этом вероятности будут задаваться по формулам:

$$ P(x_1,\ldots,x_{n-1},1) = a_nP(x_1,\ldots,x_{n-1}),\quad P(x_1,\ldots,x_{n-1},0) = (1-a_n)P(x_1,\ldots,x_{n-1}) $$

Этот набор можно взять в качестве "базового", а новые генерировать, прибавляя к этим значениям $P(x_1,\ldots,x_{n-1},1)$ поправки. При этом вектор поправок должен иметь нулевую сумму компонент, а также каждая компонента имеет ограничение сверху и снизу. Придумать разумный способ генерирования такого вектора поправок совсем несложно.

[RSNR90]

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

[PAV]

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

[RSNR90]

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

[PAV]

Я не вижу никаких проблем. Распишите в общем виде переход от предыдущего шага к последующему и увидите, что все в порядке.

[RSNR90]

Получить распределение независимых случайных величин действительно просто. А вот потом уже перейти к распределению зависимых - не так просто, и условие нулевой суммы не единственно. Если взять простой пример размерности 2, где $a_1=0.87$ и $a_2=0.79$, тогда базовый вектор -
(0.0273;0.1027;0.1827;0.6873). Если взять вектор поправок с нулевой суммой - (0.09;-0.09;-0.15;0.15) -
то получим вектор (0.1173;0.0127;0.0327;0.8327), для которого условие по $a_2$ не будет выполняться. В случае трех и более компонент будут возникать проблемы и по другим а.
Решением такой проблемы может быть вектор поправок вида (+a,-a,-a,+a), вообще для любого n позиция первого отрицательного члена будет $2^{n-2}+1$, затем все компоненты будут отрицательными, а начиная с позиции $3*2^{n-2}+1$ опять положительными. Но в таком случае на а будет ограничение сверху в виде $a_1*(1-a_2)*...*(1-a_n)$. Можно расставлять знаки и в другом порядке, но при моей расстановке получается наиболее ослабить ограничения.

[PAV]

Так я немного другое имел в виду. Под "вектором поправок" я называл только те поправки, которые прибавляются к половине предыдущих вероятностей. И именно они должны иметь нулевую сумму. А вторая половина определяется по ним симметрично. Для случая $n=2$ действительно общий получаемый таким образом вектор поправок может иметь только такой вид $(a,-a,-a,a)$. Но уже для следующих размерностей он может быть устроен и более сложно.

-- Пн мар 26, 2012 11:42:51 --

То есть иными словами, для случая $n=3$ общий вектор поправок будет иметь вид $(a,-a,b,-b,c,-c)$, где сумма $a+b+c=0$. И каждое из данных чисел ограничено сверху и снизу.

[RSNR90]

Да, только вот как генерить такой вектор с нулевой суммой компонент и следить за тем, чтобы компоненты полученного не вылетали за (0,1)? По мне так просто получилось переформулировать задачу..

[PAV]

Ограничения удовлетворить просто - каждая компонента в векторе добавок ограничена сверху и снизу своей границей. Генерацию таких векторов можно делать многими способами. Например, так: последовательно делаем элементарные шаги, выбирая две случайные компоненты, и одну увеличиваем на некоторое малое $\varepsilon$, а другую - уменьшаем на то же самое $\varepsilon$. Перед этим составляем множества компонент, которые можно увеличить, и которые можно уменьшить. Выбор компонент из этих множеств можно сделать равновероятным, а можно задать вероятность выбора соответствующей компоненты пропорциональной той величине, на которую ее можно изменить в соответствующую сторону.