Случайное блуждание - матожидание

[artempalkin]

Задача: В начале я имею число $0$. Я бросаю монетку, и если выпадает орел, вычитаю единицу из числа, если выпадает решка, то прибавляю к нему единицу. Сколько в среднем бросков мне потребуется, чтобы мое число по модулю стало равно $n$ (некоторый натуральный параметр)?

Моделирование показывает, что $\mu(n)=n^2$, то есть ответ достаточно красивый. Однако получить его что-то не получается... Если, допустим, за $N_m$ принять количество "путей", чтобы за $m$ шагов впервые мое число стало равно $n$, то можно построить разные рекурсивные формулы, но что-то ничего очень хорошего из них не следует...

Возможно, есть какой-то более простой способ подойти к этой задаче?

[iifat]

Ну, вот, например. Как бы это так ненавязчиво причинить вам информацию: вторая ссылка в Яндексе по запросу «случайное блуждание на прямой». Не читал внимательно, есть ли там ответ на ваш вопрос, но вроде как должен быть.

[мат-ламер]

iifat в сообщении #1635930 писал(а):

случайное блуждание на прямой»

Иногда в учебниках такого рода задачи именуются задачами о разорении.

artempalkin в сообщении #1635918 писал(а):

можно построить разные рекурсивные формулы

Нормальный подход.

[Alex Krylov]

Попробуйте использовать характеристическую функцию

Если $X_i, i=1,2...,N$ - независимые, одинаково распределенные случайные величины и $\varphi(t)$ - характеристическая функция этих случайных величин, то характеристическая функция суммы $\sum\limits_{i=1}^{N}X_i$ есть $\varphi(t)^N$. А дальше обратное преобразование Фурье. На самом деле там будет чистая тригонометрия.

[vicvolf]

artempalkin в сообщении #1635918 писал(а):

Задача: В начале я имею число $0$. Я бросаю монетку, и если выпадает орел, вычитаю единицу из числа, если выпадает решка, то прибавляю к нему единицу. Сколько в среднем бросков мне потребуется, чтобы мое число по модулю стало равно $n$ (некоторый натуральный параметр)?

Это известная задача о средней длительности случайного блуждания или задача о разорении игрока https://ru.wikipedia.org/wiki/%D0%97%D0 ... 0%BA%D0%B0
При одинаковых стартовых капиталах -$n$ для разорения одного из игроков потребуется $n^2$ шагов. Так что моделирование Вас не подвело. Однако обозначение $\mu(n)$ выбрано крайне неудачное, так как это обозначение арифметической функции Мебиуса.

[Alex Krylov]

Прошу прощения, невнимательно прочитал условие и выше второпях ответил невпопад...

Два возможных варианта решения:
1) на основе аппарата цепей Маркова
https://upcommons.upc.edu/bitstream/handle/2117/370283/2-Markov%20chains%20Absorbing%20Markov%20chains.pdf?sequence=1&isAllowed=y

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

2) на основе рассмотрения собственно случайных блужданий (с поглощающими экранами) + так называемые первое и второе тождества Вальда и условие номировки (сумма вероятностей равна 1)
https://people.math.wisc.edu/~roch/grad-prob/gradprob-notes12.pdf
https://web.ma.utexas.edu/users/gordanz/notes/advanced_random_walks_color.pdf

Самый быстрый и элегантный вариант - это через 1-е/2-е тождества Вальда и условие нормировки