Деликатесно-вероятностное

[spamsink]

Приобрел я шоколадное ассорти - непрозрачный мешок с маленькими шоколадками темного шоколада 3 разных сортов: 60%, 72%, sea salt almonds, по 17 штук каждого сорта. Один из этих сортов я предпочитаю больше других.

Чтобы растянуть удовольствие, каждый раз, когда мне хочется шоколада, я использую такую процедуру: Если в мешке осталась ровно одна шоколадка, то я её ем и выбрасываю пустой мешок, иначе я беру из мешка две шоколадки наугад. Если среди них найдется одна предпочитаемого сорта, я её кладу обратно, и ем другую. Если ни одна из них - не предпочитаемого сорта, я одну ем и одну кладу обратно случайным образом.

Вопрос: сколько в среднем останется шоколадок предпочитаемого сорта в мешке после того, как я съем последнюю из шоколадок других сортов? Как это значение зависит от исходного количества?

Численно это делается легко, а вот аналитически мне уже не очень.

Comments

[vak]

Ой, а мне все три нравятся, я их без разбору потребляю. :)
Но задачка прикольная.
Можно будет посчитать на досуге методом монте-карло.

[spamsink]

:) Так-то просто, и это позволяет оценить О большое, а вот аналитически...

[vanja_y]

У меня с помощью численных экспериментов и консультаций с oeis Слоана вроде получилось. Хотел бы я такие задачи решать путем чистых размышлений.

Обозначим через E(g,b) мат. ожидание количества любимых конфет в момент, когда не любимых не осталось, если в начале было g любимых и b не любимых. Тогда, если я ничего не напутал c рекурсией,

E(1,b) = 1
E(g,0) = g
          g (g-1) E(g-1,b) + b(2g+b-1) E(g,b-1)
E(g,b) = ----------------------------------------
                      (g+b)(g+b-1)                 .

Путем подбора, с последующей проверкой, у меня вышло, что

            (2g + 2b - 1)!!          g! b! 
E(g,b) = ---------------------  × -----------
          (2g-1)!! (2b + 1)!!     (g + b -1)!  

[spamsink]

Спасибо! Переход от рекуррентной формулы к явному виду я не осилил. :(

Результат для E(17,34), полученный по этой формуле вольфрамальфой, совпадает с полученным численно. Для E(x,2x) вольфрамальфа даёт, как и ожидается по численным результатам, разложение O(sqrt(x)), а точнее, sqrt(3)/2 * (pi/2)^1/4 * sqrt(x) и далее члены, пропорциональные sqrt(1/x) и мельче. Но угадать пропорциональность корню, глядя на формулу с факториалами, невозможно.

[vanja_y]

Интересно. У меня получается, что E(rx,sx) будет O(√x) для любых положительных r и s.
Я правда не уверен про константу, вроде корню четвертой степени из π неоткуда взяться.

Чтобы проще было находить асимптотики, я переписал формулу из первого комментария, используя

                    (2g + 2b)!                     (2g)!                  (2b)!(2b+1)  
(2g + 2b - 1)!! = ---------------    (2g-1)!! = ----------   (2b +1)!! = -------------
                   (g+b)! 2g + b                    g! 2g                     b! 2b

Тогда

          g + b    (2g + 2b)!        g! g!     b! b!
E(g,b) = ------ × --------------  × ------- ×  ------
         2b + 1    (g+b)!(g+b)!      (2g)!     (2b)!  

Число

  (2k)!
 -------
  k!k! 

это число Каталана C_k умноженное на к+1. Асимптотика для C_k

    4k
 -------
  k3/2 π1/2

дает асимптотику

  (2k)!         4k 
 ------- ~ -----------
  k!k!      k1/2 π1/2      .

Теперь первый множитель в формуле для E(g,b) в случае E(rx,sx) дает O(1), второй дает O(x^-1/2), a третий и четвертый дают каждый O(x^1/2). Если всё перемножить получим в точности O(x^1/2).

[vanja_y]

Забыл сказать, что степени четверок посокращаются.