2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 На дне глубокого сосуда…
Сообщение31.03.2008, 20:16 
Заслуженный участник
Аватара пользователя


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


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

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

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

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

 Профиль  
                  
 
 
Сообщение31.03.2008, 20:24 


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

 Профиль  
                  
 
 
Сообщение31.03.2008, 20:32 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение31.03.2008, 20:34 


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

 Профиль  
                  
 
 Re: На дне глубокого сосуда…
Сообщение31.03.2008, 21:04 
Заслуженный участник


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

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

 Профиль  
                  
 
 
Сообщение31.03.2008, 21:35 


21/03/06
1545
Москва
Промоделировал Вашу задачу при 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

 Профиль  
                  
 
 
Сообщение31.03.2008, 21:43 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Отличные весёлые картинки :) Я таких не делал. Здорово!

 Профиль  
                  
 
 
Сообщение31.03.2008, 21:54 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение31.03.2008, 22:01 


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

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

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

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

 Профиль  
                  
 
 
Сообщение31.03.2008, 23:23 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Изображение

Похоже?

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

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение01.04.2008, 21:25 


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

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

Вот что мне удалось придумать:
Обозначим кол-во красных шаров, находящихся в данный момент в урне за $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$

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

 Профиль  
                  
 
 
Сообщение01.04.2008, 22:40 
Заслуженный участник


09/02/06
4328
Москва
Вообще лучше выразжать через белых шаров и обозначать через $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 к бесконечности.

 Профиль  
                  
 
 
Сообщение01.04.2008, 22:53 


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

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

 Профиль  
                  
 
 
Сообщение01.04.2008, 23:47 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
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$ реально встречается.

 Профиль  
                  
 
 
Сообщение02.04.2008, 07:14 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group