Комментарии 72
Кстати, к этой задаче есть ещё другой подход. Есть какое-то распределение вероятностей по шагам f(n, t), которое мы ищем, а так же краевое условие f(n, t) = 0. Можно сначала найти решение p(n, t) без краевых условий (как будто пропасти нет), а потом для учёта краевого условия сказать, что f(n, t) = p(n, t) - p(-n, t). Как будто за пропастью есть "анти-пьяница" с отрицательной вероятностью существования, и сложение вероятностей как раз даст 0 на границе пропасти.
Для больших t распределение вероятностей будет похожим на распределение Гаусса. (если не смотреть на приколы с чётностью шагов). Если вероятность шага право выше шага влево, то центр гауссианы со временем будет двигаться вправо (как раз на разность вероятности шагнуть влево и вправо.). Идея с "отражением" функции для учёта краевого случая будет работать и тут, так что результат точно так же будет суммой положительной и отрицательной Гауссиан.
Кстати, в жизни случается что-то похожее в гальванике - молекула металла случайно блуждает в электролите, но из-за электрического поля вероятность блуждания "в нужном направлении" будет выше, а при достижении поверхности молекула осядет на ней.
Ставь лайк, если после этого стал немного больше уважать пьяниц :)
При
получаем, что
то есть пьяница точно упадет с обрыва.
Таким образом, если вероятность
то пьяница точно упадет (другими словами, это достоверное событие).
Задача вероятностная. При
вероятность того, что ВСЕ шаги пьяницы будут в сторону от обрыва, пусть и мала, но тем не менее ненулевая. Вероятность того, что на любом шаге количество шагов "от" будет не менее количества шагов "до" - не просто ненулевая, а гораздо больше предыдущей, хотя и по-прежнему исчезающе мала. А потому достоверным это событие назвать ну никак нельзя.
Наполовину вы правы. Если ограничить количество шагов пьяницы, то, действительно, событие "пьяница упал с обрыва" не является достоверным (за исключением тривиального случая, когда
). Если же не ограничивать количество шагов, то событие "пьяница упал с обрыва" будет достоверным при
потому что при
множество элементарных событий состоит только из этого события.
Вероятность того, что ВСЕ шаги пьяницы будут сделаны в направлении ОТ обрыва, равна 
, где n - количество шагов. Верно? И хотя предел данного выражения при n стремящемся к бесконечности равен нулю, значение этого выражения тем не менее не ноль, а некое положительное, хотя и исчезающе малое, значение. Верно? То есть вероятность, что пьяница не упадёт потому, что будет все шаги делать в сторону от обрыва - ненулевая. Верно?
Или есть возражения? только, пожалуйста, не на бытовом уровне...
Мне самому в своё время с трудом далось понимание, что "если длина палки, измеренная портновским метром, равна 1 метру, то существует ненулевая вероятность, что длина палки 2 метра".
А можно чуть подробнее про палку, очень уж интересно ?
Вероятность любой отдельной реализации в бесконечном пространстве возможных событий (в том числе и вероятность бесконечного числа шагов направо) строго равна нулю.
И тему насчёт своего понимания случая с палкой поясните, пожалуйста. У методически правильно используемого портновского метра есть погрешность измерения, больше которой получиться не может.
Нет, вы неправильно обращаетесь с предельным переходом. Расширяя комментарий от @BigBeaver, представьте, что мы с вами заключаем пари - если пьяница упадёт за 
шагов, то вы мне платите 1 рубль, если пьяница не упадёт - я вам плачу 
рублей. При этом сначала вы выбираете число 
и говорите мне, а потом я выбираю число 
. При каком значении 
игра будет для вас выигрышна в среднем? Ни при каком: я всегда смогу предложить такое конечное значение 
(зависящее от 
), что пьяница не упадёт с вероятностью меньшей 
.
Именно это и понимается под утверждение "пьяница гаратнированно упадёт через бесконечное количество шагов" - это просто удобная фигура речи, позволяющая опускать несколько тяжеловесную формулировку предела на бесконечности.
Операция "подождать бесконечное число шагов" в реальном мире в общем-то неопределена - даже с Большого взрыва прошло конечное число секунд.
А потому достоверным это событие назвать ну никак нельзяВероятность достоверного события = 1, но обратное верно ли?
Например, вероятность случайного выбора любого (заранее заданного) числа на отрезке [0,1] равна нулю, но как только эксперимент проведён, какое-то число точно выпало, хотя вероятность его выпадения строго равна 0.
Вот мне тоже этот пример вспомнился. Если я ничего не путаю, в задаче про пьяницу тот же случай, когда вероятность падения строго равна единице, но достоверным событие не является.
Для любого конечного числа шагов оно и вероятность равную единице не имеет. А на бесконечном числе шагов вероятность равна единице, но событие является «почти достоверным», но не достоверным.
Так же как при выборе точки на отрезке вещественных чисел попадание в конкретное число имеет нулевую вероятность, называется «почти невозможным», но произойти всё-таки может.
называется «почти невозможным», но произойти всё-таки может.Ну так здесь идея в том, что на бесконечном луче нет понятия «все» (по крайне мере в бытовом смысле). То есть, как бы далеко он не уползал от обрыва, всегда остается вероятность упасть.
Потому здесь на самом деле намного интереснее выглядят исходы, когда вероятность меньше единицы. Я бы сказал, что существование шанса того, что можно вообще никогда не упасть интуитивно кажется странным.
Если «вероятность упасть» равна p1, то «вероятность не упасть» равна ли (1-p1)?
Вероятность упасть (вообще когда-либо) есть сумма вероятностей:
— вероятность упасть на 1-м шаге
— вероятность упасть на 2-м шаге
…
Вероятность не упасть есть произведение вероятностей:
— вероятность не упасть на 1-м шаге
— вероятность не упасть на 2-м шаге
…
Если суммировать ряды мы худо-бедно умеем, то как обстоят дела с бесконечными произведениями?
Вполне возможно, что доказуемы оба утверждения:
— вероятность упасть равна 0 < p1 < 1 (например, для любой точки в левой части графика статьи);
— вероятность не упасть равна 0.
при одном и том же начальном p.
Если суммировать ряды мы худо-бедно умеем, то как обстоят дела с бесконечными произведениями?
Точно так же - сходятся к пределу частичных произведений, как ряд к пределу частичных сумм. Ну или, если я правильно помню матан, сводятся к ряду через взятие логарифма.
Вполне возможно, что доказуемы оба утверждения:
— вероятность упасть равна 0 < p1 < 1 (например, для любой точки в левой части графика статьи);
— вероятность не упасть равна 0.
Проблема в том, что при бесконечном количестве шагов эти исходы исчерпывают всё пространство событий. А значит, сумма их вероятностей, какими бы они ни были, будет 1, чисто по определению.
Проблема в том, что при бесконечном количестве шагов эти исходы исчерпывают всё пространство событий. А значит, сумма их вероятностей, какими бы они ни были, будет 1, чисто по определению.Для бесконечных множеств такие предположения делать опасно. Тут и равенство количества чётных чисел количеству всех целых чисел, и парадокс Банаха-Тарского.
То есть, Вы утверждаете, что существует событие (бесконечная последовательность шагов), которое не относится к одному из этих двух исходов? Если нет - то бесконечность не играет никакой роли, у нас просто есть разбиение множества на две части. Худшее, что может случиться, - одна из этих частей может оказаться неизмеримой (и то, не помню с ходу, возможно ли, чтобы неизмеримой была ровно одна из них); но если обе измеримы, то сумма их мер (~вероятностей) будет равна мере всего множества (~единице, по определению вероятности).
Но как вы проверите?
У вас нет бесконечного времени, чтобы смоделировать исход шагов для любой бесконечной последовательности.
Можно как-то алгоритмически конструировать такие последовательности, и привязать их к каким-то недоказаным гипотезам. Например, мы не упадём, если количество простых чисел-близнецов бесконечно. Иначе упадём.
И тогда аналитически вы не предскажете исход, а моделирование потребует бесконечных ресурсов.
А можно ещё попробовать привязать к невычислимой функции. Как-никак, бесконечных последовательностей — континуум, а алгоритмов — счётное число. Значит, есть последовательность, которую нельзя задать алгоритмически. И как вы для неё посчитаете исход?
А вы утверждаете, что нет такого события?
Да, тривиальным образом: из двух исходов один реализуется, когда шаг, на котором происходит падение, существует, второй - когда этот шаг не существует. Вы, я так понимаю, различаете случаи "шаг доказуемо существует" и "шаг существует, но невычислим", и считаете, что во втором случае факт наличия падения не определён?
Я считаю, что между фактами "X существует" и "X не существует" отсутствует третья альтернатива, да. Каждый из них отдельно распадается на случаи "...и это доказуемо" и "...и это недоказуемо", но для факта существования это незначимо.
Это возвращаясь к утверждению «Вполне возможно, что доказуемы оба утверждения...» Не удивлюсь, если так и есть.
Теорема о неполноте гласит, что существуют утверждения, истинные, но недоказуемые. На факт наличия/отсутствия истинности она никак не влияет, он по-прежнему бинарен.
Вопрос в том, что нулевая вероятность на бесконечном пространстве событий не означает невозможности события.
Здесь все упирается как раз в то, как вы сделаете выбор? За конечное время можно описать только конечное количество чисел. По факту, нет возможности выбрать из бесконечного количества чисел
В какой-то момент я планирую сделать выбор, а в другой момент я уже выбрал.
Вы выбрали число, ок. Какое именно? Вам же нужно ответить на этот вопрос хотя бы для себя. Может вы назовете число, может, зададите через формулу, опишете его, но выбор должен описывать ваше число однозначно. На описание числа уходит время, а вот время, как раз, конечная величина, следовательно, вы можете описать число с конечной точностью. Множество чисел, которые вы можете описать за всю свою жизнь это очень большое, но конечное множество
А тот я, из идеального мира, мы про него запишем «выбрал число a, про которое мы ничего не знаем». А если по условиям задачи нужно как-то взаимодействовать с этим числом, все взаимодействия будут прописаны в условии. Пока нет никаких ограничений, нам достаточно знать, что это число a.
Разве не вы выше написали:
Например, вероятность случайного выбора любого (заранее заданного) числа на отрезке [0,1] равна нулю, но как только эксперимент проведён, какое-то число точно выпало, хотя вероятность его выпадения строго равна 0.
Вот я и прошу описать мне, как вы в эксперименте выберете и зададите число. Будете кидать кубик? Спрашивать прохожих? Писать числа от балды? Использовать генератор случайных чисел?
Да, чисел на этом отрезке бесконечное количество, но, в данном случае, идет речь только о числах, которые могут быть выбраны, а их конечное (хоть и очень большое) число. Ограничение накладывается не множеством, а необходимостью выбора
Вот и будет в задачке формулировка: пользователь хабра qw1 выбрал случайное число из отрезка [0;1]. А как он это сделал — это вне абстракции.
Кстати, к этой задаче есть ещё другой подход. Есть какое-то распределение вероятностей по шагам f(n, t), которое мы ищем, а так же краевое условие f(n, t) = 0. Можно сначала найти решение p(n, t) без краевых условий (как будто пропасти нет), а потом для учёта краевого условия сказать, что f(n, t) = p(n, t) - p(-n, t). Как будто за пропастью есть "анти-пьяница" с отрицательной вероятностью существования, и сложение вероятностей как раз даст 0 на границе пропасти.
Для больших t распределение вероятностей будет похожим на распределение Гаусса. (если не смотреть на приколы с чётностью шагов). Если вероятность шага право выше шага влево, то центр гауссианы со временем будет двигаться вправо (как раз на разность вероятности шагнуть влево и вправо.). Идея с "отражением" функции для учёта краевого случая будет работать и тут, так что результат точно так же будет суммой положительной и отрицательной Гауссиан.
Кстати, в жизни случается что-то похожее в гальванике - молекула металла случайно блуждает в электролите, но из-за электрического поля вероятность блуждания "в нужном направлении" будет выше, а при достижении поверхности молекула осядет на ней.
В непрерывном виде получится уравнение, аналогичное уравнению теплопроводности с граничными условиями 1 типа (Дирихле). Положим, что в точке х=0 отводится всё тепло (или уничтожаются все пьяницы), соответственно u(0, t) = 0. Такая задача действительно легко решается путём "помещения" пьяницы в точку х=1 и антипьяницы в точку х=-1 и свёртки с ядром Гаусса по всей вещественной оси.
Интересно, что подобным образом можно решить и граничную задачу 2 типа (Неймана), когда в точке х=0 находится непреодолимый барьер и, соответственно, поток равен нулю (∂u/∂x = 0 при х = 0). В этом случае мы "помещаем" "положительных" пьяниц в точки х=1 и х=-1 и аналогично вычисляем свёртку с ядром Гаусса.
В чем вы делали такие шикарные анимации?
...и на четырёх конечностях. С таким условием, даже если он "шагнёт" в пропасть - это не будет означать автоматического падения.
В марковских цепях есть тема: "Cлучайные блуждания на кубических решетках", в ней как раз и разбираются подобного рода задачи. Например, в книге "Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения. Кельберт М. Я., Сухов Ю. М." на 59 стр. разбирается эта тема.
В целом было интересно, особенно про связь с числами Каталана.
Тем не менее, есть два наблюдения.
Формулу для P1 можно упросить, поскольку под корнем полный квадрат (2p - 1)^2. Мне кажется приятнее видеть |2p - 1| в этой формуле.
Исходную задачу можно решить много проще, если выводить рекуррентное соотношение сразу для вероятности Pn. Оно имеет вид
(1) P(n) = p P(n-1) + (1-p) P(n+1)
Пространство решений уравнения (1) двумерно и при p отличном от 0.5 общее решение имеет вид P(n) = A (p / (1-p))^n + B. Для поиска базиса нужно просто искать решения вида n^a. При p=0.5 общее решение имеет вид A +B n.
Далее, из условий (P(0) = 1, P(n) <= 1) и непрерывности решения по p, находим, что
P(n) = (p / (1 - p))^n при p< 0.5 и
P(n) = 1 при p>= 0.5
Вообще, в задаче неслучайно указан пьяница, а не слепой инженер-математик, например. Вероятность того, что он навернется - либо да, либо нет.
(но вот за числа Каталана спасибо)
Не нашёл решения исходной задачи (на картинке)
при p = 1/3 => P1 = 0,5.
Все уже давно придумано до нас, и решается в общем случаи, https://en.wikipedia.org/wiki/Birth–death_process не надо велосипедов.
а чисто по логике, разве вероятность может быть ниже 1/3 ? У первого шага в сторону пропасти именно такая вероятность. Если первый шаг в другую сторону, то дальше эта вероятность стремится к нулю(если нет ограничения по рассчитываемому кол-ву шагов), но учитывая первый шаг - не может быть ниже 1/3
быть меньше 
Нет, не может, потому что верно следующее неравенство
Почему тут не применим тривиальный подход:
если движение ничем не ограничено, то рано или поздно появится такая последовательность шагов в сторону пропасти, которая всегда будет больше предыдущей последовательности, направленной от пропасти, таким образом шанс упасть 100%?
Или шанс упасть не 100%, и в утверждении выше - ошибка?
Ошибка заключается в том, что не всегда появится нужная последовательность шагов. Например, если пьяница делает один шаг в сторону от обрыва и один шаг в сторону обрыва, и повторяет эту последовательность бесконечно много раз, то нужная последовательность не появится.
Я правильно понимаю, что если в казино, где на игровых автоматах вероятность выигрыша настроена на 50%, то при долгой игре у игрока нет шансов? Слышал, что в Лас-Вегасе, законом установлено, что такая вероятность должна быть 70% в пользу игрока. Уж, не из вышеизложенных обстоятельств такое требование?
Скажем, если вероятность выигрыша 50%, ставка $1, выигрыш $1.1, то в половине случаев вы отдадите казино один доллар, а во второй половине оставите себе свой доллар и получите от казино 10 центов. На 1000 игр вы потратите $500, вернёте $50, то есть ваш убыток будет $450.
Публикации
Задача про пьяницу