| 0
- 12.12.2013 - 18:43
|
Моя проблема. Модернизируя генератор псевдлслучайных чисел, придумал для тестирования геоиетрическую интерпретацию. По одному его выходному значению формируется координата Х, по другому значению координата У. Точка (Х,У) меняет цвет свой текущий цвет на следующий цвет из массива цветов. В итоге на экране квадрат из цветных точек. Если в квадрате хаотичный набор точек, это будет говорить о приемлимом качестве генератора. Если в квадрате просматривается какая либо закономерность, это будет говорить о плохом качестве генератора. И тут я столкнулся с проблемой. Чтобы не засорять описание ненужными деталями, сведу, без ограаничения общности, к 2-м простым ситуациям. Ситуация 1-я. Две колоды карт перетасовываются (каждая по отдельности) случайным образом. Далее из каждой колоды открывается по одной карте, они образуют первую пару. Аналогично формируются вторая и следующие пары. Когда карты в колодах заканиваются, опять повтояряется тоже самое. И так многократно. Ситуация 2-я. Две колоды карт смешиваются в одну, удвоенную колоду. Эта колода также перетасовываются случайным образом. Затем из колоды по одной окрывается две карты, образующие первую пару. Аналогично формируются последующие пары. Когда колода заканчиваеися, всё опять многократно повторяется Вопрос. Одинакова ли для этих 2-х случаев вероятность выпадения в паре одинаковых (по масти и значению) карт? Моя же геометрическая интерпретация показала, что в первом случае вероятность меньше. Мне это не совсем ясно.     | |
| 1
- 12.12.2013 - 19:46
| Оп, попутал малость. Во 2-и случае вероятность уменьшается. | |
| 2
- 13.12.2013 - 07:25
| В первом случае делали srand() перед снятием карты в каждой колоде? | |
| 3
- 13.12.2013 - 11:43
| 0-Надир > в первом случае никак не получится в паре одинаковые по масти и значению карты =) | |
| 4
- 13.12.2013 - 17:04
|
2-KohaVasin, мой генератор во всех случаях работал на протяжении всех выборок без начального своего сброса, т.е., продолжал формировать свой выходной массив псевдослучайных чисел. Можно попробовать и со сбросом, но эти два случая всё равно работают несколько по-разному, оттого аналогичного случайного распредления не получить. 3-2Late, ну, отчего не получится? Кто мешает первым же ходом из первой колоды извлечь, допустим, туза бубен, и такаую же точно карту извлечь и из 2-й колоды? | |
| 5
- 13.12.2013 - 17:22
| Опишу более подробно суть дела. У меня есть генератор, выдающий псевдослучайное 8-ми битное число, т.е в диапазоне от 0 до 255. При его конструировании я использовал вышеописанную проверку. Выдаваемые генератором числа формировали пару координат Х,У, которые задавали точку на экране. Цвет точки менялся с начальной на следующуюю, из массива цветов, расчитанным так, что точка становилась всё ярче и ярче. Таким образом было видно, как именно формируются случайные числа, хаотично, или нет. Когда цвет достигал своего пика, он сбрасывался в ноль и более не менялся. Т.е. вначале появлялися точки, которые становились всё ярче и ярче, если на них падал выбор, на экране вырисовывался квадрат из точек. Затем, когда квадрат заполнялся, точки постеменно начинали гаснуть. В итоге на экране оставались лишь те точки, на которые выбор падал реже всего. Эти точки не должны были образовывать никаких чётких геометрических фигур - линий, квадратов и пр. И от опыта к опыту эти точки должны были името различное распределение. Вот только тогда можно было сказать, что генератор более-менее качественный. | |
| 6
- 13.12.2013 - 17:33
|
Если запросить у этого генератора 256 чисел, то некоторые из чисел могли повторяться два, или три раза, некоторых в выборке не было совсем. Но для одной из задач мне понадобилоась ситуация, когда из выборки в 256 чисел все бы они были бы выданы ровно по одному разу, т.е. как бы перетасовать колоду карт от 0 до 255 и раздать её. Я модернизировал генератор и стал проверять его на этом стенде. Конечно, я получил хаотичный цветной квадрат, но с абсолютно чёрной диагональю, ибо получить точки с Х=У было в этом случае невозможно. Тогда я изменил генератор так, что он как бы оперировал сразу с двумя независимыми колодами, выдавая в первом случае числи из первой колоды, во втором - из второй. В этом случае геометрический тест прошёл нормально. Тогда я решил упростить задачу и заставить генератор выдавать числа из удвоенной колоды. И вот тут-то я и стал наблюдать этот эффект. Точки на диагонали хоть и стали выпадать (чего не было с одной колодой), но именно они оставались ещё на экране с некоторыми другими хаотичными точками, когда более вероятностные точки потухли, чётко образую диагональную линию. Вероятность их выпадения была ниже, чем у любых других точек. | |
| 7
- 13.12.2013 - 20:20
|
Если взять колоды из трёх карт, то в первом случае итоговая вероятность 0.448888, во втором случае 0.638888 как я считал: в каждом случае всего три шага (P1,p2,p3) вероятность вытаскивания карты на первом шаге очевидна. На втором шаге это вероятность вытаскивания одинаковых карт в случае, когда осталось всего две одинаковые и две разные (на первом то шаге уже вытащили разные) умноженная на вероятность что первый шаг не стрельнет (1-Р). На третьем шаге это фактически вероятность, что на втором шаге мы вытащили две разные карты, но ни одну из тех, что оставались в колодах одинаковыми, ну и умножим это на то, что не стрельнет первый и второй шаги. Думаю что для большого числа карт тенденция будет такая-же. 1. P1=1/5=0.2 P2=2/3*1/3*(1-P1)=0.13333333333 P3=2/4*1/3*(1-P1)*(1-p2)=0.11555555555 P=0.448888888888 2. p1=1/3=0.333333 p2=1/2*1/2*(1-p1)=0.166666666 p3=1/2*1/2*(1-p1)*(1-p2)=0.13888888 p=0.638888888 | |
| 8
- 14.12.2013 - 14:28
|
[quote=Надир;33300120]Моя проблема. Модернизируя генератор псевдлслучайных чисел, придумал для тестирования геоиетрическую интерпретацию. [/quote] проблема в отсутствии базовых знаний об этих генераторах.[quote=Надир;33314722]При его конструировании я использовал вышеописанную проверку. [/quote] Такие генераторы должны создаваться специалистами, прочитавшими и понявшими гоответствующил раздел в великом труде Дональда Кнута Исскуство программирования для ЭВМ, том 2 Получисленные алгоритмы. Остальным использовать готовые, взятые из надежных книг. искать marsaglia random вот уже готовый текст [url]www.stat.berkeley.edu/classes/s243/mother.c[/url] | |
| 9
- 14.12.2013 - 17:40
|
7-GrandKaa, да, я опять всё напутал. Дело в том, что массив тех цветов, что я использовал, был скорее ориентирован для наглядности разброса, но не столько для оценки вероятности. Я переделал немного цветовую иллюстрацию, и тут наглядно стало ясно, что верляьность в случае два выше. Мне интуитивно это не совсем ясно. Я ожидал тного результата. Я продолжил опыты. Я стал использовать три объеденённые колоды, четыре и т.д. Вероятность от опыта к опыту явственно росла. Я увеличил кол-во колод до кол-ва отображаемых мною цветов. Диагональ прорисовывалась всё явственнее, что говорило о больщей вероятности. И как это понимать? Если колод достаточно много, то можно считать, что их и нету вовсе, ибо их влияние будет невелировано. При этом вероятность должна падать, выравниваясь к вероятности остальных точек. Но это-то не так? | |
| 10
- 14.12.2013 - 17:47
|
8-ex_05772, этот генеротор мною написан и давно написан. Он весьма неплох, не хуже библиотечных. Но имеет то неоспоримое превосходство, что его всегда можно подогнать под любые мои текущие требования. И его очередная модификация, которая и стала виновником данной темы, тоже написана и работает. Всё, что тут обсуждается, это так, побочные эффекты тестирования, не более того. | |
| 11
- 18.12.2013 - 09:27
| Выборки из удвоенной колоды следуют непосредственно друг за другом? Попробуйте паузу случайной длительности между выборками ввести. | |
| 12
- 18.12.2013 - 16:59
|
11-KohaVasin, да, выборки идут одна за одной. Генератор устроен так, что пауза между выборками ни на что не влияет. | |
| 13
- 18.12.2013 - 21:20
| Мне представляется следующим образом,возможно ошибаюсь. Допустим условная колода 52 карты. В первом случае вероятность 1/52, а во втором случае вероятность 1/52х2-1. Разве не так? | |
| 14
- 18.12.2013 - 21:35
| 13-MRV_, так-то оно так, но... Вы расчитали вероятность для первой и единственной пары. А что там дальше? | |
| 15
- 19.12.2013 - 08:40
|
"более вероятностные точки [em]потухли[/em], чётко образую диагональную линию" А как вы отличаете потухшие по факту точки от тех, которые и не "зажигались"? Т.е. какова динамика этой диагонали, например, во 2м случае? | |
| 16
- 19.12.2013 - 20:19
|
[quote=Надир;33327015]8-ex_05772, этот генеротор мною написан и давно написан. Он весьма неплох, не хуже библиотечных. [/quote] Я уже высказался по поводу самопала. Ну не надо лезть и самому писать генератор равномерно распределенных случайных чисел. Потому как потом будет гораздо хуже. Первый мой подвиг был именно в доказательстве того, что результаты по теории отличаются от моделированных именно в использовании плохого генератора, которым у нас все пользовались. Получил ценный приз - 3л прекрасного грузинского портвейна. | |
| 17
- 19.12.2013 - 20:30
|
[b]Надир[/b], очень интересно с визуализацией, а почему бы не взять проверенное временем и математически доказанное Гаусово распределение? [url]http://ru.wikipedia.org/wiki/Нормальное[/url] распределение | |
| 18
- 20.12.2013 - 16:27
| 15-AD13, алгоритм визуализацтт таков. По начальному пуску весь квадрат всплошную закрашивается яркими красными точками. Далее закраска идёт уже по мере выпадения точек. Начинается от тёмно-голубых и до ярко-голубых. Затем ярко-голубые переходят в ярко-белые, которые тускнеют до чёрного. Всё, чёрный так и остаётся, если даже на него продолжают выпадать точки. Таким образом, наиболее чаще выпадающее точки будут на первой фазе гореть более ярким цветом, на второй же фазе будут тёмпыми до чёрного. Менее выпадающие точки, наоборот, вначале будут более тёмными, а потом останутся светнлыми на тёмном фоне. Первую фазу от второй отдичает сам цвет голубой-белый. Точки же, на которые выбор так и не пал остануьмя красными на чёрном фоне. | |
| 19
- 20.12.2013 - 16:29
|
16-ex_05772, ну не стану я оспаривать Ваше мнение. Я сделал это чисто для себя. Меня устраивает. Кстати, проверил библиоьечный генератор (язык С), результат один в один с моим. | |
| 20
- 20.12.2013 - 16:35
| 17-Арегнидёрш Ток, да можно взять, чего не взять. Но хотел сделать сам. Может это и глупо, но я люблю кое-что делать сам. На разделе Фото меня осмеяли, что я взялся за графический редактор и HDR-свёртку фотоснимков для формата BMP. Но ведь сделал... | |
| 21
- 20.12.2013 - 16:55
|
Кстати, заметил ещё одну странность. Я выбор карт, то бишь, точек из диапазона 0-255 органнизовал банально просто. Каждой точке привязан счётчик. Вначале все нули. Если выпадает число, счётчик становмися единицей. Нсли колода одна, это предел. Если две - счётчик может достигать двойки. Если генератор опять выбирает число, которое уже выбрано, я запускаю генератор до тех пор, пока он не выберет число из диапазона невыбранных. Вот именно при такой организации и прорисовывалась тонкая одно-точечкая диагональ. Но тут подумал, а что если не запускать генератор многократно, а запускать его тольео один раз для каждой точки. Если же его выбор пал на точку, которая уже была выбрана, то просто сдвигаться влево, или вправо на один по диапазону 0-255, до тех пор, пока не наткнусь на невыбранную точку. Вроде ничего особого, ожидал тот же результат, только с более щустрой работой, но нет. Диагональ-то прорисовалася, но уже более толстая, как минимум из трёх точек. Причём, средняя линия была более вероятностка, чем переферийные. Когда же стал сдвигаться по диапазону на три числа, диагональ вообще растолстела чуть ли не четверть самого квадрата. Не знаю пока, как это понимать... | |
| 22
- 20.12.2013 - 20:24
|
вероятность, возможно, и не одинакова в этих случаях Не знаю, может пригодиться идея... Думаю, можно попробовать оценить, используя дерево-вероятностей n 0 +/ \- n-1 0 0 +/ -\ +/ \- n-2 0 0 0 0 ... На каждом уровне оно вертится, + ситуация, когда карты совпали, - не совпали Тогда вероятность выпадения пары на каждом уровне, будет равна сумме выпания веростности в кружках (т.к. по всем случаям, как мы в эту ситуацию пришли), ну а общая вероятность - суммирование вероятностей по уровням. Тогда на уровне n вероятность выпадения дублей будет 1/n На уровне: n-1 для первого случая, если в первый раз совпало вероятность 1/(n-1) если не совпало (n-2)/((n-1)(n-1)), n-2 - количество возможных дублей, с учетом, что 2 карты выпали т.е. не уже не могут дуплиться, а (n-1)(n-1) - всего возможныйх вариантов выпадения для второго случая, если в первый раз совпало, вероятность такая же 1/(n-1), а для ситуации, когда не совпало (n-2) также, количество возможных дуплетов, но количество вариантов вообще, будет другое... у нас одна колода и выпали две разные карты, значит походи еще по одно остались, тогда первую карту мы можем выбрать n -способами, а вторую (2/n*(n-1)+(n-2)/n*n), 2/n - вероятность, что выпадет одна из уже выпавщих, тогда следующая может быть из (n-1) вариантов, т.к. один вид карт уже закончился, а (n-2)/n - вероятность того, что попадутся еще не выпавшие и в этом случае выбирать можно из n вариантов. Если мы раскроем скобки, то в первом случае у нас n(2)-2n-1, а во втором n(2)-2, в первом случае, число будет всегда меньше, (2n>1 при любом натуральном n), оно стоит в знаменатели, значит - сама вероятность больше.... т.е. на (n-1) уровне уже есть перекос для первого случая... правда, на других это может скомпнсироваться случаями, когда несколько несовпадений подряд, они появяться уже на след. уровне, у меня не хватило обсессии их оценить... Но, в принципе, там главное правильно и аккуратно расписать все возможные выпадания карт на этом уровне для второго варианта, учитывая, что они могут совпадать с уже выпавшими... в общем виде, думаю, решить не реально... но можно загнать в процедуру - для каждого уровня, алгорит,думаю схож... и опытными путем, посмотреть, что будет... | |
| 23
- 18.01.2014 - 21:14
| Для оценки качества генератора, попробуйте распределение точек не на плоскости, а в 3-х мерном пространстве, по координатам x,y,z. Может случится, что увидите явные плоскости из точек в трёхмерном кубе. | |
| 24
- 19.01.2014 - 03:44
|
[quote=AleM;33768077] Может случится, что увидите явные плоскости из точек в трёхмерном кубе.[/quote] Специально для многомерности придуман спектральный тест. Который опечалил многих юных и неопытных. Потому что они использовали очень плохие генераторы и проверяли их хорошесть слабыми тестами. Чтите Кнута. | |
| 25
- 19.01.2014 - 14:02
|
[quote=x_05772;33770328] Потому что они использовали очень плохие генераторы и проверяли их хорошесть слабыми тестами. Чтите Кнута. [/quote] Трёхмерный тест именно из Кнута, если я не ошибаюсь. Им нашли плохость генератора случайных чисел от IBM кажется. Но могу ошибаться, последний раз читал Кнута в 1992 году когда изучал алгоритмы арифметики многократной точности. | |
| 26
- 19.01.2014 - 14:44
|
[quote=AleM;33773673]Трёхмерный тест именно из Кнута, если я не ошибаюсь.[/quote] совершенно верно [quote=ex_05772;33324504]Такие генераторы должны создаваться специалистами, прочитавшими и понявшими гоответствующил раздел в великом труде Дональда Кнута Исскуство программирования для ЭВМ, том 2 Получисленные алгоритмы. [/quote] | |
| 27
- 19.01.2014 - 15:27
| Слышал, что Intel в свои современные процессоры встраивает аппаратный генератор случайных чисел, не пробовали проверить насколько он хорош ? | |
| 28
- 19.01.2014 - 20:20
|
[quote=AleM;33774738]Intel [/quote] Ватсон, это же элементарно [url]http://ru.wikipedia.org/wiki/RdRand[/url] С одной стороны хорошо - ничего не надо придумывать. С другой - временами надо прогнать счет с теми же данными но другой обработкой. Для этого нужны псевдослучайные числа. У того же Кнута есть очени интересные рассуждения о том, что такое случайность. | |
| 29
- 19.01.2014 - 20:22
| Попробую 3-х мерное тестирование... | |
| 30
- 20.01.2014 - 10:40
|
GVCV надо не придумывать свой генератор, а применить хорошо известные, для которых доказано, что они близки к идеальным. Кроме того, есть готовый набор тестов [url]http://ru.wikipedia.org/wiki/Тесты_diehard[/url] | |
| 31
- 20.01.2014 - 11:16
| Верно. Ничего придумывать не нужно. Всегда и везде использовать только готовые решения. Думать вредно. | |
| 32
- 20.01.2014 - 18:13
|
[quote=KohaVasin;33784519]Думать вредно.[/quote] Не думать гораздо вреднее. | |
| 33
- 21.01.2014 - 16:38
| 3-х мерное тестирование генератора прошло успешно. | |
| 34
- 25.01.2014 - 22:10
| Совершенно непонятно, нужен ли самке мелкого рогатого скота меховой духовой инструмент? | |
| 35
- 27.01.2014 - 16:52
|
34-x_05772, удобсто управления генератором. Имея полный контроль над собсвенным генератором, я использовал его, например, для программы криптозащиты. Ну вот, хотя бы - это. | |
| 36
- 07.02.2014 - 13:52
|
Надир, генератор случайных чисел так проверить невозможно (с цветами, на глазок). Вот самая тупая, но боле-мене приемлемая проверка: Надо взять 256 счетчиков, запустить генератор 2560000 раз и по каждому результату увеличивать свой счетчик. Сразу будет видно, равны ли вероятности. Дальше надо проверить, нет ли зависимости между соседними результатами. Для этого заводим 511 счетчиков (c[-255] , c[-254], ... , c[k], ... , c[253] , c[254] , c[255]). Запускаем генератор N+1 раз и каждым k-ым счетчиком считаем, сколько раз X[i+1]-X[i]=k. По-нормальному, должно получиться треугольное распределение: соотношение значений счетчиков близкое к 1:2:3:4: ... :254:255:256:255:254: ... :3:2:1 (256 – для с[0]). Если не так, то генератор плохой. Если так, то это еще ничего не значит. Из описания про чёрную диагональ понятно, что соседние значения зависимы: вероятность одного и того же числа подряд =0 (c[0] = 0 будет). Баг алгоритма. По-хорошему, надо делать проверку статистической гипотезы о соответствии распределения равномерному (напр., по хи-квадрат), смотреть автокорреляционную функцию. Лучше велосипед не изобретать, а написать по известному алгоритму. «Полный контроль над собсвенным генератором» никуда не денется, а работать он будет нормально. Правда, непонятно, что за «контроль»? | |
| 37
- 08.02.2014 - 00:48
|
[quote=Надир;33885176]34-x_05772, удобсто управления генератором.[/quote] А вот это категорически не надо. Задается начальное значение, seed. Алгоритмы НАДЕЖНЫХ генераторов и тестов давно известны. У них есть важные плюсы 1 статистические свойства генераторов находятся из теории 2 набор тестов разнообразен и позволяет оценить качество генераторов Хороший пример - разбор Кнутом рекуррентного алгоритма умножь, раздели, получи остаток. У того же Кнута есть пример генератора, придуманного так, что вроде бы он надежен, так как состоит из нескольких методов. Однако при проверке быстро зацикливался. [quote=Надир;33885176]я использовал его, например, для программы криптозащиты.[/quote] Вот это - полный Alopex lagopus. Во всех умных книжках по криптографии есть специальный раздел о генераторах псевдослучайной последовательности. [quote=Дюша;34043519]По-хорошему, надо делать проверку [/quote] По хорошему, не надо изобретать велосипед. | |
| 38
- 08.02.2014 - 09:27
|
[QUOTE=x_05772] По хорошему, не надо изобретать велосипед. [/QUOTE] Про велосипед я написал в следующей строчке после процитированной. Но если уж кому-то по каким-то причинам нужно именно изобрести СВОЙ велосипед, то уж нужно позаботиться, чтобы колеса крутились. А это, скорее всего, лучше сделать без изобретений колеса, о чем я и написал. Надеюсь, все аналогии понятны | |
| 39
- 12.02.2014 - 23:39
| а как может замкнутая, в каких-то определенных пределах, система вдруг стать идеальным генератором случайных чисел? | |
Интернет-форум Краснодарского края и Краснодара |
