Задачка про двух математиков на марковские процессы

Автор темы mozzie1 (mozzie) 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий и рекламы в форуме26.03.2008 03:07
ОбъявлениеРекомендации по использованию теха в нашем форуме15.04.2017 21:40
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
22.02.2007 21:57
Задачка про двух математиков на марковские процессы
Итак, имеется 2 математика, которые в честь дня Пифагора перебрали пива и по этой причине нетвёрдо стоят на ногах. Так как все математики неповторимы, эти двое тоже непохожи друг на друга. Про первого математика можно сказать, что неизвестно, куда он сделает следующий шаг - вперёд или назад. Второй математик, сделав шаг вперёд, скорее всего и следующий шаг сделает вперёд. Так же, если он сделает шаг назад, то скорее всего и следующий шаг он сделает назад.

Вопрос : какой математик быстрее доберётся, скажем, до общежития?

p.s. задача на марковские цепи, скажем так, ну или на марковские процессы.

p.s.s. любопытства ради.



встану утром рано...
23.02.2007 13:18
пьян был автор задачи
ответ 12.

НЕ поленитесь доформулировать условия.

Фразы типа "неизвестно, куда он сделает следующий шаг "
"скорее всего и следующий шаг " - говорят в пользу того что составитель задачи был пъян.
24.02.2007 12:50
пьян или трезв - тайна, покрытая мраком
по поводу вопроса, если уж один студент сделал шаг в одном направлении, то и все последующие шаги он точно сделает в том-же направлении. Второй студент первый шаг также делает в одном из двух направлений, но и следующий шаг так-же случайно, и все следующие шаги. вот в чем их разница.



встану утром рано...
24.02.2007 15:16
точность
случайно это не понятный термин.


Доопределите его.

Случайно равновероятно.
Случайно по распределению х, образом не зависимым от истории.
Случайно по распределению х зависимо от истории

и т.п и.т.д
24.02.2007 18:22
Как я понял задачу
Возьмём независимые $\xi_i$, принимающие $\pm 1$ с вероятностью 1/2, и зависимые $\eta_i: \eta_1 \sim \xi_1, P(\eta_i = \eta_{i-1}) = 1 \; \forall i > 1$.
Тогда позиция первого математика в t-й момент времени равна $\xi_0 + ... + \xi_t$, второго - $\eta_0 + ... + \eta_t$.
Вопрос - что такое "доберется быстрее"? Даже в самом простом случае, когда общежитие находится в одном шаге от старта, первый до него не дойдёт с вероятностью 1/3 (можно посчитать), второй - с вероятностью 1/2 (поскольку это зависит от того, куда он сделает первый шаг).
Поэтому матожидание времени достижения цели в обоих случаях, вообще-то, бесконечно.

EDIT: С 1/3 я ошибся, сорри. Сейчас попробую исправить.

[MM/IUM]



Редактировалось 1 раз(а). Последний 01.03.2008 18:16.
24.02.2007 18:57
извиняюсь за нестрогость =)
самое подходящее - случайно равновероятно, я не могу сказать, что тут такое х, размер шага или вес мобильника в кармане одного из студентов и т.п. Т.е. это не важно.

p.s. лично я не знаю как решать, мне кажется, что дойдет быстрее тот, кто идет все время в одну сторону... а как количественно оценить это - не знаю.



встану утром рано...
24.02.2007 18:58
откуда
откуда вы поняли про 1\2 с бороды?
24.02.2007 19:01
может быть
я так понимаю, что тут надо считать что земля круглая.

вобщем, имхо, эта задача кажется, пересекается с этим вопросом вопросом

т.е. если выпадает достаточно длинная серия орлов, значит тот, кто на каждом шаге с вероятностью 1/2 может повернуться обратно имеет больше шансов добраться до общаги.



встану утром рано...
24.02.2007 22:46
ответ
Оговорюсь сразу, что я считал здесь землю одномерной и бесконечной в обе стороны (т.е. действие происходит на прямой)

Возьмите события $A = \{\eta_1 = 1\}$ и $B = \{\eta_1 = -1\}$
$P(A) = P(B) = 1/2$, потому что так предположили.(первый шаг делается случайно равновероятно)
Также предположили, что $P(\eta_i = \eta_{i-1}) = 1$. Поэтому A, быть может, с точностью до множества вероятности 0, совпадает с множеством $\{\eta_i = 1 \; \forall i >= 1\}$. То же самое с B.
Получаем разбиение нашего вероятностного пространства на два множества меры по 1/2, на одном из которых все конечные суммы $\eta_1 + ... + \eta_t$ отрицательны (равны -t), а на втором положительны и равны t.
Теперь заметьте, что математик добирается до общаги во втором случае и только в нём.

