Задача про 3 буфера

[svv]

Обозначим количество заявок в $1,2,3$ буферах соответственно $i,j,k$. Так как числа целые и удовлетворяют условиям $0 \leqslant i,j,k \leqslant n$, всего возможно $(n+1)^3$ комбинаций значений.

Тройку чисел $(i,j,k)$ можно интерпретировать как координаты точки в трёхмерном пространстве. Точки, соответствующие допустимым значениям $(i,j,k)$, образуют кубическую сетку (точки куба $0 \leqslant x,y,z \leqslant n$, имеющие целочисленные координаты). Каждый узел сетки — это возможное состояние всех трёх буферов. Например, узел с координатами $(2,7,4)$ соответствует состоянию, когда в первом буфере 2 заявки, во втором 7 заявок, в третьем 4 заявки.

Представьте одну подвижную точку, которая с каждым ходом перемещается с одного узла на другой. В начале (положение 0) она была в узле $(0,0,0)$, т.е. ни в одном буфере не было заявок. После первого хода она с вероятностью $P_1$ попадёт в узел $(1,0,0)$, с вероятностью $P_2$ в узел $(0,1,0)$ и с вероятностью $P_3$ в узел $(0,0,1)$. Теперь мы имеем положение $1$. В зависимости от положения $1$ после второго хода мы получим с разными вероятностями несколько возможных вариантов положения $2$. И так далее.

После $\ell$-ого хода мы получаем множество вариантов положения $\ell$ с различными вероятностями. В каждом узле сетки $(i,j,k)$ мы можем написать число $p^{\ell}_{i,j,k}$ (верхний индекс — номер положения), которое означает вероятность того, что подвижная точка, двигаясь случайно, попадёт после $\ell$-ого хода именно в этот узел. После очередного хода вероятности, написанные в каждом узле, изменятся, то есть числа $p^{\ell+1}_{i,j,k}$ будут какими-то другими.

Пока Вы меня понимаете?

[Vaarallinen]

svv в сообщении #1091577 писал(а):

Пока Вы меня понимаете?

Да,пока понятно.

[svv]

Далее вместо «положение» будем говорить «момент». Итак, после $\ell$-го хода наступает $\ell$-ый момент.

Так вот, расчёт основан на следующем.
1) Мы знаем вероятности для нулевого момента (перед первым ходом). Именно, подвижная точка достоверно находится в узле $(0,0,0)$. Стало быть, $p^{0}_{0,0,0}=1$ и $p^{0}_{i,j,k}=0$ для остальных узлов.
2) Если мы знаем все вероятности для момента $\ell$, мы можем вычислить все вероятности для момента $\ell+1$.

Вот рекуррентная формула:
$p^{\ell+1}_{i,j,k}=p^{\ell}_{i-1,j,k}\;P_1+p^{\ell}_{i,j-1,k}\;P_2+p^{\ell}_{i,j,k-1}\;P_3$
Она справедлива с двумя оговорками:
$\bullet$ Работает только первый диспетчер
$\bullet$ Если в правой части в каком-то слагаемом один из индексов принимает некорректное значение (меньше нуля), это слагаемое выбрасывается. (Или, что эквивалентно, соответствующая вероятность $p^\ell_{...}$ для несуществующего узла считается нулевой.)

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

[Vaarallinen]

svv в сообщении #1091607 писал(а):

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

В состояние $(i,j,k)$ на $l+1$ моменте мы можем прийти 3 способами. На $l$ - ом моменте мы уже $j$ раз отправляем заявку во второй буфер; $k$ раз в третий буфер и $i-1$ раз в 1 буфер. Поэтому на $l+1$ моменте нам надо,чтобы заявка ушла в первый буфер. Вероятность этого у нас $p^{l}_{(i-1,j,k)}P_1$.

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

UPD.

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

[svv]

Vaarallinen в сообщении #1091615 писал(а):

В состояние $(i,j,k)$ на $l+1$ моменте мы можем прийти 3 способами.

