Критерии случайности

[svv]

Андрей АK писал(а):

Многие криптографы тоже так думали ... пока все их шифры ,в конце концов, не взломали.

Я Вам расскажу о своем алгоритме даже очень много. Но не всё.
Я вычисляю функцию Бесселя $J_{\nu}(an)$ до $k$-го знака. $n$-м элементом последовательности является $k$-й десятичный разряд числа $J_{\nu}(an)$.
Я храню в тайне вещественный порядок $\nu$, вещественный коэффициент $a$ и целое число $k$.
Я применяю арифметику с произвольной точностью, поэтому Вы не можете надеяться, что, скажем, вещественные числа занимают 8 байт, а целые 4.
Теперь, положа руку на сердце: сколько Вам потребуется от меня первых элементов последовательности и сколько времени, чтобы разгадать закон?

Андрей АK писал(а):

по длине периода повторения

А как Вы найдёте период повторения? Чему равно $n$ -- количество повторений, после которого Вы приходите к выводу, что "дальше только так и будет"? А если Вы недооценили сложность алгоритма? Каждый год, кратный 4, високосный, но это не вся правда. Каждый год, кратный 100, всё-таки невисокосный, но и это не вся правда. Вот устрою какое-нибудь отклонение через $2n$, нет, через $n!$ повторений, и все Ваши выводы окажутся неверными.

[Черный Евгений]

1) Ответ на вопрос "Может ли последовательность из 0 и 1 быть случайной?" дан падающей монетой с тех пор, когда кто либо захотел положиться на случай. При розыграше полей в футболе это применяется до сих пор.
2) Мы анализируем только конечные числовые последовательности. Для этого придумано множество тестов, которым не надо знать как именно получена последовательность. Здесь в основном собрались люди, обдумывающие идеи (в течении 5-ти, много 10-ти минут). Я проверял последовательность числа ПИ на случайность, нет никаких оснований сомневаться в ней. А мне говорят почти по Станиславскому: "Не верю!" Это не вопрос веры. Нужно в начале заставить себя изучить состояние дел, составить программу, а потом числом показать, что данная конечная последовательность не случайна.

[Андрей АK]

svv в сообщении #414022 писал(а):

Андрей АK писал(а):

Многие криптографы тоже так думали ... пока все их шифры ,в конце концов, не взломали.

Я Вам расскажу о своем алгоритме даже очень много. Но не всё.
Я вычисляю функцию Бесселя $J_{\nu}(an)$ до $k$-го знака. $n$-м элементом последовательности является $k$-й десятичный разряд числа $J_{\nu}(an)$.
Я храню в тайне вещественный порядок $\nu$, вещественный коэффициент $a$ и целое число $k$.
Я применяю арифметику с произвольной точностью, поэтому Вы не можете надеяться, что, скажем, вещественные числа занимают 8 байт, а целые 4.
Теперь, положа руку на сердце: сколько Вам потребуется от меня первых элементов последовательности и сколько времени, чтобы разгадать закон?

Андрей АK писал(а):

по длине периода повторения

А как Вы найдёте период повторения? Чему равно $n$ -- количество повторений, после которого Вы приходите к выводу, что "дальше только так и будет"? А если Вы недооценили сложность алгоритма? Каждый год, кратный 4, високосный, но это не вся правда. Каждый год, кратный 100, всё-таки невисокосный, но и это не вся правда. Вот устрою какое-нибудь отклонение через $2n$, нет, через $n!$ повторений, и все Ваши выводы окажутся неверными.

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

Т.е. можно придумать сложно расшифрованные алгоритмы, но все они могут иметь иерархию сложности и соответствующую скорость расшифровки.

[svv]

Андрей АK писал(а):

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

Усложнение алгоритма обычно сопровождается увеличением его длины? Согласен, какие могут быть вопросы? Насчет "очень" -- я бы так однозначно не утверждал (я программист, для меня выделение 20 бит на число "миллион" -- не проблема). Да и каким образом Вы меня ограничиваете в ресурсах?

Андрей АK писал(а):

Т.е. можно придумать сложно расшифрованные алгоритмы, но все они могут иметь иерархию сложности и соответствующую скорость расшифровки.

