Продолжаем тему разностных уравнений и случайных блужданий. Мы рассмотрели странствия пьяного матроса по палубе или мосту, которое описывается тем же уравнением, что и игра в орлянку. И получилось, что при равных шансах на шаг вперед/назад (влево/вправо, выиграть/проиграть) возврат (или прибытие) в нуль неизбежно, если блуждание в одном или двух измерениях.
Более того, переходов через нуль будет бесконечно много с вероятностью единица. Те случаи, когда нуль достигается конечное число раз за бесконечное число игр все вместе имеют нулевую вероятность.
Не так дело обстоит при асимметричном блуждании: если матрос шагает вперед чуть чаще, чем назад, а монета выпадает гербом чуть чаще, чем портретом короля. Возьмем этот случай. Пусть p --- вероятность проиграть Бену, а q=1-p --- вероятность выиграть, и они не равны. У Бена Ганна N монет, у его оппонента M монет. Игра идет до разорения одного из игроков. Вероятность Бену выиграть, имея n монет, обозначим P(n). Уравнение имеет вид
P(n) = pP(n-1) + qP(n+1).
Граничные условия к нему P(0)=0, P(N+M)=1. Обозначим N+M=T.
Как обычно, сначала решаем уравнение без граничных условий. Это линейное разностное уравнение второго порядка. Как мы уже обсуждали, пространство его решений двумерно: зная P(0) и P(1), мы можем определить все P(n). Значит, найдя два решения, мы получим все.
Однако здесь уже не так легко подобрать два решения. Одно, правда, напрашивается: это константа P(n)=1. Попробуем поискать решения в виде степени P(n) = x^n:
x^n = px^(n-1) + qx^(n+1) ~ qx^2 - x + p = 0.
Одно решение мы уже знаем, это x=1. Второе (L=p/q) дает теорема Виета, которая также гарантирует, что корни оба положительные. Кстати, дискриминант равен 1-4pq равен нулю только при p=q=0.5.
Этот факт заслуживает отдельного разговора --- про оптимизацию, энтропию и симметрию. В другой раз. Подписывайтесь --- будет интересно.
Поэтому корней всегда два и с решениями у нас порядок: одно константа, другое (p/q)^n, и все решения запишутся в виде комбинации
P(n) = A + B(p/q)^n
для каких-то констант A и B. Теперь вспомним про граничые условия. Применим первое, и получим A=-B и
P(n) = A( 1 - (p/q)^n ),
а второе дает A = 1 / (1-(p/q)^T).
Какое отличие от случая p=q? Самое заметное: при большом N (и потому T) вероятность выиграть стремилась к нулю, а теперь это не так, если p<q (то есть вероятность проиграть меньше вероятности выиграть):
P(1) = 1-p/q при N=1 и бесконечном M.
При p>q вероятность, конечно, стремится к нулю, если вычислить предел. Но можно непосредственно применить граничное условие в бесконечности и увидеть, что решений нет: вероятность равна нулю всегда, единицы достичь не может даже в бесконечности.