случайная точка в выпуклой многогранной области

Question

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

Типичный пример: генерировать равномерно распределенные случайные (p_1, ..., p_n) в симплексе, то есть p_i> = 0, для всех i и p_1 + ... + p_n = 1.

Answer 1

Если у вас есть подпространство коразмерности k, это означает, что ваш выпуклый многогранник определяется некоторым числом неравенств и k независимыми равенствами. Таким образом, вы все еще можете использовать модифицированный отбор проб:

1. Найти n-k независимых переменных p_1 через p_ {n-k}.
2. Вычислить возможные диапазоны для этих переменных
3. Образец каждой переменной.
4. Вычисление p_ {n-k + 1} через p_n
5. Принимайте, если оно находится в вашем симплексе, иначе отклоните и повторите.

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