Есть ли быстрый способ взять образец из подмножества GLn?

Правила этой проблемы довольно специфичны, потому что я на самом деле смотрю на подмножество из GLn, где векторы строк и столбцов должны иметь определенную форму (назовите эти векторы допустимыми - примеры ниже), поэтому, пожалуйста, будьте терпеливы. Вот правила:

1. Вы можете выберите допустимый ненулевой вектор длины n равномерно и случайным образом.

2. Учитывая допустимые векторы v1, v2, ..., vk , вы можете определить, являются ли формируемые ими частичные столбцы префиксами действительных ve ctors (например, встречается ли [v1_1 v2_1 ... vk_1] как первые k записей допустимого вектора)с помощью функции isPrefix .

3. Учитывая допустимые векторы v1, v2, ..., vk, вы можете определить, являются ли они линейно зависимыми, используя функцию areIndependent .

] Цель состоит в том, чтобы выбрать из этого подмножества GLn равномерно случайным образом. Вот наивное решение, которое не работает:

    Step 1: Select a valid v1 uniformly at random. 
            If isPrefix(v1) then Go to Step 2.
            Otherwise repeat Step 1.

    Step 2: Select a valid v2 uniformly at random. 
            If areIndependent(v1,v2) & isPrefix(v1,v2), then go to Step 3. 
            Otherwise, repeat Step 2.

    ...

    Step n: Select a valid vn uniformly at random. 
            If areIndependent(v1,v2,...,vn) & isPrefix(v1,v2,...,vn), then END. 
            Otherwise, repeat Step n.

Проблема с этим потенциальным решением заключается в том, что оно может застрять в бесконечном цикле в не слишком маловероятном событии, которое areIndependent (v1, v2, ... , vk) & isPrefix (v1, v2, ..., vk) правильно возвращает TRUE , но нет способа завершить этот k-кортеж до линейно независимого действительного n-кортежа. Типичный пример этого - когда k = n-1 и существует уникальный допустимый вектор vn такой, что isPrefix (v1, v2, ..., vn) имеет значение ИСТИНА, но этот вектор не независим от предыдущих n-1 векторов.

Поэтому мне нужно каким-то образом добавить резервную копию шага или двух, когда я нахожусь в этом цикле, но я не обязательно знаю, когда я в нем. Я ищу решение в следующих направлениях: Если шаг k не выполняется f (k) раз для некоторой явной функции f , которая может зависеть от распределения допустимых векторов, затем вернитесь к Шагу k-1 (или даже дальше, каким-то явным образом).

Мы будем очень благодарны за любые предложения, комментарии, ссылки и т. д.! Спасибо!

ПРИМЕРЫ:

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

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

 0  1  0
 1 -1  1
 0  1  0

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

Еще раз спасибо всем, кто смотрел на это!