Да, верно. При этом события
$\bullet$ в результате $(\ell+1)$-го хода система попала в состояние $(i,j,k)$ из состояния $(i-1, j, k)$
$\bullet$ в результате $(\ell+1)$-го хода система попала в состояние $(i,j,k)$ из состояния $(i, j-1, k)$
$\bullet$ в результате $(\ell+1)$-го хода система попала в состояние $(i,j,k)$ из состояния $(i, j, k-1)$
являются взаимоисключающими (здесь нужно такое слово). А вероятность того, что произойдёт любое из взаимоисключающих событий, равна сумме вероятностей каждого из них.

Теперь найдём, например, вероятность первой альтернативы. Для этого должны произойти совместно два события:
$\bullet$ в момент $\ell$ система находилась в состоянии $(i-1,j,k)$
$\bullet$ на $(\ell+1)$-м ходу диспетчер положил заявку в буфер 1
Эти события независимы (вероятности $P_1,P_2,P_3$ не зависят от состояния), поэтому вероятность того, что эти события произойдут совместно, равна произведению их вероятностей.

Аналогично для второй и третьей альтернатив.

Дальнейшая программа:
$\bullet$ Записать рекуррентную формулу для $\ell>n$ (или $\ell>n+1$, Вы сами уточните) — с учётом действий второго диспетчера. В ней будет уже побольше слагаемых (9 или, если объединить некоторые, 7), но для компьютерной программы, которая, как предполагается, будет это вычислять, это — тьфу.
$\bullet$ Учесть эффекты, связанные с полным или пустым буфером (с которых мы начинали разговор). Вы теперь понимаете, что в нашей геометрической интерпретации этому соответствуют узлы, находящиеся на поверхности (на гранях) куба.

Вот и всё. Уверен, Вы справитесь.

Upd. Мы не расстаёмся: Вы напишете формулу — я проверю, у Вас могут быть вопросы, и т.д.

[Vaarallinen]

svv
Итак,вот что получилось.

Чтобы получить блокировку по первому буферу на $n+m$ шаге нам надо выполнение следующих условий на $n+m-1$ шаге:
$i = n$, а во втором буфере $a$ заявок или в третьем $b$ заявок (считаем,что $i$ - ая ось соответствует первому буферу; $j$ - второму; $k$ - третьему);
$j = 0$ или $k = 0$. При этом второй и третий буфер могут быть оба пустые.

Вероятность такого события: $P = p^{n+m-1}_{n,0,b} \cdot P_1 \cdot G_2 + p^{n+m-1}_{n,a,0} \cdot P_1 \cdot G_3 + p^{n+m-1}_{n,0,0} \cdot P_1 \cdot (G_2 + G_3)$.

Аналогичные рассуждения для второго и третьего буферов. Тогда:

$P = p^{n+m-1}_{n,0,b} \cdot P_1 \cdot G_2 + p^{n+m-1}_{n,a,0} \cdot P_1 \cdot G_3 + p^{n+m-1}_{n,0,0} \cdot P_1 \cdot(G_2 + G_3) +$ $p^{n+m-1}_{0,n,c} \cdot P_2 \cdot G_1 + p^{n+m-1}_{d,n,0} \cdot P_2 \cdot G_3 + p^{n+m-1}_{0,n,0} \cdot P_2 \cdot (G_1 + G_3) +$ $+ p^{n+m-1}_{f,0,n} \cdot P_3 \cdot G_2 + p^{n+m-1}_{0,e,n} \cdot P_3 \cdot G_1 + p^{n+m-1}_{0,0,n} \cdot P_3 \cdot (G_2 + G_1)$.

[svv]

Vaarallinen в сообщении #1091854 писал(а):

Вероятность такого события: $P = p^{n+m-1}_{n,0,b} \cdot P_1 \cdot G_2 + p^{n+m-1}_{n,a,0} \cdot P_1 \cdot G_3 + p^{n+m-1}_{n,0,0} \cdot P_1 \cdot (G_2 + G_3)$.

