Обозначим ДСЧ0 датчик случайных чисел "мощности" 1000, который за первые 1000 последовательных вызовов выдаёт в случайном порядке числа от 0 до 999 (например: 666, 1, 113 ...), а потом "зацикливается", то есть начинает повторно выдавать ту же последовательность чисел (666, 1, 113...), и далее так и выдает их такими "циклами" по 1000 чисел.

Построим на основе ДСЧ0 следующий датчик случайных чисел ДСЧ:

1) возьмем массив размером 1000 ( M(0 to 999) ) и заполним его как-нибудь числами от 0 до 999, например, по возрастанию (0, 1, 2, 3 ... 999);

2) создадим переменную А ("адрес") с начальным значением 0;

3) при каждом вызове ДСЧ будем поступать следующим образом:

а) вызываем ДСЧ0: Х0 = ДСЧ0();

б) увеличиваем А на Х0 по модулю 1000: А = (А + Х0) mod 1000;

в) берем число по адресу А в качестве "выхода" ДСЧ: ДСЧ = М(А);

г) сохраняем Х0 в ячейке А (вместо "использованного" значения): М(А) = Х0.

Вопрос: будет ли "зацикливаться" ДСЧ, а если будет, то начиная с какого "шага" (вызова) и с каким периодом?

Barlone,

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

В описанной в посте конкретной реализации этой идеи конкретные порождаемые ею параметры 499500 и 1000 получились соразмеримы, и из-за этого "увеличение мощности" оказалось незначительным. Но ведь можно сделать размер буфера не 1000,а 997 (например)...

... Но ведь можно сделать размер буфера не 1000,а 997 (например)...

Или не экономить на вызовах ДСЧ0 и реализовать схему:

А=ДСЧ0()
ДСЧ=М(А)
М(А)=ДСЧ0()

-- которая концептуально даже проще (тем, что не нужно заморачиваться с "арифметикой" приращения адреса А)

kealon(Ruslan),

1) должна быть основана на "слабом" датчике случайных чисел (с коротким циклом);

2) должна иметь намного больший цикл, в пределе -- вообще его не иметь.

-- типа, не более, чем N*ЧислоПерестановок(N)?

Обозначим для простоты последовательность, повторения которой мы ждём, -- 1, 2, ... N. Предположим, что после неё -- не позже чем через N*ЧислоПерестановок(N) вызовов ГСЧ -- мы наконец снова увидели эту ( 1, 2, ... N ) последовательность. Но появится ли после неё (после значения N) то же самое следующее значение, которые появилось -- после N -- в первый раз?

Basil A. Sidorov,

понятно, что если однажды при некотором значении А0=ДСЧ0() -- "состояние" массива М будет в точности (во всех ячейках!) тем же самым, которое было ранее при некотором предыдущем появлении этого А0, то в этой точке ряд значений ДСЧ зациклится.

-- одномерное распределение, то есть распределение рассматриваемых по отдельности значений в ряду, возвращаемом ДСЧ()? Да, равномерное, точнее -- такое же, как и у ДСЧ0; а поскольку оно равномерное, то и от ДСЧ мы вправе требовать равномерности.

-- это мне напоминает коллизию, которая была в Как отбирать из потока 1/1000 лучших экземпляров? :

я говорю: в трубе течёт вода, нужно делать с этой водой то-то и то-то.

мне отвечают: сколько там той воды! вырой бассейн, собери в него всю воду и делай спокойно с водой в бассейне своё "то-то и то-то".

Aleksandr Sharahov,

задача -- повысить "мощность" ДСЧ (как и сказано в 22354962 )

Aleksandr Sharahov,

задача -- повысить "мощность" (имеющегося) ДСЧ, а не сделать (взять из литературы или даже из исходников) ДСЧ.

mayton,

у меня в VB (VBA, на самом деле) один стандартный (и не клонируемый) ДСЧ -- Rnd(). Которому я доверяю в том смысле, что если он и косячит -- то это хотя бы не моя вина.

(Да, у него, конечно, период не 1000, а типа 17 миллионов. 1000 я здесь взял просто для простоты.)

да, и с ним тоже.

Barlone,

кстати, в вашей цитате очень мило прозвучало "чтобы получить миллионы и миллионы случайных чисел"...

так я поэтому и обсуждаю не "один генератор", а "генератор с буфером"...

поиск методом квази-Монте-Карло квазирегрессионных квазипредсказательных соотношений для выбора акций из списка NASDAQ-100 для биржевой игры методом однодневного перекладывания из (какой-либо) одной в (какую-либо) другую.

Требования на мощность ДСЧ возникают потому, что на каждую проверяемую точку в монтекарловом пространстве "расходуется" 100 вызовов ДСЧ, то есть формально от "мощности" 16 миллионов остается 16М/100 = 160К.

mayton,

у меня всю дорогу VBA внутри MS Access 2003 .

Basil A. Sidorov,

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

Basil A. Sidorov,

[продолжается оффтопик] значит я не (правильно) понял, про какую "при необходимости, подтянутся маркет-мейкеры" вы высказались... но не суть, объяснять не надо.

Basil A. Sidorov, мне совершенно не нужно "предвидеть неслучайную компоненту рынка".

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

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

Basil A. Sidorov, я вам больше скажу: мне настолько не нужно "предвидеть неслучайную компоненту рынка", что я даже не ощущаю потребности ни обдумывать, ни обсуждать, что это такое и существует ли она.

Вы утверждаете, что маркетмейкеры "неслучайно" грызут друг друга? Мне наплевать.

Вы утверждаете, что маркетмейкеры "неслучайно" поедают значительную часть, возможно даже большую часть мелких игроков? Мне наплевать.

kealon(Ruslan),

если я разделяю на "два потока" четные и нечетные члены ряда псевдослучайных чисел, выдаваемых ДСЧ0 (как я и предложил в 22354995 ) -- то это "один генератор" или "два генератора"?

kealon(Ruslan),

подвох состоит в том, что мы не можем так просто некоторое время пользоваться одним потоком и не пользоваться другим, потому что этот второй поток невозможно остановить, ибо каждое второе возвращаемое ДСЧ0 число полюбасу есть второй поток. То есть "остановленный" (за временной ненадобностью) поток нужно будет или буферизовать, или выбрасывать.

Впрочем, в том варианте, который я обсуждаю:
А=ДСЧ0()
ДСЧ=М(А)
М(А)=ДСЧ0() -- это не два совершенно независимых "потока", а просто разное использование четных и нечетных членов. Разное, но совместное.