плоность распределения в не очень школьной задачке...

и задачки для интервью.
User avatar
Galileo
Уже с Приветом
Posts: 2878
Joined: 29 Nov 2007 19:06

плоность распределения в не очень школьной задачке...

Post by Galileo »

Может, кому-то интересно порассуждать... В моём училище мы это не проходили, а вот что-то призадумался, интересно знать...


Задача такая: одномерное пространство. Координатная прямая. В нуле стоит человек. Вероятноcть, что он шагнёт вперёд равна вероятности, что он шагнёт назад и равна .5. Шаг равен единице.
Вопрос: какова вероятность, что за n шагов он отойдёт от нуля на расстояние большее, чем s, хотя бы один раз? (в сходных задачах формула полной вероятности иногда помогает - для каждого участка выписывается в бесконечный столбец, потом всё складывается и большая часть сокращаетя, но у меня не получается её применить).


Для двухмерного пространства - такой же вопрос. Следует уточнить, что человек стоит в (0,0). Шаг его - либо (0,1) либо (0,-1) либо (-1,0) либо (1,0) (по диагонали нельзя ходить). Шаги в разные стороны в любом месте равновероятны - по -.25. Какова вероятность, что человек выйдет за n шагов хотя бы раз за квадрат с четырьмя вершинами (-s,-s), (s, -s), (s,s), (-s,s)?

Для трёхмерного - можно в 6 сторон ходить. Какова вероятность, что выйдет хотя бы раз за куб с шестью вершинами (± s, ±s,±s).

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


Для одномерного случая также интересно было бы узнать, когда шаги в разные стороны не равновероятны, а зависят от расстояния до нуля, а именно:
на расстояии единица тянет к нулю с вероятностью 0.75 - на расстоянии 1, 0.875 - на расстоянии 2, 0.9375- на расстоянии 3,
(1-0.5^(k+1)) на расстоянии к.

Не для дипломных, а просто интересуюсь.

Интересен ли кому-нибудь будет этот раздел?
Где два беларуса, там три политические партии. (Народная мудрость.)
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Re: плоность распределения в не очень школьной задачке...

Post by Ворона »

Ну раз за целый день никто не подсказал, то я позволю себе:
http://en.wikipedia.org/wiki/Random_walk
Правда, там примерчик с равными вероятностями.
Вот еще книжка, но не знаю, получится ли ссылку скопировать: http://books.google.com/books?id=F004AA ... t&resnum=5
(книжка Introduction to Probability and Statistics from a Bayesian Viewpoint, Part 1 , страница 104, задача 33 -хотя это не ответ на Ваш вопрос, но просто про разные вероятности шагания вправо-влево и стояния на месте).
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: плоность распределения в не очень школьной задачке...

Post by venco »

Ворона wrote:Ну раз за целый день никто не подсказал, то я позволю себе:
http://en.wikipedia.org/wiki/Random_walk
Правда, там примерчик с равными вероятностями.

Что-то я там не нашёл решения этой задачи даже для равных вероятностей.
Там просто вероятность оказаться в какой-либо точке на определённом шаге. И можно посчитать вероятность нахождения за границей в некое время.
Но здесь спрашивается о вероятности оказаться за границей не просто в определённое время, а хотя бы раз за всё предшедствующее время.
CAIIIKA
Уже с Приветом
Posts: 1753
Joined: 23 Apr 2005 16:54

Re: плоность распределения в не очень школьной задачке...

Post by CAIIIKA »

Если надо не точную вероятность, а верхний предел, то неравенство Чебышева (Chebyshev's inequality) дает его для конкретного числа шагов i=n (написать как?), а чтобы посчитать то же, но хотя бы за один раз из i=1,...n шагов, то можно просто сложить все пределы из первой части для i=1,...n (union bound).
ksi
Уже с Приветом
Posts: 10086
Joined: 20 May 1999 09:01

Re: плоность распределения в не очень школьной задачке...

Post by ksi »

Galileo wrote:Может, кому-то интересно порассуждать... В моём училище мы это не проходили, а вот что-то призадумался, интересно знать...
Интересен ли кому-нибудь будет этот раздел?


Это все нетривиально. Классическая книжка William Feller, An Introduction to Probability Theory and its Applications (Volume 1,2). Точные формулы обычно или не выписываются или бесполезны. Поэтому обычно интресуются асимптотикой при больших s, n, которая напрямую связана с поведением броуновского движения (дискретное случайное блуждание при соответствующей центрирование и нормировке сводится к броуновскому движению) и эта асимптотика находится. Если вероятности прыжков зависят от положения, то дискретный процесс сходится к некоторому диффузионному процессу и там уже все зависит насколько этот диффузионный процесс может быть аналитически исследован на асимптотическое поведение.
STS
Уже с Приветом
Posts: 508
Joined: 20 May 2004 08:05

Re: плоность распределения в не очень школьной задачке...

Post by STS »

for one-dimensional case google "exotic options formulas" (financial applications). there is an exact algebraic/calculus solution for one-dimensional case. something like "down and out" option or "barrier options" -- i forgot the exact name.

Return to “Головоломки”