Достаточно близко к истине. Ваша формула эквивалентна вот чему (перегруппируем слагаемые):
$P = (p^{n+m-1}_{n,0,0}+p^{n+m-1}_{n,0,b}) \cdot P_1 \cdot G_2 + (p^{n+m-1}_{n,0,0}+p^{n+m-1}_{n,a,0}) \cdot P_1 \cdot G_3$
Я понимаю, что Вы хотите сказать: здесь $b$ означает любое число. Но в формулу-то надо подставить какое-то конкретное $b$. А откуда его взять?

Давайте введём удобное обозначение. Блокировка 1,3 означает ситуацию, когда первый диспетчер пытается положить заявку в уже полный буфер 1, а второй пытается взять заявку из пустого буфера 3.

Казалось бы, ситуация определённая. Но при этой блокировке возможно ещё $n+1$ взаимоисключающих альтернатив, отличающихся значением второго буфера, который в такой блокировке не участвует. По правилам теории вероятностей, вероятность блокировки 1,3 равна сумме вероятностей всех альтернативных вариантов, то есть
$P_{1,3}=P_1\;G_3\;\sum\limits_{a=0}^n p^{n+m-1}_{n,a,0}$
А это как раз хорошо, потому что нам даны вероятности конкретных значений всех буферов, в том числе второго, именно таков наш строительный материал. Хоть в формулу входит переменная $a$, это немая переменная суммирования, её можно заменить на другую, например, $j$ (так и сделаю), а левая часть от какого-то конкретного значения $a$ не зависит.

Итак, вероятность того, что на ходу $n+m$ возникнет блокировка 1,2 или 1,3:
$P = P_1\;G_2\;\sum\limits_{k=0}^n p^{n+m-1}_{n,0,k} + P_1\;G_3\;\sum\limits_{j=0}^n p^{n+m-1}_{n,j,0}$

[Vaarallinen]

svv в сообщении #1092005 писал(а):

Как насчет блокировки 1,1 — она возможна? (Это вопрос постановки задачи.)

Что под этим подразумевается? Ситуация, когда оба диспечера выбирают первый буфер, когда в нем уже $n$ заявок?

[svv]

Извините, ум за разум зашёл. Считайте, что я этого не говорил.
Да, я имел в виду такую ситуацию, забыл, что это не считается блокировкой.

[Vaarallinen]

svv в сообщении #1092007 писал(а):

Извините, ум за разум зашёл. Считайте, что я этого не говорил.
Да, я имел в виду такую ситуацию, забыл, что это не считается блокировкой.

Хорошо :)

Я утром подробнее посмотрю то,что Вы написали.

[svv]

Теперь надо написать рекуррентную формулу с учётом действий второго диспетчера, про которую я говорил, что в ней будет то ли 7, то ли 9 слагаемых.

[Vaarallinen]

svv в сообщении #1092009 писал(а):

Теперь надо написать рекуррентную формулу с учётом действий второго диспетчера, про которую я говорил, что в ней будет то ли 7, то ли 9 слагаемых.

Пусть на $l$ - ом шаге мы оказались в точке $(i-1,j,k)$. На $l+1$ включается второй диспечер и теперь нам надо это учитывать. Диспечеры действуют независимо друг от друга.

Итак, получается такое соотношение для $l+1$ шага: $p^{l}_{i-1,j,k} \cdot P_1 \cdot G_1 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_2 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_3$. То есть, первый диспечер выбирает первый буфер, а второй диспечер выбирает первый буфер ИЛИ второй диспечер выбирает второй буфер ИЛИ второй диспечер выбирает третий буфер.

Для точки $(i,j-1,k)$: $p^{l}_{i,j-1,k} \cdot P_2 \cdot G_1 + p^{l}_{i,j-1,k} \cdot P_2 \cdot G_2 + p^{l}_{i,j-1,k} \cdot P_2 \cdot G_3$.

