Время возвращения в начало координат

manggol

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

k11122nu

распределение расстояние между концами цепи N случайных блужданий описывается гауссом по R, формула известна. R = 0. Остается что-то навроде
3/(2πN)
, и это надо проинтегрировать по N. Правда, при таком подходе не ясно, как учитывать короткие цепочки (которые, очевидно, дают довольно большой вклад в общую вероятность).

k11122nu

хотя, собственно, что-то тут не то. Интеграл получается бесконечным. Похоже, с интегрированием по N я погорячился.

k11122nu

Ага, нужно просуммировать вероятности того, что на n, n+1 и так далее шагах цепочка не вернется назад.

Hana7725

А известно, что эта величина конечна, а то, мб и оценивать нечего?

manggol

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

k11122nu

ну надо вспомнить, чему равно
1 - (1-3/2π)*(1-3/4π)*(1-3/6π)*...*(1-3/2πn)*...

k11122nu

Mathematica пишет, что это
1 - Γ(1 - 3/2π) / e = 0.906

railok

может бесконечность?
в одномерном случае это так ...

k11122nu

прошу прощения, опять слажал. Забыл скобку в математике поставить. Формула та же самая, ответ
0.375411

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

manggol

Mathematica пишет, что это
1 - Γ(1 - 3/2π) / e = 0.906
то есть в среднем требуется меньше одного шага, чтобы из нуля, блуждая по дискретной решетке, вернуться в ноль. поздравляю.

manggol

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

k11122nu

А, блин, "матожидание времени возвращения", а не "вероятность возвращения". Слажал третий раз. Ну и фигли, вероятность для N я написал, что мешает посчитать? Тогда, конечно, бесконечность, Легат прав.

manggol

может бесконечность?
фигово. я просто на компе эксперимент провожу, там не двумерное случайное в чистом виде, но что то вроде того. уже для ста миллионов шагов проверил, казалось уже вот вот вернется сцуко, но в ноль таки на заходит :grin:

manggol

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

railok

А чем плоха бесконечность?

griz_a

Время возвращения даже в одномерном случае в среднем бесконечность для симметричного, не знаю о чем вы тут разговариваете :)

manggol

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

k11122nu

Думаю, надо пояснить.
За время N цепь покроет площадь N, а расстояние между концами будет [math]$D = \sqrt{N}$[/math]. В одномерии площадь N имеет диаметр [math]$N \gg D$[/math], в двумерии - диаметр [math]$N^{1/2} \approx D$[/math], в трехмерии - [math]$N^{1/3} \ll D$[/math]. Поэтому 100% одномерных цепей вернутся за бесконечное время в начальную и любую другую точку. Для плоскости покрыт окажется лишь определенный процент, и нет никакой гарантии, что заданная нулевая точка будет покрыта цепью (начиная с первого шага). Для трехмерного блуждания 100% точек окажутся не затронутыми цепью.
Поэтому если в одномерии можно ждать, и за бесконечное время любая цепь вернется назад, то для двумерной задачи лучше запустить много разных цепей, а для трехмерной вообще ждать не стоит: если в ближайшие шаги цепь не вернулась, она уже никогда не вернется.

griz_a

А что вы тогда обсуждаете? Ясно, что если двумерное вернется, то и его проекция вернется в 0, а она есть одномерное блуждание. Поэтому матожидание возвращения в 0 двумерного бесконечность

griz_a

Если тебе интересно в среднем - то никогда не дождешься. Попробуй воспользоваться другими характеристиками возвращения

k11122nu

я подумаю над этим. Пошел на прак.
Пока, если не сложно, объясни, где у меня ошибка. Если площадь, покрываемая цепью на плоскости, пропорциональна площади с радиусом, равном расстоянию между концами, то за счет чего заполняются пробелы?

griz_a

Для плоскости покрыт окажется лишь определенный процент, и нет никакой гарантии, что заданная нулевая точка будет покрыта цепью (начиная с первого шага).

У тебя какие-то странные рассуждения %)
Правильное рассуждение такое - вероятность вернуться на n-ом шаге порядка [math]$1/\sqrt n$[/math] в одномерном и 1/n в двумерном, [math]$(1/n)^{3/2}$[/math] в трехмерном и т.д. Если ряд расходится, то возвращается с вероятностью 1, если сходится, то нет.
А твоё какое-то непонятное абсолютно С чего ты взял, что с диаметром [math]$\sqrt n$[/math] нельзя покрыть всю плоскость? Ну пойду я по спирали, как раз такой диаметр и будет, а плоскость покроет :confused:

Martika1

Правильное рассуждение такое - вероятность вернуться на n-ом шаге порядка в одномерном и 1/n в двумерном, в трехмерном и т.д. Если ряд расходится, то возвращается с вероятностью 1, если сходится, то нет.
Я с этого и начал. У меня получилось, что ряд сходится и дает около 40% для вероятности вернуться за бесконечное число шагов (тут я доверился программе Математика). Использовав именно ту самую формулу "вероятность вернуться на n-ом шаге порядка 1/n". Посмотри, в начале треда я именно это и писал. Про покрытие плоскостью - это была лишь иллюстрация.

manggol

Если тебе интересно в среднем - то никогда не дождешься.
дождался таки!
Вернулась точно в ноль примерно на 150 миллионном шаге

manggol

просто обидно было, она после 30 миллионов очень близко прошла - на расстоянии 89. почти уже :cn: собака женского рода поймалась, и снова убежала)

iri3955

Я с этого и начал. У меня получилось, что ряд сходится и дает около 40% для вероятности вернуться за бесконечное число шагов (тут я доверился программе Математика). Использовав именно ту самую формулу "вероятность вернуться на n-ом шаге порядка 1/n". Посмотри, в начале треда я именно это и писал. Про покрытие плоскостью - это была лишь иллюстрация.
Ну, 5/2n тоже порядка 1/n, а даёт около 100%... А 3/n - больше 100... Парадокс.

griz_a

У тебя сходится гармонический ряд что ли? :confused:
Если ряд из вероятностей вернуться на n-ом шаге расходится, то вернется, гармонический ряд расходится, значит возвращается.
Вероятность невозвращения появляется только если ряд сходится.
Потому что вероятность того, что возвращение произойдет равна (-1+сумма ряда)/(сумма ряда)
Оставить комментарий
Имя или ник:
Комментарий: