Проблема с овцами Мабиногиона

В теории вероятностей задача об овце Мабиногиона или Мабиногиева урна — это задача стохастического управления, предложенная Дэвидом Уильямсом ( 1991 , 15.3), который назвал ее в честь стада волшебных овец из валлийского сборника сказок « Мабиногион» .

Заявление

И пришел он к долине, по которой текла река; и границы долины были лесистыми, и по обе стороны реки были ровные луга. И на одном берегу реки он увидел стадо белых овец, а на другом — стадо черных овец. И всякий раз, когда одна из белых овец блеяла, одна из черных овец переходила дорогу и становилась белой; и когда одна из черных овец блеяла, одна из белых овец переходила дорогу и становилась черной.

Передур, сын Евравка , из «Мабиногиона» в переводе леди Шарлотты Гест (1812–1895)

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

Оптимальное решение на каждом этапе — удалить ровно столько белых овец, чтобы черных овец было больше, чем белых.

Ссылки

• Чан, Теренс (1996), «Некоторые диффузионные модели для задачи Уильямса о овцах Мабиногиона», «Достижения в области прикладной теории вероятностей » , 28 (3): 763–783, doi : 10.2307/1428180 , MR   1404309
• Уильямс, Дэвид (1991), Вероятность с мартингалами , Кембриджские математические учебники, издательство Кембриджского университета