На дне глубокого сосуда…

[незваный гость]

На дне глубокого сосуда
Лежат спокойно $n$ шаров.
Поочередно их оттуда
Таскают двое дураков.
Сие занятье им приятно.
Они таскают $t$ минут.
И, вынув шар, его обратно
В сосуд немедленно кладут.
Ввиду условия такого,
Сколь вероятность велика,
Что первый был глупей второго,
Когда шаров он вынул $k$?
. . . . . В.Скитович

В связи с повышением общего уровня образования задачу изменили:

Дураки тащат шар из сосуда, и принимают решение: если шар красный, его выбрасывают (и количество шаров в сосуде убывает), а если белый — вместо него кидают в сосуд красный шар (количество шаров в сосуде остаётся прежним, но цветовой состав меняется). С какой вероятностью через $t$ минут будет вынут красный шар, если до начала трудовой деятельности в сосуде были только белые шары числом $n$?

Я должен честно признать, что решать эту задачу не умею. Но, например, вариантом ответа может быть приблизительная вероятность как функция $t/n$, при больших $n$. Мне любопытно также распределения количества белых и красных шаров в конкретный момент времени.

P.S. 2 Архипов: я знаю, задача некорректно поставлена.

[e2e4]

Мне кажется, в условии не хватает двух величин: времени вытаскивания очередного шара (оно постоянно, да?), и главное - начального кол-ва красных (или всех) шаров. От второго парамтера будут естественно изменяться требуемые Вам зависимости.

[незваный гость]

Имеется в виду, что в начальный момент в сосуде были только белые шары, числом $n$. Что же касается времени, то его, как обычно, считают в операциях.

[e2e4]

Немного подумал, и понял, что смесь красных и белых шаров - это определенный шаг задачи, где изначально были только белые шары. Так что действительно достаточно рассмотреть начальное положение только с белыми шарами.

[Руст]

незваный гость писал(а):

Дураки тащат шар из сосуда, и принимают решение: если шар красный, его выбрасывают (и количество шаров в сосуде убывает), а если белый — вместо него кидают в сосуд красный шар (количество шаров в сосуде остаётся прежним, но цветовой состав меняется). С какой вероятностью через $t$ минут будет вынут красный шар, если до начала трудовой деятельности в сосуде были только белые шары числом $n$?
P.S. 2 Архипов: я знаю, задача некорректно поставлена.

Причём тут $t$ минут. Я думаю имеется ввиду при $t$ - ом вынимании. Какой смысл в том, что дураков несколько. Достаточно одного.
В таком случае задача корректная и решабельная.

[e2e4]

Промоделировал Вашу задачу при n= 600. График кол-ва белых шаров - более-менее плавная, вогнутая, убывающая кривая с максимумом, естественно, 600 и минимумом 0. График кол-ва красных шаров имеет явный экстремум (хотя, конечно, т.к. работаем со случайными величинами, линия имеет множество локальных экстремумов), на концах обращаясь в 0. Напиминает участок окружности или часть параболы с ветвями вниз. Т.к. в моей программе используется еще понятие пустого шара (массив из 600 элеменотов, случайным образом выбираем из него, если красный, то данная ячейка массива становится пустым шаром) то заодно построил и их график. Он довольно симметричен с графиком белых шаров, только кривая - возрастающая. Интересно, что максимум графика красных шаров очень близок к точке пересечения графика белых шаров и пустых шаров.

Ну а вероятность вытащить красный шар, как отношение кол-ва красных к сумме кол-ва красных и белых шаров в начальной части графика примерно совпадает с графиком красных шаров (с учетом масштаба, я домножил эту вероятность на n=600), в среднем возрастает, одновременно все больше и больше "прыгая", в конце - вообще довольно размыта, но приближается опять таки к 1 (ну или к 600 с учетом домножения).

Надеюсь, ясно написал. Думаю, Вы без труда и сами промоделируете.

Важно, что зависимости вероятностей и кол-ва шаров в среднем, явно существуют и вполне определенные. Вопрос - как их найти.

Добавлено спустя 3 минуты 45 секунд:

Вот код моделирующей программы (Builder, но от билдера там только рисование графиков) на всякий случай, за алгоритм прошу не пинать - естественно он самый простой и не оптимизированный:

#define WHITE 2
#define RED 1
#define EMPTY 0

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   const int n = 600;
   int balls[n];

   for(int i=0;i<n;i++)
      balls[i] = WHITE;

   int n_white = n, n_red = 0, n_empty = 0;

   int x = 0;
   while(n_white || n_red)
   {
      Image1->Canvas->Pixels[x][Image1->ClientHeight - n*n_red/(n_red+n_white)] = clBlue;

      int nn;
      while( balls[nn = rand()%n] == EMPTY);
      if(balls[nn] == RED) {balls[nn] = EMPTY;n_red--;n_empty++;}
      else {balls[nn] = RED;n_white--;n_red++;}

      Image1->Canvas->Pixels[x][Image1->ClientHeight - n_white] = clGreen;
      Image1->Canvas->Pixels[x][Image1->ClientHeight - n_red] = clRed;
      Image1->Canvas->Pixels[x++][Image1->ClientHeight - n_empty] = clBlack;
   }
}

Добавлено спустя 26 минут 21 секунду:

график 1-го прогона

график многих прогонов
Зеленая - кол-во белых шаров, черная - кол-во пустых шаров, красная - кол-во красных шаров, синяя - вероятность вытащить красный шар * 600

[незваный гость]

Отличные весёлые картинки Я таких не делал. Здорово!

[Руст]

Не очень понятны ваши графики. Тут имеется очевидный инвариант:
$Nr+2Nw+t\equiv 2n$, где $Nr$ количество красных шаров после $t$ шагов $Nw$ - количество белых шаров, $t$ - количество шагов. Поэтому, при $t=2n$ очевидно ничего не остаётся и на этом шаге может выниматься только красный шар.

[e2e4]

Графики построены как качественная иллюстрация. В графике множества прогонов Вы можете видеть справа вверху прямой синий отрезок - это вероятность вытащить красный шар равная единице. Просто несколько раз белые шары закончились полностью, а красные оставались.
То, что в графиках есть ошибка (синий сдвинут по х относительно остальных на 1 пиксель), я не отрицаю - это видно и по алгоритму. Крайние точки тоже могут быть не видны.

Важно, как мне кажется, поведение графиков белых и красных шаров - они имеют вполне определенный характер, который наверняка может быть как-то довольно просто найден.

незваный гость писал(а):

Здорово!

Спасибо на добром слове, на самом деле Ваша задача заинтересовала, вот и построил для себя, ибо решить аналитически не могу .

[незваный гость]

Похоже?

Добавлено спустя 20 минут 6 секунд:

Руст писал(а):

Причём тут $t$ минут. Я думаю имеется ввиду при $t$-ом вынимании. Какой смысл в том, что дураков несколько. Достаточно одного.

В честь старой песни, приведённой в эпиграфе. Вы абсолютно правы по обоим пунктам.

Руст писал(а):

В таком случае задача корректная и решабельная.

Конечно. Но Вы — не Архипов.

e2e4: забавно, что зелёная и красная линии пересекаются аккурат в точке максимума красной.

[e2e4]

незваный гость, Вы видимо построили какой-то усредненный график для множества прогонов модели?

Да, довольно забавно поведение красного и зеленого графиков.

Вот что мне удалось придумать:
Обозначим кол-во красных шаров, находящихся в данный момент в урне за $k$.
Обозначим общее начальное кол-во шаров за $n$.
Обозначим номер хода (очередного вытаскивания) как $s$. При $s = 0$ имеем $k = 0$.
Обозначим $V_{s,k}$ как вероятность нахождения $k$ красных шаров в урне после хода $s$.

Сразу заметим, что $V_{s,s-2m-1} \equiv 0$ при $m \in \mathbb{Z}$.
Заметим, что кол-во оставшихся шаров в урне при шаге $s$ и кол-ве красных шаров $k$ будет $n - \dfrac{s-k}{2}$
Вероятность нахождения $k$ красных шаров после хода $s$ выразится следующим образом:
$V_{s,k} = V_{s-1, k-1}\left(1-\dfrac{k-1}{n- ^{(s-k)}/_2}\right) + V_{s-1, k+1}\left(\dfrac{k+1}{n- ^{(s-k)}/_2 + 1}\right)$