Для точки $(i,j,k-1)$: $p^{l}_{i,j,k-1} \cdot P_3 \cdot G_1 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_2 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_3$.

В итоге: $p^{l}_{i-1,j,k} \cdot P_1 \cdot G_1 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_2 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_3 +$$ p^{l}_{i,j-1,k} \cdot P_2 \cdot G_1 + p^{l}_{(i,j-1,k)} \cdot P_2 \cdot G_2 + p^{l}_{(i,j-1,k)} \cdot P_2 \cdot G_3 +$$ + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_1 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_2 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_3$.

Немного в раздумьях, какую нотацию выбрать для $p^{l+1}_{...}$. Пока у нас был только первый диспечер, то все было понятно: из состояний на $l$-ом шаге $(i-1,j,k)$, $(i,j-1,k)$, $(i,j,k-1)$ в результате работы этого диспечера на $l+1$ мы однозначно приходили в состояние $(i,j,k)$. Но ведь теперь мы можем двигаться не только "вперед" по осям, но и "назад".

[svv]

Vaarallinen в сообщении #1092178 писал(а):

Но ведь теперь мы можем двигаться не только "вперед" по осям, но и "назад".

Верно. И потому в результате действий двух диспетчеров (слово пишется с буквой «т») точка-состояние по одной координате съезжает вперёд, а по другой назад. Например, было состояние $(2,7,4)$. Допустим, первый диспетчер положил заявку в буфер 1, второй забрал из буфера 2. В результате такого «хода 1,2» (будем так говорить) состояние будет $(3,6,4)$. Иначе говоря (и обобщая), в результате хода 1,2 мы попадаем в точку $(i,j,k)$ из точки $(i-1,j+1,k)$.

Собственно говоря, второй диспетчер для того и нужен, чтобы не позволять точке-состоянию упереться в угол куба $(n,n,n)$ («все буферы заполнены») и застрять там навсегда.

Подправьте с учётом этого формулу.

[Vaarallinen]

svv в сообщении #1092256 писал(а):

Подправьте с учётом этого формулу.

$p^{l+1}_{i,j,k} =$ $p^{l}_{i,j,k} \cdot P_1 \cdot G_1 + p^{l}_{i-1,j+1,k} \cdot P_1 \cdot G_2 + p^{l}_{i-1,j,k+1} \cdot P_1 \cdot G_3 +$ $p^{l}_{i+1,j-1,k} \cdot P_2 \cdot G_1 + p^{l}_{i,j,k} \cdot P_2 \cdot G_2 + p^{l}_{i,j-1,k+1} \cdot P_2 \cdot G_3 +$ $+ p^{l}_{i+1,j,k-1} \cdot P_3 \cdot G_1 + p^{l}_{i,j+1,k-1} \cdot P_3 \cdot G_2 + p^{l}_{i,j,k} \cdot P_3 \cdot G_3$

Некоторые пояснения.

$p^{l}_{i,j,k} \cdot P_1 \cdot G_1 $ - формула такая, потому что если нет блокировки, то в буфер будет положена заяввка и тут же забрана. Что будет, если буфер полон и оба диспетчера выбирают его - обсуждалось на первой странице.

[svv]

Да, формула правильная. В ней 9 слагаемых. Если же сгруппировать коэффициенты при $p^\ell_{i, j, k}$, которое встречается 3 раза, их будет 7. Но делать это не нужно, и так хорошо.

Следующий шаг.
Осознайте, что формула неприменима для узлов на поверхности куба (т.е. таких, у которых одна или несколько координат равны $0$ или $n$).
Осознайте, что единственно правильного варианта для поверхностных узлов нет, так как он зависит от дополнительных условий задачи: надо дополнительно оговаривать, что происходит, когда диспетчер пытается положить заявку в полный буфер или забрать из пустого. Вы говорили, что в этом случае происходит блокировка по одному диспетчеру, но нужно четко сформулировать, что происходит с буферами, продолжается ли «игра» и т.д. Возможно, Вы это уже говорили, тогда, пожалуйста, повторите.