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

Суть вопроса такова: необходимо произвести последовательность случайных нулей/единиц так, чтобы шанс на появление нуля был $%0.95$%, а шанс на появление единицы соответственно $%0.05$%.

Прежде всего, рассмотрим простейший алгоритм:

  1. Сгенериривать случайную равномерно распределённую на $%[0,1)$% величину $%x$%.
  2. Если $%x < 0.95$%, произвести 0, в противном случае -- $%1$%.

Выдаёт ли он действительно случайную величину? (Я отвлекаюсь в данный момент от качества случайной величины, произведённой на шаге 1.)

Затем, рассмотрим альтернативный алгоритм:

  1. Поместить в резервуар (скажем, массив) на $%100$% элементов $%5$% единиц и $%95$% нулей.
  2. Сгенерировать случайную перестановку из $%S_{100}$%, и перемешать ей элементы резервуара.
  3. Выдавать элементы резервуара по одному по запросу. Когда резервуар опустеет, вернуться к начальному шагу.

Преимущество такого метода, по мнению одного из участников, состоит в том, что отношение количества сгенерированных нулей к общему количеству элементов равно $%0.95$% (хотя бы для последовательностей длины кратной ста), и не сильно отклоняется от него для остальных длин.

Другой участник утверждает, что такая последовательность не будет случайной, поскольку элементы с номерами кратными $%100$% предсказуемы.

Как мне кажется, отличие позиций состоит в разном понимании понятия "случайная последовательность". Как вы считаете, какое из пониманий правильнее?


Автор вопроса требует именно появления ровно $%95$% нулей из каждых $%100$% подряд идущих элементов последовательности. Это, конечно, возможно, но не имеет большого смысла: при этом для последовательности $%\{r_i\}$% выходит, что $%r_{k+100} = r_k$% для всех $%k$% (чтобы количество единиц среди элементов

$$r_k, r_{k+1}, ..., r_{k + 99}$$

равнялось количеству единиц среди элементов

$$r_{k+1}, r_{k+2}, ..., r_{k + 100}$$

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

задан 5 Мар '13 21:45

изменен 5 Мар '13 22:27

Казино любого типа - это гадость и безобразие! Не занимаетесь этим! Даже помогать не хочется.

Хотя, конечно, второй подход неверный.

(5 Мар '13 22:17) DocentI

@DocentI: во-первых, казино занимаюсь не я, а автор вопроса, для меня вопрос имеет чисто умозрительный характер.

Во-вторых, не могли бы вы аргументировать, почему именно второй подход неверен? Меня интересовала именно аргументация.

И в-третьих, не вижу спорности вопроса: ведь есть общепринятое среди математиков понимание случайной последовательности?

(5 Мар '13 22:21) VladD

А зачем закрыли вопрос? Я сам крайне негативно отношусь к коммерции. В азартные игры тоже давно не играю (хотя когда-то это было интересно). Но мне кажется, что у вопроса есть какое-то математическое содержание. Тут не лишне вспомнить и о том, что теория вероятностей появилась как раз из анализа азартных игр. Генерация псевдослучайных последовательностей -- это весьма содержательная и обширная научная тема, и мне кажется, что она заслуживает обсуждения.

(5 Мар '13 22:26) falcao

Абстрагировал вопрос от казино :)

(5 Мар '13 22:28) VladD
10|600 символов нужно символов осталось
6

Требование, чтобы среди каждых подряд идущих членов последовательности было ровно 95 нулей представляется мне совершенно непригодным. Конечно, в этом случае последовательность будет периодична, и её исходы станет можно просто выучить.

Даже тот вариант, когда делаются серии из 100 испытаний, и в каждом из них отводятся какие-то 5 случайно выбираемых мест для единиц, смотрится не слишком хорошо. Допустим, я знаю, что это так. Тогда после того, как я выиграл 5 раз или даже 4 раза за начальный промежуток времени, далее имеет смысл выйти из такой игры по причине выполнения "нормы".

Наилучшим, конечно, видится первый способ, то есть использование равномерного распределения на $%[0;1)$% или равновероятного выбора натурального числа от $%1$% до $%100$%. Если тут есть какие-то сомнения относительно "случайности", то можно вместо правого конца отрезка выбирать что-то посередине, или даже в нескольких местах. То же касается чисел: скажем, можно назначить "выигрышными" любые $%5$% номеров. Конечно, если все исходы на самом деле равновероятны, то можно таковыми считать числа от $%1$% до $%5$% или любые другие. Тут чисто психологический эффект срабатывает -- подобно тому, как некоторые люди считают, что в "Спортлото" невыгодно указывать числа, идущие подряд, потому что они никогда не выпадают. (Правда, тут есть другой аспект, связанный с тем, что номера от $%1$% до $%5$% в карточке укажут многие люди, и тогда выигрыш придётся делить на несколько частей, но это не имеет отношения к теме.)

Я также вспомнил сейчас об одном интересном эксперименте, о котором где-то читал. Было две группы испытуемых. Одной из них было дано задание: подбросить $%200$% раз монетку, и записать на бумажке исходы бросаний (скажем, в виде нулей и единиц). Участники второй группы должны были сочинить из головы как бы "случайную" последовательность нулей и единиц, также записав её на листочке. Далее все листочки от обеих групп тщательно перемешали и отдали математикам. Последние сумели безо всякого труда отличить настоящие результаты от выдуманных. При этом использовался весьма простой подход: оказывается, вероятность появления семи и более одинаковых знаков подряд в этом случае достаточно велика, если бросать монетку. А когда человек пытается сымитировать случайный эффект, то он таких длинных последовательностей старается избегать. Это только один из признаков, а есть и другие. Мне кажется, этот пример имеет отношение к обсуждаемому вопросу: неудачно составленную закономерность довольно легко "расколоть".

ссылка

отвечен 5 Мар '13 23:27

Угу, если я не ошибаюсь, у Кнута это называется "проверка серий" (TAOCP 3.3.2B).

(6 Мар '13 0:18) VladD
10|600 символов нужно символов осталось
2

Тут, собственно, вопрос определения. Случайная последовательность - это последовательность из сл. величин. Каких именно - вопрос открытый. В описанной задаче (казино, о котором не хотите говорить) эта последовательность должна состоять из одинаково (видимо, равномерно) распределенных независимых величин.

Никакая уже реализованная последовательность не может считаться случайной. Поэтому считается, что датчики выдают только псевдослучайную величину. То есть похожую.

У хорошей имитации должны быть правильно распределены не только отдельные значения, но и их пары, тройки и т.п. Думаю, есть специальные стандарты для хорошей псевдослучайной последовательности. И периодическая последовательность им явно не удовлетворяет.
Например, автокорреляция такой последовательности с подходящим шагом равна 1, чего в реальном случае быть не должно. В силу независимости отдельных значений.

ссылка

отвечен 5 Мар '13 23:24

изменен 5 Мар '13 23:36

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

(5 Мар '13 23:47) DocentI

В реальном мире для тех задач, где случайность важна, используется "надёжный" аппаратный генератор независимых равномерно распределённых случайных величин в промежутке $%[0, 1)$%. К её случайности обычно нету претензий. В задаче я считал важным не испортить случайность генератора несовершенством алгоритма.

(6 Мар '13 0:22) VladD
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,000
×338
×183

задан
5 Мар '13 21:45

показан
2287 раз

обновлен
6 Мар '13 0:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru