Давайте сегодня рассмотрим задачу о разорении в простой безобидной игре вроде орлянки. Безобидной игрой называется игра с равными шансами для игроков.
Бен Ганн играет в орлянку на могильных плитах. Пусть у Бена одна монета, а его противника - тысяча монет. Каковы шансы Бена выиграть все деньги? А разориться самому? И каково среднее число партий до разорения одного из игроков?
Прямой подсчет всех возможных исходов до разорения - труден. Но можно использовать то свойство игры, что после одной партии это та же самая игра, только суммы денег у игроков изменились. Обозначим сумму у Бена через n, а среднее число партий до разорения одного из игроков - через N(n). Понятно, что после одной партии либо Бен выиграл, и теперь среднее равно N(n+1), либо проиграл, и тогда оно равно N(n-1). Получается уравнение
N(n) = 1 + 0.5N(n+1) + 0.5N(n-1).
К этому уравнению (если угодно - системе) прилагаются граничные условия:
N(0) = N(M+B) = 0.
Здесь M=1000 - начальный капитал противника Бена, а B=1 - начальный капитал самого Бена. Ведь если у Бена ничего не осталось - игра окончена, равно как если он все выиграл.
Это уравнение легко решается, но если знать некоторую теорию в основе. А именно - теорию линейных уравнеий. Это линейное неоднородное уравнение! И очень полезно немного воспарить над задачей, выкинув временно часть условий и забыв о физическом смысле.
Давайте отбросим граничные условия, а также единичку из уравнения:
2N(n) = N(n+1) + N(n-1).
Нам надо найти все решения этого вспомогательного уравнения - это будет первый шаг к победе.
Заметим, что уравнение линейное - если какая-то функция целочисленного аргумента N(n) подходит, то можно умножить ее на любое число, и это тоже будет решение. Например, N(n)=1 при всех n - удовлетворяет уравнению, а потому подходит и любая константа. Более того, если есть два разных решения, то и их сумма - тоже решение. Например, N(n)=n - решение, а значит, и n+1 подойдет. Это вроде как банально - но это очень мощное наблюдение. Ведь можно наделать много решений из пары найденных хоть подбором, хоть как.
Второе наблюдение такое. Независимых решений может быть только два. В самом деле, если нам даны N(0) и N(1), все остальное легко определяется. Степеней свободы ровно две.
То есть, наша частная задача сводится к отысканию двух независимых (непропорциональных) решений. Эти два решения легко подбираются, и мы их уже нашли: одно решение это константа, например N(n)=1, а второе N(n)=n.
Умножая на числа и складывая, мы получим не просто много решений, а вообще все - мы это строго доказали. Итак, все решения нашего вспомогательного уравнения записываются так:
N(n) = C + Sn
для произвольных чисел C и S.
Теперь вспомним об исходном уравнении:
N(n) = 1 + 0.5N(n+1) + 0.5N(n-1).
Пусть мы нашли одно решение этого уравнения, обозначим его X(n). Добавляя к нему решения вспомогательного, мы получим еще решения - ведь решение вспомогательного будет добавлять к единице нуль.
Таким образом, нам надо отыскать одно-единственное решение уравнения, и оно породит все без исключения решения - среди которых мы найдем то, которое удовлетворяет и граничным условиям.
Это решение X(n) = -n^2. Легко проверить. Тогда заветная формула такова:
N(n) = C + Sn - n^2.
Вспомним граничные условия: N(0)=0, откуда сразу C=0, и N(M+B)=0, откуда S=M+B. Мы решили уравнение:
N(n) = n(M+B-n).
Мы получили намного больше, чем хотели: у нас есть формула для среднего числа выигрышей с любой партии. Если n=B, то N=MB.
То есть, с самого начала, когда у Бена B=1 монета, а у его противника M=1000 монет, среднее число партий равно тысяче. Это немного удивительно, так как в половине случаев Бен все проиграет на первом же ходу. Но если почитать, например, эту заметку или еще эту, станут понятны причины. Игра может подзатянуться, и эти длинные траектории вносят большой вклад в среднее, несмотря на свою малую вероятность. Бен никогда в жизни не увидит партию в миллион ходов - а ее вклад в среднее уже учтен.
Теперь вычислим шансы Бена. Тут сюрпризов не будет, а вот метод заслуживает внимания. Обозначим вероятность выиграть, имея n монет, через P(n). Тогда уравнение будет таким:
P(n) = 0.5P(n+1) + 0.5P(n-1),
а граничные условия к нему: P(0)=0, P(M+B)=1 - ведь если денег нет, он уже проиграл, а если денег нет у противника, то уже выиграл.
Уравнение в общем виде мы уже решили - как вспомогательное - выше. Его решение: P(n) = C+Sn. Граничные условия дают C=0, S=1/(M+B). В итоге,
P(n) = n/(M+B),
а P(B) = B/(B+M).
Вполне предсказуемо. Вот так несложная теория (но не входящая в школьный курс) позволяет решить довольно сложную задачу.