|
К задаче про монетку:
Давайте рассмотрим серию из N игр. Обозначим k_0 число игр, в которых не выпало ни одного орла, k_1 - в которых выпал 1 орел, k_2 - в которых выпало 2 орла и так далее до бесконечности. Cумма всех k_i для i от 0 до бесконечности (что мы обозначмим как sum[k_i, {i,0, inf}]) равна N. Набор значений k_i характеризует исход N игр с заданной выплатой
L = sum[(2^i-1)*k_i, {i, 0, inf}] (1)
Найдем вероятность, с которой реализуется данный набор k_i.
Всего в данной последовательности игр выпало m орлов, причем
m = sum[i*k_i, {i, 0, inf}] = sum[i*k_i, {i, 1, inf}]
и N решек. Тот или иной исход бросания реализуется с вероятностью 1/2, поэтому мы имеем коэффициент 1/2^(N+m). Чтобы получить искомую вероятность, надо умножить его на число комбинаций результатов игр, дающих в итоге заданный набор k_i: N!/(k_0! k_1! ... k_i! ...)
Итого, вероятность реализации набора k_i есть
p = N!/(2^(N+m) k_0! k_1! ... k_i! ...) (2)
и она соответствует выплате (1).
Чтобы найти самый вероятный исход серии N игр, нам надо найти минимум знаменателя в (2). Воспользуемся приближенной формулой Стирлинга
ln[n!] = n ln[n] - n
и запишем логарифм знаменателя в (2) (который достигает минимума тогда же, когда и сам знаменатель)
f = ln[2]*(N+m) + sum[k_i*ln[k_i], {i, 0, inf}] - sum[k_i, {i, 0, inf}]
Последняя сумма есть просто N; кроме того, подставим сюда m в виде суммы и выразим k_0 как N - sum[k_i, {i, 1, inf}]. Получим
f = (ln[2]-1)*N + ln[2]*sum[i*k_i, {i, 1, inf}] + sum[k_i*ln[k_i], {i, 1, inf}] + (N - sum[k_i, {i, 1, inf}])*ln[N - sum[k_i, {i, 1, inf}]]
Нам необходимо найти минимум данной функции от переменных k_1, ... k_i, ... Для этого надо приравнять нулю частные производные по всем k_i. Для i=j имеем
df/dk_j = j*ln[2] + 1 + ln[k_j] - (1 + ln[N - sum[k_i, {i, 1, inf}]]) == 0
или, проведя элементарные преобразования,
2^j * k_j + sum[k_i, {i, 1, inf}]] = N (3)
Эта формула задает систему из бесконечного числа линейных уравнений на бесконечное число переменных k_i, которая, к счастью, решается тривиально. Вычтем из j+1 го уравнение j-е. Получим:
k_(j+1) = k_j/2
Отсюда немедленно следует, что для k_i удовлетворяющих системе (3), sum[k_i, {i, 1, inf}]] = 2*k_1, а следовательно, из уравнения для j = 1,
k_1 = N/4
Отсюда
k_2 = N/8
k_3 = N/16
...
k_i = N/2^(i+1)
Все члены, для которых N/2^(i+1) < 1 будут, очевидно, нулями, поэтому всего будет
r = ln[N]/ln[2] - 1
ненулевых k. Подставляя k_i в формулу для L, получаем, что все ненулевые члены равны N/4, и, следовательно, полная сумма наиболее вероятной выплаты есть
L = N/4 (ln[N]/ln[2] - 1)
Это сообщение отредактировал Gombo - 13/03/2006, 14:42
|