Мне кажется, мы с Вами согласны в том, что:
1) существуют классы алгоритмов, в пределах которых найти конкретный алгоритм по результатам его работы можно только перебором;
2) отгадывающий находится в невыгодном положении, поскольку отгадывать алгоритмы много, много сложнее, чем загадывать.
И представляете ли Вы, насколько большие числа можно порождать сравнительно короткими алгоритмами? Вы наверняка слыхали о функции Аккермана. Она очень быстро растёт с ростом аргументов. Посмотрите в статье Функция_Аккермана определение, а потом там же в табличке значение $Ack(5, 4)$, например. Поэтому для гарантированной расшифровки алгоритма Вам придется проанализировать очень большое число элементов последовательности, если я решу использовать алгоритмы подобного рода. Рекурсия -- это страшно.

[Андрей АK]

Очень сложно - не значит невозможно.
Хотя да, сложность расшифровки растет гараздо быстрее скорости шифровки.

[svv]

Андрей АK писал(а):

Хотя да, сложность расшифровки растет гараздо быстрее скорости шифровки.

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

Вы посмотрели про функцию Аккермана? Впечатлило?

[Андрей АK]

Эту функцию я уже раньше знал.
Но мы ведь говорим не о больших числах, а о случайных последовательностях.
Если я с большой точностью буду предсказывать последовательность, ошибаясь только в каких-то редких случаях, типа на расстоянии функции Аккермана, то для приложений это будет все равно важно.
(Как например для предсказания курса валют и акций на бирже)
И небольшая неточность мне не повредит (уже при небольшом проценте правильных предсказаний большие доходы гарантированы)
Если же даже теоретически невозможно подобрать правило для предсказания псевдослучайных величин, то никакие роботы и прочие потуги не смогут ничего сделать на валютном рынке.
Вроде бы такая небольшая разница (возможно/невозможно) а каков результат!

[brimal]

"Что мы знаем о вероятности" АБС Стажеры

(Оффтоп)

Если столько длится дискуссия (будем надеяться,что это дискуссия-где ищут истину,а не спор где возвеличивают свое Я) и нет результата,то не лишне задуматься о причинах. Их собствено две
1. собрались потрепаться (как в пивной в доброе старое время. Каждый предъявляет свое Я (обращаю внимание ПРЕДЪЯВЛЯЕТ, а не ВОЗВЕЛИЧИВАЕТ) и рассчитывает на уважение к нему. Это для души. Истину
не установишь, но люди становятся добрее друг к другу (немного интеллигентнее)). Это тоже благо.
2. Нет общности, которая объединяет. Все расходятся по частностям (Вот и появилась криптология здесь).
Обычная история. Начинаем спорить, не договорившись о дефинициях. Понимаю, что неприятно и сложно
дать определение случайности (Надо уходить в философию. Ну а ваше отношение к ней следует из гуманитарного отдела форума, где RENDALL блистательно защищает философию от своры арифмометров).
Итак, что же такое случайность? Дайте определение, согласитесь с ним (представляю какая будет дискуссия)
и окажется, что обсуждать то и нечего.
Даю определение от АБС (не помню откуда и не дословно): Случайность форма проявления непознаной закономерности

.

[Черный Евгений]

1) "Случайность - непознанная закономерность" - Лаплас, Эйнштейн.
2) "Истинная случайность в природе, нет никакой закономерности" - Эпикур, Гейзенберг, фон Нейман.

[Андрей АK]

Если бы вместо цитат еще и формулы приложить.

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

[PAV]

Андрей АK в сообщении #414646 писал(а):

Например, у истинно случайной величины, функция распределения удовлетворяет закону Гаусса с такой то дисперсией.

А что, кроме нормального распределения других в природе не существует?

Андрей АK в сообщении #414646 писал(а):

Но и сама дисперсия ,для разных участков, имеет средне квадратичное отклонение, подчиняющееся закону Гаусса с другой дисперсией, которая имеет точно такой же закон распределения, как и предыдущие до нее и все последующие.

Абсолютно непонятная фраза.

[Андрей АK]

PAV в сообщении #414680 писал(а):

Андрей АK в сообщении #414646 писал(а):

Например, у истинно случайной величины, функция распределения удовлетворяет закону Гаусса с такой то дисперсией.

А что, кроме нормального распределения других в природе не существует?

Я пытаюсь сформулировать требования к критерию случайности - как он должен выглядеть, какая должна быть формула, чтоб некую последовательность считать случайной.
Распределение Гаусса я назвал как пример.
Конечно- это распределение для непрерывной величины, а мы говорим про дискретные ... но для дискретных величин есть свой аналог.
Нормальное распределение мне представляется правильным выбором - ведь бесконечный набор дискретных величин, можно всегда приблизить к непрерывному распределению ( тем более что дисперсия уже будет не дискретной величиной).