Это понятно или написать формальнее?

[MM/IUM]



Редактировалось 2 раз(а). Последний 01.03.2008 18:19.
25.02.2007 23:32
решение не верное и не понятное
Вопрос был кто быстрей добереться до общаги:?


Для обоих математиков мат.ожидание времени до прихода в общагу равно бесконечности. Отсюда и ответ.


А ваше решение вы уж извините чистой воды прованация не слова не понял. Термины понасунуты а смысл?
04.03.2007 00:21
про смысл
Смысл в том, что событие A = { второй математик доберется до общаги } совпадает с событием B = { второй математик сделает в сторону общаги первый шаг } с точностью до события нулевой вероятности.
P(B) = 1/2, а в предыдущем посте всё это просто более формально доказано.
Если хотите это утверждение оспорить -- валяйте.:)



[MM/IUM]
04.03.2007 11:27
Да чего тут думать?! Надо проводить натурный эксперимент!!!
Да чего тут думать?! Надо проводить натурный эксперимент!!! Но для частоты эксперимента, его необходимо провести строго в день Пифагора!...:) Господа математики, среди Вас есть желающие пожертвовать немного своего здоровья во имя Науки!?

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

Вот видите как все просто. А Вы говорите Марковские процессы...;-)

08.02.2008 20:04
вот еще нашел про данную задачку
Пусть подвыпивший матрос вышел поздно вечером из кабачка и направился вдоль улицы. Пройдя путь l до ближайшего фонаря, он отдохнул и пошел... либо дальше, до следующего фонаря, либо назад, к кабачку – ведь он не помнит, откуда пришел. Спрашивается, уйдет он когда-нибудь от кабачка, или так и будет бродить около него, то отдаляясь, то приближаясь к нему? (В другом варианте задачи говорится, что на обоих концах улицы, где кончаются фонари, находятся грязные канавы, и спрашивается, удастся ли матросу не свалиться в одну из них). Интуитивно кажется, что правилен второй ответ. Но он неверен: оказывается, матрос будет постепенно все более удаляться от нулевой точки, хотя и намного медленнее, чем если бы он шел только в одну сторону. Вот как это можно доказать.

Пройдя первый раз до ближайшего фонаря (вправо или влево), матрос окажется на расстоянии s1 = ± l от исходной точки. Так как нас интересует только его удаление от этой точки, но не направление, избавимся от знаков, возведя это выражение в квадрат: s12 = l2. Спустя какое-то время, матрос, совершив уже N «блужданий», окажется на расстоянии

sN = от начала. А пройдя еще раз (в одну из сторон) до ближайшего фонаря, – на расстоянии sN+1 = sN ± l, или, используя квадрат смещения, s2N+1 = s2N ±2sN l + l2. Если матрос много раз повторит это перемещение (от N до N + 1), то в результате усреднения (он с равной вероятностью проходит N-ый шаг вправо или влево), член ±2sNl сократится, так что < s2N+1 = s2N + l2> (угловыми скобками обозначено усредненная величина).

Так как s12 = l2, то

s22 = s12 + l2 = 2l2, s32 = s22 + l2 = 3ll2 и т.д., т.е. s2N = Nl2 или sN =l. Общий пройденный путь L можно записать и как произведение скорости матроса на время в пути (L = ut), и как произведение числа блужданий на расстояние между фонарями (L = Nl), следовательно, ut = Nl, откуда N = ut/l и окончательно sN = . Таким образом получается зависимость смещения матроса (а также молекулы или броуновской частицы) от времени. Например, если между фонарями 10 м и матрос идет со скоростью 1 м/с, то за час его общий путь составит L = 3600 м = 3,6 км, тогда как смещение от нулевой точки за то же время будет равно всего s = = 190 м. За три часа он пройдет L = 10,8 км, а сместится на s = 330 м и т.д.



встану утром рано...
25.02.2008 22:19
источник
почитайте Феллера, вроде как первый том, там эта задача разобрана

при равномерном (вероятность 1/2 налево и столько же направо) случайном блуждании на прямой мат. ожидание положения точки в случайный момент времени есть начальный пункт блуждания.

далее, с вероятностью 1 случайное блуждание приходит в начало за конечное время (т.е. E(min(t)|X(t)=0)<inf), не помню за какое.

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

Кликните здесь, чтобы войти