Обозначим среднее кол-во красных шаров после очередного хода как $K_s$.
Оно выразится следующим образом:
$K_s = \sum\limits_{m=0}^{\lfloor ^S/_2 \rfloor}(s-2m)V_{s,s-2m} = \ldots$

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

[Руст]

Вообще лучше выразжать через белых шаров и обозначать через $p_k(t)$ вероятность того, что через t шагов имеется k белых шаров и при этом количество красных шаров $m=2n-2k-t$. При этом по крайней мере отделений на 2 избавляемся. Соответствующее рекурентное соотношение имеет вид
(1)

$$p_k(t+1)=p_k(t)\frac{2n-t-2k}{2n-t-k}+p_{k+1}(t)\frac{k+1}{2n-t-k-1}.$$

Начальные значения $p_k(0)=0,k<n, \ p_n(0)=1$.
Только мне не удалось решит это аналитический методом подбора биномиальных сомножителей.
Можно ввести производящую функцию

$$P_t(x,y,z)=\sum_{2k+m+t=2n}p_k(t)x^ky^mexp((k+m)z).$$

При этом получается дифференциальное уравнение

$$\frac{\partial P_{t+1}(x,y,z)}{\partial z}=(y\frac{\partial }{\partial x}+exp(-z)\frac{\partial }{\partial y})P_t(x,y,z).$$

Но из-за некоммутирования дифференциальных операторов слева и справа не удалось решить в явном виде и это уравнение. Поэтому, думаю вряд ли существует удобовыражаемое аналитическое решение для произвольных t.
Однако, вполне правдоподобно существование асимптотических формул для больших n, когда $t=sn$ и выражение искомой вероятности как функции от s с точностью о(1) стремящимся к 0 при стремлении n к бесконечности.

[e2e4]

Руст писал(а):

Но из-за некоммутирования дифференциальных операторов слева и справа не удалось решить в явном виде и это уравнение. Поэтому, думаю вряд ли существует удобовыражаемое аналитическое решение для произвольных t.
Однако, вполне правдоподобно существование асимптотических формул для больших n, когда $t=sn$ и выражение искомой вероятности как функции от s с точностью о(1) стремящимся к 0 при стремлении n к бесконечности.

Однако, судя по виду графиков, усредненные зависимости довольно простые. Не имеет ли смысла пойти с конца - подобрать удовлетворяющую усредненным графикам зависимость кол-ва шаров от шага и начального кол-ва?

[незваный гость]

e2e4 писал(а):

Однако, судя по виду графиков, усредненные зависимости довольно простые. Не имеет ли смысла пойти с конца - подобрать удовлетворяющую усредненным графикам зависимость кол-ва шаров от шага и начального кол-ва?

Строго говоря, на графиках — ассимптотические, а не усреднённые зависимости. И не скажу, чтобы они выглядели просто. Особо элегантен синий график: Вы сможете прикинуть формулу, которая будет себя вести примерно так?

Добавлено спустя 39 минут 11 секунд:

Руст писал(а):

Однако, вполне правдоподобно существование асимптотических формул для больших n, когда и выражение искомой вероятности как функции от s с точностью о(1) стремящимся к 0 при стремлении n к бесконечности.

Собственно, это и есть постановка задачи. Я очень сомневаюсь в существовании компактной формы для точного распределения.

Вторая задача — уточнение этой ассимптотики. Ясно, что в данный момент времени $t$ мы можем иметь от $n-t$ до $n-t/2$ белых шаров. Тем не менее, вероятность крайних исходов очень мала (и быстро убывает с ростом $n$ при фиксированном $\tau = t/n$). Соответственно, возникает вопрос об описании $[n_1,n_2]: p([n_1,n_2], \tau n) = 1/2$ (или любой другой не зависящей от $n$ величине). Т.е., описания диапазона, где $n$ реально встречается.

[Руст]

Распределение при больших n и $t=sn, k=rn$ можно получить через биномиальные множители (наподобии интегрирующих множителей) в рекурентных формулировках. Для выбора точного множителя мешало одна 1 и при переходе к непрерывным переменным это можно учесть. Это моя идея как получить асимптотические формулы. У самого пока нет времени для дальнейшего занятия этим.