Здравствуйте, dilmah, Вы писали:
D>уже 100 раз написали и доказали, что такого распределения нет.
А где сказано, что там одно распределение? Может быть, устройство запоминает выданные числа и выдает новое число, пользуясь симметричным распределением на (N\{выданные числа}) с медианой, равной последнему выданному.
Здравствуйте, batu, Вы писали:
B>Здравствуйте, deniok, Вы писали:
D>>Здравствуйте, batu, Вы писали:
B>>>А ты в школе не учил как обращаться с бесконечностями? Возьми отношение для любого N и устреми N к бесконечности..
D>>Ну беру [-N;2N] D>>
D>>P([-N;0])=1/3
D>>P([0;2N])=2/3
D>>
D>>Устремляю N к бесконечности, вероятности не меняются. B>Извини.. Я не помню как вопрос был поставлен.. На диапазоне [0;2n] вероятность получить положительное равна 1..
Вопрос был: откуда 1/2 в (1/2)^9. Предложение было — взять равномерное на отрезке и растягивать в обе стороны, перейдя к пределу. Ну я взял равномерное на [-N;2N] и растянул.
Вроде результат обладает главным ожидаемым свойством: ни один из исходов не предпочтительнее никакого другого. Скажем, вероятность любого значения в дискретном случае равна 1/(3*N) (если один конец в диапазон не включать, т.е делать предельный переход над полуинтервалом [-N;2N) — это чисто техническое замечание). А в непрерывном случае 1/(3*N) — вероятность выпадения числа из любого интервала единичной длины.
Здравствуйте, deniok, Вы писали:
D>Здравствуйте, batu, Вы писали:
B>>Здравствуйте, deniok, Вы писали:
D>>>Здравствуйте, batu, Вы писали:
B>>>>А ты в школе не учил как обращаться с бесконечностями? Возьми отношение для любого N и устреми N к бесконечности..
D>>>Ну беру [-N;2N] D>>>
D>>>P([-N;0])=1/3
D>>>P([0;2N])=2/3
D>>>
D>>>Устремляю N к бесконечности, вероятности не меняются. B>>Извини.. Я не помню как вопрос был поставлен.. На диапазоне [0;2n] вероятность получить положительное равна 1..
D>Вопрос был: откуда 1/2 в (1/2)^9. Предложение было — взять равномерное на отрезке и растягивать в обе стороны, перейдя к пределу. Ну я взял равномерное на [-N;2N] и растянул.
D>Вроде результат обладает главным ожидаемым свойством: ни один из исходов не предпочтительнее никакого другого. Скажем, вероятность любого значения в дискретном случае равна 1/(3*N) (если один конец в диапазон не включать, т.е делать предельный переход над полуинтервалом [-N;2N) — это чисто техническое замечание). А в непрерывном случае 1/(3*N) — вероятность выпадения числа из любого интервала единичной длины.
D>Тем не менее 1/2 не вышла. Такие дела.
Диапазон -N;2N не соответствует условию задачи. Это означает все отрицательные числа, и только четные положительные. Надо брать диапазон -N;N тогда все станет на свои места.
Здравствуйте, batu, Вы писали:
B>Диапазон -N;2N не соответствует условию задачи. Это означает все отрицательные числа, и только четные положительные. Надо брать диапазон -N;N тогда все станет на свои места.
Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, deniok, Вы писали:
D>>>>Ну беру [-N;2N] D>>>>
D>>>>P([-N;0])=1/3
D>>>>P([0;2N])=2/3
D>>>>
D>>>>Устремляю N к бесконечности, вероятности не меняются.
F>>>Кто сказал, что вероятности не меняются?
D>>Ну меня в школе учили, что предел константы — это константа.
F>Ну, ты изначально сравниваешь неравномощные множества, а потом внезапно оказывается мощность одинаковая.
Неправда (точнее я не до конца понимаю твой "мощностный" язык). У меня честное равномерное распределение: вероятность каждого единичного интервала (в непрерывном случае) и каждого значения (в дискретном) равна 1/(3*N). То есть мой генератор (с точки зрения условий задачи) ничем не хуже того, который получается предельным переходом над [-N;N].
Здравствуйте, deniok, Вы писали:
F>>Ну, ты изначально сравниваешь неравномощные множества, а потом внезапно оказывается мощность одинаковая.
D>Неправда (точнее я не до конца понимаю твой "мощностный" язык). У меня честное равномерное распределение: вероятность каждого единичного интервала (в непрерывном случае) и каждого значения (в дискретном) равна 1/(3*N). То есть мой генератор (с точки зрения условий задачи) ничем не хуже того, который получается предельным переходом над [-N;N].
На пальцах.
Для конечных N (кроме случая N == 0) у тебя между левой ([-N,0]) и правой ([0, N])частями всегда можно поставить знак строго "<" по признкаку мощности множества (оно совпадает с количеством элементов в нём). Но при переходе к бесконечности теряется строгость знака. А в случае предельного перехода над [-N;N] отношение (равенство) сохраняется.
Именно поэтому в первом случае происходит разрыв в "пределе константы".
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, deniok, Вы писали:
F>>>Ну, ты изначально сравниваешь неравномощные множества, а потом внезапно оказывается мощность одинаковая.
D>>Неправда (точнее я не до конца понимаю твой "мощностный" язык). У меня честное равномерное распределение: вероятность каждого единичного интервала (в непрерывном случае) и каждого значения (в дискретном) равна 1/(3*N). То есть мой генератор (с точки зрения условий задачи) ничем не хуже того, который получается предельным переходом над [-N;N].
F>На пальцах.
F>Для конечных N (кроме случая N == 0) у тебя между левой ([-N,0]) и правой ([0, N])частями всегда можно поставить знак строго "<" по признкаку мощности множества (оно совпадает с количеством элементов в нём). Но при переходе к бесконечности теряется строгость знака. А в случае предельного перехода над [-N;N] отношение (равенство) сохраняется.
F>Именно поэтому в первом случае происходит разрыв в "пределе константы".
А у вас то же самое происходит с мощностями [-N;5] и [5;N]. И что?
PS Я в этой ветке пока не вижу рассуждений, которые бы дали 1/2 в выражении (1/2)^9. Более строгих, чем "У прямой два конца, нам мил один, ergo 1/2".
F>>>>Ну, ты изначально сравниваешь неравномощные множества, а потом внезапно оказывается мощность одинаковая.
D>>>Неправда (точнее я не до конца понимаю твой "мощностный" язык). У меня честное равномерное распределение: вероятность каждого единичного интервала (в непрерывном случае) и каждого значения (в дискретном) равна 1/(3*N). То есть мой генератор (с точки зрения условий задачи) ничем не хуже того, который получается предельным переходом над [-N;N].
F>>На пальцах.
F>>Для конечных N (кроме случая N == 0) у тебя между левой ([-N,0]) и правой ([0, N])частями всегда можно поставить знак строго "<" по признкаку мощности множества (оно совпадает с количеством элементов в нём). Но при переходе к бесконечности теряется строгость знака. А в случае предельного перехода над [-N;N] отношение (равенство) сохраняется.
F>>Именно поэтому в первом случае происходит разрыв в "пределе константы".
D>А у вас то же самое происходит с мощностями [-N;5] и [5;N]. И что?
В этом случае отношение между мощностями множеств стремится к 1. Поэтому скачок на бесконечности незаметен. Но это не значит, что его нет.
D>PS Я в этой ветке пока не вижу рассуждений, которые бы дали 1/2 в выражении (1/2)^9. Более строгих, чем "У прямой два конца, нам мил один, ergo 1/2".
А я в ветке не увидел как при комбинаторном решении отработали ситуацию неполучения числа / невозможности сравнения.
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, Аноним, Вы писали:
А>1. Допустим есть некое абстрактное устройство с кнопкой, которое при нажатии на кнопку выдает случайное целое (integer) число от -бесконечности до +бесконечности А>кнопку нажимают 10 раз — какова вероятность что все числа в возрастающем порядке ?
А>2. А если заменить в условии целые числа на вещественные (real) ?
1. Обозначим Y случайную величину, порождаемую абстрактным устройством. Пусть эта величина имеет ряд распределения:
P {Y = k} = p_k >= 0, p_k — сходящийся ряд с суммой 1.
Нажатие кнопки 10 раз порождает новую случайную величину W, значениями которой будут упорядоченные 10-ки целых чисел:
(k1, k2, ..., k10). Ряд распределения этой случайной величины есть:
P {W = (k1, k2, ..., k10)} = P{Y = k1} * P{Y = k2} * ... * P{Y = k10} = p_k1 * p_k2 * ... * p_k10.
Нас интересует следующая вероятность:
P { W из множества { (k1, k2, ..., k10) | k1 < k2 < ... < k10} } = \sum_{k1=-\infty}^{\infty} \sum_{k2=k1 + 1}^{\infty} \sum_{k3=k2 + 1}^{\infty} ... \sum_{k10=k9 + 1}^{\infty} P {W = (k1, k2, ..., k10)} =
\sum_{k1=-\infty}^{\infty} \sum_{k2=k1 + 1}^{\infty} \sum_{k3=k2 + 1}^{\infty} ... \sum_{k10=k9 + 1}^{\infty} p_k1 * p_k2 * ... * p_k10.
Рассмотрим пример. Пусть P {Y = k} = 1 / 2^k, k > 0, P {Y = k} = 0, k <= 0.
Чтобы не загромождать техническими подробностями получим результат для 2-х нажатий (для 10 аналогично, только выкладки длиннее):
p = \sum_{k1=-\infty}^{\infty} \sum_{k2=k1 + 1}^{\infty} 1 / 2^k1 * 1 / 2^k2 = \sum_{k1=-\infty}^{\infty} 1 / 2^k1 \sum_{k2=k1 + 1}^{\infty} 1 / 2^k2 =
\sum_{k1=-\infty}^{\infty} 1 / 2^k1 * 1 / 2^k1 \sum_{i=1}^{\infty} 1 / 2^i = 1/2 * \sum_{k1=-\infty}^{\infty} 1 / 4^k1 = 1/6.
2. Принципиальной разницы нет. Трудности могут возникнуть при вычислении. Если случайная величина абсолютно непрерывна, то есть имеет плотность распределения, то задача сведется к вычислению 10-ти мерного интеграла по области {(x1, x2, ..., x10) | x1 < x2 < ... < x10}.
Для понимания рассмотрим что это за область при n=2, то есть {(x1, x2) | x1 < x2}. Это те точки, которые лежат выше прямой x1=x2.
Здравствуйте, vadimcher, Вы писали:
V>Во как! Ну-ка придумай мне распределение такое, что вероятность того, что три НЕЗАВИСИМЫЕ случайные величины с этим распределением идут в возрастающем порядке, равна, например, 1/3. Про независимость только не забудь.
Пусть величина принимает значения {0, 1, 2} соответственно с вероятностями p1, p2, p3.
Последовательность из трех испытаний будет строго возрастать, только в одном случае (0,1,2).
Вероятность этого p1*p2*p3, и должно выполняться условие p1+p2+p3=1.
Например, 8/10 * 1/10 * 1/10 = 8/1000;
1/2 * 1/4 * 1/4 = 1/32;
2/3 * 1/6 * 1/6 = 1/54 и т.д.
D>>А у вас то же самое происходит с мощностями [-N;5] и [5;N]. И что?
F>В этом случае отношение между мощностями множеств стремится к 1. Поэтому скачок на бесконечности незаметен. Но это не значит, что его нет.
Хорошо. [-N;N/2] и [N/2;N]. 3:1 в пределе прыгает к бесконечности.
D>>PS Я в этой ветке пока не вижу рассуждений, которые бы дали 1/2 в выражении (1/2)^9. Более строгих, чем "У прямой два конца, нам мил один, ergo 1/2".
F>А я в ветке не увидел как при комбинаторном решении отработали ситуацию неполучения числа / невозможности сравнения.
При неполучении числа / невозможности сравнения задача не имеет смысла. Случайное целое вовсе не обязательно равномерно распределено (точнее обязательно неравномерно ); это просто программисты привыкли к таким генераторам. В задаче, кстати, про равномерность ничего не сказано.
Вот, например, генератор случайного целого, для которого бесконечное зацикливание теоретически возможно, но имеет нулевую вероятность
getRandom :: IO Integer
getRandom = do
n <- randomRIO(-10, 10) -- случайное целое из [-10,10]if (n == 0)
then return n
else do
m <- getRandom
let k = m + n
return k
Здравствуйте, deniok, Вы писали:
F>>В этом случае отношение между мощностями множеств стремится к 1. Поэтому скачок на бесконечности незаметен. Но это не значит, что его нет.
D>Хорошо. [-N;N/2] и [N/2;N]. 3:1 в пределе прыгает к бесконечности.
Как такое отношение прыгает к бесконечности? Наверное, ты имел ввиду разницу? Но это несколько не то.
D>При неполучении числа / невозможности сравнения задача не имеет смысла.
Почему?
D>Случайное целое вовсе не обязательно равномерно распределено (точнее обязательно неравномерно ); это просто программисты привыкли к таким генераторам. В задаче, кстати, про равномерность ничего не сказано.
Да, мы договорились до того, что в тройке "равномерное распределение на бесконечности" одно из слов лишнее, по крайней мере в каконическом определении распределения. Однако, нечто, обладающее похожими на распределение свойствами будет получаться в пределе — и это будет наиболее неудобным случаем с точки зрения теории игр — минимакса.
D>Вот, например, генератор случайного целого, для которого бесконечное зацикливание теоретически возможно, но имеет нулевую вероятность
...
Тут у тебя управляемое зацикливание с известными свойствами. А вот что ты будешь делать в случае привязки ГСЧ к более сложному случаю — например, останову абстрактной машины Тьюринга, для которой ты не сможешь так легко получить асимптоту вида (1/K)^n?
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, deniok, Вы писали:
F>>>В этом случае отношение между мощностями множеств стремится к 1. Поэтому скачок на бесконечности незаметен. Но это не значит, что его нет.
D>>Хорошо. [-N;N/2] и [N/2;N]. 3:1 в пределе прыгает к бесконечности.
Когда N -> \inf, то первый интервал стремится ко всей числовой оси (-\inf;+\inf), а второй вырождается в пустое множество — ни одно число в него не входит.
F>Как такое отношение прыгает к бесконечности? Наверное, ты имел ввиду разницу? Но это несколько не то.
D>>При неполучении числа / невозможности сравнения задача не имеет смысла.
F>Почему?
По условию задачи "устройство с кнопкой, которое при нажатии на кнопку выдает ... целое"
D>>Случайное целое вовсе не обязательно равномерно распределено (точнее обязательно неравномерно ); это просто программисты привыкли к таким генераторам. В задаче, кстати, про равномерность ничего не сказано.
F>Да, мы договорились до того, что в тройке "равномерное распределение на бесконечности" одно из слов лишнее, по крайней мере в каконическом определении распределения. Однако, нечто, обладающее похожими на распределение свойствами будет получаться в пределе — и это будет наиболее неудобным случаем с точки зрения теории игр — минимакса.
Какое всё это имеет отношение к задаче-то? Ваш генератор, если уж говорить про реализацию, никогда ничего не выдаст, поскольку вероятность получить число с количеством десятичных знаков меньше любого наперёд заданного числа — строго равна нулю. Грубо моделируя, вы предельным переходом загоняете половину плотности распределения на -\inf, а половину — на +\inf и пытаетесь сказать, что типа это чем-то лучше, чем загнать треть на -\inf, и две трети — на +\inf. И то и другое далеко отстоит по свойствам от исходного равномерного на отрезке, демонстрируя крайнюю степень неравномерности.
D>>Вот, например, генератор случайного целого, для которого бесконечное зацикливание теоретически возможно, но имеет нулевую вероятность F>...
F>Тут у тебя управляемое зацикливание с известными свойствами. А вот что ты будешь делать в случае привязки ГСЧ к более сложному случаю — например, останову абстрактной машины Тьюринга, для которой ты не сможешь так легко получить асимптоту вида (1/K)^n?
Я? Я ничего не буду делать. В первую очередь я не буду использовать такой генератор, поскольку он не выполняет своей главной задачи — генерировать.
Здравствуйте, vitasR, Вы писали:
R>Здравствуйте, vadimcher, Вы писали:
V>>Вот давай ты сначала на этот вопрос ответишь. Проблема не в этом. Проблема в том, что понятие вероятности само по себе отпадет. Используя подобные не-до-функции-распределения ты сможешь строить эксперименты, в которых сможешь вывести любую вероятность одного и того же события. Давайте посчитаем так, получим одно, посчитаем по-другому -- другой ответ. Так что давай ты сначала этот вопрос самостоятельно изучишь, а потом будешь строить собственные неколмогоровские теории, и уж тем более отвергать верные ответы этими теориями.
R>т.е. Вы признаете, что Ваше док-во некорректно для данной задачи (свой вариант ф-ции распределения, удовлетворяющей условиям задачи Вы не предложнили) R>каких-либо возражений против решения с 2^-9 не выдвинули. ну собственно что и требовалось доказать.
Для какой для данной? Мое самое первое решение здесь
покрывает общий случай, когда числа, выдаваемые генератором, независимые. Более того, я там сразу описал "плохие" случаи, когда ответ зависит от неизвестного распределения, а именно, если оно не является непрерывным, т.е. имеет особые точки с вероятностью >0. Я это сразу оговорил: в этом случае ответ зависит от неизвестного распределения, чем больше вероятность совпадений, тем дальше ответ от 1/10!. Если же неизвестное распределение непрерывное, результаты независимые, то ответ 1/10! от распределения не зависит. Здесь же уже предпринимаются последние попытки подогнать задачу под какие-то ответы. Проблема в том, что если не известно, что испытания независимые, то и ответа никакого нет, он зависит от устройства ГСЧ, однако независимость сама по себе дает уже ответ 1/10! (по крайней мере для непрерывных распределений). А вот пример распределения с ответом 1/2^9 я пока не видел. Только не надо опять про равномерное на бесконечности. Для него я могу вывести ответ 1/2^9, 1/10! или какой угодно еще, по желанию.
Здравствуйте, vadimcher, Вы писали:
V>Более того, я там сразу описал "плохие" случаи, когда ответ зависит от неизвестного распределения, а именно, если оно не является непрерывным, т.е. имеет особые точки с вероятностью >0.
Ты рассматривал вариант, в котором вероятность отдельного числа строго 0, отдельной выборки строго 0, а не б.м.?
Здравствуйте, deniok, Вы писали:
F>>>>В этом случае отношение между мощностями множеств стремится к 1. Поэтому скачок на бесконечности незаметен. Но это не значит, что его нет. D>>>Хорошо. [-N;N/2] и [N/2;N]. 3:1 в пределе прыгает к бесконечности. D>Когда N -> \inf, то первый интервал стремится ко всей числовой оси (-\inf;+\inf), а второй вырождается в пустое множество — ни одно число в него не входит.
Да. Сорри, я не сразу обратил на это внимание. Только это тоже подтверждает моё утверждение, что нельзя брать произвольное соотношение между сторонами
D>>>При неполучении числа / невозможности сравнения задача не имеет смысла. F>>Почему? D>По условию задачи "устройство с кнопкой, которое при нажатии на кнопку выдает ... целое"
Я условие задачи воспринял так, что результат работы устройства принадлежит неограниченному счётному множеству. А вот факт наступления события — получение конкретного числа — не очевиден. Более того, оппоненты с заявлением о невозможности равнвероятности таких чисел только это подтверждают.
D>>>Случайное целое вовсе не обязательно равномерно распределено (точнее обязательно неравномерно ); это просто программисты привыкли к таким генераторам. В задаче, кстати, про равномерность ничего не сказано.
F>>Да, мы договорились до того, что в тройке "равномерное распределение на бесконечности" одно из слов лишнее, по крайней мере в каконическом определении распределения. Однако, нечто, обладающее похожими на распределение свойствами будет получаться в пределе — и это будет наиболее неудобным случаем с точки зрения теории игр — минимакса.
D>Какое всё это имеет отношение к задаче-то? Ваш генератор, если уж говорить про реализацию, никогда ничего не выдаст, поскольку вероятность получить число с количеством десятичных знаков меньше любого наперёд заданного числа — строго равна нулю. Грубо моделируя, вы предельным переходом загоняете половину плотности распределения на -\inf, а половину — на +\inf и пытаетесь сказать, что типа это чем-то лучше, чем загнать треть на -\inf, и две трети — на +\inf. И то и другое далеко отстоит по свойствам от исходного равномерного на отрезке, демонстрируя крайнюю степень неравномерности.
Отношение к задаче простое — это предельный случай не полностью определённой исходной задачи.
D>>>Вот, например, генератор случайного целого, для которого бесконечное зацикливание теоретически возможно, но имеет нулевую вероятность F>>...
F>>Тут у тебя управляемое зацикливание с известными свойствами. А вот что ты будешь делать в случае привязки ГСЧ к более сложному случаю — например, останову абстрактной машины Тьюринга, для которой ты не сможешь так легко получить асимптоту вида (1/K)^n?
D>Я? Я ничего не буду делать. В первую очередь я не буду использовать такой генератор, поскольку он не выполняет своей главной задачи — генерировать.
Это академическая задача, у неё не обязательно должно быть практическое применение в виде работающего генератора. Хотя какая-то польза от неё есть и в таком виде — я уже приводил тут пример игры в условиях неопределённости внешних условий.
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, deniok, Вы писали:
D>Здравствуйте, batu, Вы писали:
B>>Надо брать диапазон -N;N тогда все станет на свои места.
D>То есть ты подгоняешь задачу под ответ? Ну-ну.
С Новым годом! Горячился.. Было такое. Не подгонял, а на своем мнении зациклился..
Здравствуйте, Аноним, Вы писали:
А>1. Допустим есть некое абстрактное устройство с кнопкой, которое при нажатии на кнопку выдает случайное целое (integer) число от -бесконечности до +бесконечности А>кнопку нажимают 10 раз — какова вероятность что все числа в возрастающем порядке ?
А>2. А если заменить в условии целые числа на вещественные (real) ?
Пните, пожалуйста, кто следил за обсуждением, если это решение уже было — ветка уж очень большая...
В задаче рвспределения нет и попытка оттолкнуться от него приводит в тупики типа "равномерное распределение на целых числах".
Предположим что все 10 чисел получились разные. (совпадения опять требуют возни с распределением... или нет?)
Устройство с кнопкой пусть генерит числа независимо от предыдущего р-тата. Опять же, в условии этого нет, но если есть неизвестная зависимость, то любое решение не учитывающее её неверно, то есть задача некорректна.
Учитывая это все, пронумеруем числа по возрастанию и переформулируем задачу: "Есть последовательность чисел 1,2,..10 в произвольном порядке. Какова вероятность что числа идут по возрастанию."
В общем у меня такое чувство, что в силу недоопределенности задачи мы доказали что 2^9 = 10!