PAV в сообщении #414680 писал(а):

Андрей АK в сообщении #414646 писал(а):

Но и сама дисперсия ,для разных участков, имеет средне квадратичное отклонение, подчиняющееся закону Гаусса с другой дисперсией, которая имеет точно такой же закон распределения, как и предыдущие до нее и все последующие.

Абсолютно непонятная фраза.

Например, для десятичной записи какого-то числа.
Если мы подсчитаем количество разных цифр на определенном участке последовательности , то должна быть одна цифра, встречающаяся чаще всех, другая цифра, встречающаяся чуть реже ... и наконец, самая редко встречающаяся цифра, и , если их расположить в порядке возрастания, то мы должны получить некое распределение.
И у этого распределения должна быть дисперсия - "математическое ожидание квадрата отклонения случайной величины от ее математического ожидания" - но вместо математического ожидания можно говорить о доле вхождения самого часто встречающегося числа.
(Т.е. если на каком-то отрезке число '9' - самое встречающееся, то считаем, что мат ожидание - это число '9')
Точно так же мы можем брать пары чисел, тройки чисел и т.д. строить график распределения и считать его дисперсию.
Например, для последовательности $01234567890123456789...$ вероятность вхождения каждой цифры одинакова ... но вот дисперсия всюду постоянна и максимальна - следовательно, наша гипотетическая формула "критерия случайности" должна этот факт учесть и добавить к коэффициенту упорядоченности лишний балл.
(Для пар, троек ... чисел это уже будет не случайное распределение и этот факт также должен быть учтен в формуле)
Далее, сама дисперсия может меняться от отрезка к отрезку (и её уже нельзя назвать дискретной величиной) - если мы посчитаем дисперсию для разных участков последовательности и составим уже её график распределения ... то этот график также должен удовлетворять всем критериям случайности.
И у него снова должна быть своя дисперсия.
У той уже свой график распределения ...
Ну и т.д.

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

(Хотя до бесконечности -это проверить конечно невозможно)

[venco]

Андрей АK в сообщении #414821 писал(а):

Т.е. если на каком-то отрезке число '9' - самое встречающееся, то считаем, что мат ожидание - это число '9'

Что такое мода и мат-ожидание проходят в третьем классе. Андрей АK, ну зачем Вы лезете в математику? Вы ведь почти ничего не знаете.

[PAV]

+1

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

[Черный Евгений]

1) Для дискретных величин (например последовательность 0 и 1) есть понятие идеального распределения. Его первым сформулировал Паскаль, проанализировав равновероятность всех возможных исходов. Это знаменитый треугольник Паскаля. Его еще называют Биномиальным. Обобщив это распределение на непрерывный ряд, Муавр полулил первое аналитическое выражение, которому окончательную форму придал Лаплас. Сегодня мы называем его нормальным.
2) Всякую не двоичную последовательность можно перевести в двоичную. Если кто-то сомневается и боится, что эта исходная последовательность может утратить элементы случайности при переводе, то легко получить идеальное распределение для N-альтернативного процесса, подобное треугольнику Паскаля для 2-х альтернативного.
3) Конечно, анализируя число ПИ и так и эдак, я нигде не получил полного совпадения с идеальным распределением. (При переводе ПИ в двоичную последовательность расхождения чуть меньше, очевидно за счет того, что последовательность длиннее), Но практически такие же отклонения получаются и при анализе встроенных в языки программирования (Delphi, VBA for app..) генераторов случайных последовательностей. Поэтому у меня есть основания утверждать, что "Последовательность знаков числа ПИ не менее случайна, чем последовательность любого машинного генератора случайных чисел".
4) Критериям случайности нет никакого дела до того, как именно получена та или иная последовательность. Ведь от того, что услышав стихи "Я помню чудное мгновенье..." не в авторском исполнении, мы же не будем утверждать, что они никуда не годятся. Важно что написано, а не как получено.
5) Здесь иногда звучат советы "Куда вы лезете, это же математика, читайте книги". Читаем, и диву даемся когда когда дискретную последовательность сравнивают не с идеальным распределением для дискретных величин, а с непрерывной, которая безусловно не может в полной мере отразить исходную. Что ж на это возразить - читайте Паскаля, а уже потом Муавра и Лапласа.