Случайность и закономерность

[nikov]

gris писал(а):

Разве это задача? Чего то я не встречал математических задач с вопросом Как вы думаете?

Вполне задача. Польза арифметики - не только в развитии ума, но и в применимости при пересчете реальных предметов, а польза теории вероятностей - применимость при оценки рисков и принятии решений относительно реальных процессов, в которых присутствует случайность.

[gris]

Если достаточно много раз подбрасывать монетку, то вероятность получения вообще любой последовательности любой определённой длины будет стремиться к 1.

Уже несколько раз в помогите решить/разобраться спрашивали про вероятность выпадения решки после 10 орлов подряд. Ну большинство населения уверено, что она больше 1/2. Так и с Вашим опросом. Большинство тех, кто ответил 123 или 4 просто прикалывались.

Задача эта не поставлена. Или поставлена очень и очень нестрого, что допускает различные трактования.

[AD]

А если так поставить: Вот вы выходите в интернет по диалапу, динамический IP-адрес, и вы замечаете, что у вас адрес 111.111.111.111 . Вы сильно удивитесь? А если 236.73.83.162? Думаю, что меньше, да?

(Адреса брал первые попавшиеся, сходство с реальными случайное, if any).

Как измерять удивительность?

_________________
"Принцип наименьшего удивления": Программа должна работать так, чтобы вызывать наименьшее удивление у пользователя.

[gris]

AD, я сильно удивлюсь в обоих случаях. Во-первых эти айпишники не входят в пул адресов моего провайдера. Откуда им взяться? Во вторых у меня нет диалаповского модема. Да и вообще - в интернет по диалапу? Это не гламурно. Может быть ещё в клуб в телогрейке заявиться?

[ewert]

nikov в сообщении #208506 писал(а):

Как вы думаете, какая из последовательностей, скорее всего, была получена подбрасыванием монетки? Почему?

Третья. По критерию хи-квадрат или ещё какому-нибудь непараметрическому.

[Лукомор]

Вот четыре последовательности:

1) 00111100000100110100000111010111101000111101011010

2) 00111100000100110100000110101000010111000010100101

3) 00000000000000000000000000000000000000000000000000

4) 01101001010001100001010010000010111101101000001111

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

[worm2]

В качестве меры случайности некоторой последовательности можно взять её энтропию. А именно, каждой последовательности из некоторого множества M можно сопоставить энтропию следующим образом:

1) Отсортируем всевозможные программы для Машины Тьюринга (МТ) в лексикографическом порядке (начиная от самых коротких);
2) Выкинем из полученной на предыдущем шаге последовательности (ПНПШП) некорректные и те, которые не останавливаются;
3) Выкинем из ПНПШП те, которые НЕ выдают в результате последовательности из множества M;
4) Из ПНПШП выкинем повторяющиеся элементы;
5) Каждому элементу ПНПШП сопоставим натуральное число, равное длине соответствующей программы для МТ.

В результате мы поставим каждому элементу из множества M длину минимальной программы для МТ, выдающей эту последовательность. Чем больше длина, тем более случайным можно считать число.

По-моему, это похоже на Колмогоровское определение энтропии, лень сверяться.

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

[gris]

Представляю, как к nikov заявится человек с Машиной Тьюринга в рюкзаке.

[nikov]

worm2 писал(а):

И, бьюсь об заклад, согласно такому определению последовательность 3 будет более случайна.

И что отсюда следует? Вероятность, что именно она была получена подбрасыванием монетки очень велика? Или очень мала?

[Nxx]

Точно третья.

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

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

[gris]

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

[AlexDem]

Nxx в сообщении #209080 писал(а):

Энтропия ее выше

Не понимаю, чем народу не понравилось моё решение на предыдущей странице на основе "красивых" и "некрасивых" последовательностей??? Если мы априори объявим "красивыми" другие последовательности, то вероятность получить одну из них при одной-единственной серии бросков монеты будет так же мала, как и вероятность получения последовательностей 1, 2 и 4... К тому же мы с gris про энтропию вроде всё сказали...

[Pi]

Корреляция!!! Точнее автокореляция.

Берете вычисляете коэффициенты корреляции при каждой сдвижке.
Та последовательность у которой максимальный по абсолютной величине коэффициент корреляции будет ближе к нулю, та и есть самая "случайная".

Если есть коэфициент корреляции по абсолютной величине равной единице то последовательность "детерминированная".

Полностью отделить мух от котлет ("детерминированная" - "случайная") мы конечно можем только в случае "бесконечной" последовательности (и "очень" большим окном, в случае прямого статистического учета).

[Лиля]

nikov в сообщении #208506 писал(а):

Как вы думаете, какая из последовательностей, скорее всего, была получена подбрасыванием монетки? Почему? Какова вероятность того, что это 1-ая последовательность? 2-ая? 3-я? 4-я?

почему мне кажеться 3я.....

смотрю я на последовательности 1,2,4 и вижу в них порядок что я думаю?-их вероятность маленькая....

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

а если рассматривать последовотельность 3 вне ее "хорошести" то ее вероятность точно такая как и у 1,2,4

[AlexDem]

Лиля в сообщении #209105 писал(а):

хотя если рассматривать последовотельность 3 вне ее "хорошести" то ее вероятность точно такая как и у 1,2,4

Дело в том, что на 3-ем месте стоит не какая-то конкретная, чем-то выделенная, последовательность, а первая попавшаяся при бросании монет. То есть, там по сути - сумма вероятностей всех плохих... Просто потому, что у нас по условию дано, что одна и только одна из последовательностей получена однократной серией бросков монеты (если я верно понял условие). Вероятность первой, второй и третьей последовательностей - по $2^{-50}$, а всё остальное (ну, кроме, может ещё трёх столь же красивых последовательностей, полученных инвертированием) от единицы приходится на третью.

Добавлено спустя 8 минут 50 секунд:

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