Zasada odroczenia decyzji

Zasada odroczonych decyzji jest techniką stosowaną w analizie algorytmów losowych .

Definicja

Losowy algorytm dokonuje zestawu losowych wyborów. Te przypadkowe wybory mogą być misternie powiązane, co utrudnia ich analizę. W wielu z tych przypadków stosowana jest zasada odroczenia decyzji . Ideą tej zasady jest to, że cały zestaw losowych wyborów nie jest dokonywany z góry, ale raczej ustalany dopiero po ujawnieniu ich algorytmowi.

Aplikacje

Zegarowa gra w pasjansa

Zasada służy do oceny i określenia prawdopodobieństwa „wygranej” z talii kart . Chodzi o to, aby losowe wybory się rozwijały, aż iteracja zakończy się na 52, gdzie jeśli czwarta karta zostanie wyciągnięta z grupy oznaczonej „K”, gra się kończy.

Źródła

• M. Mitzenmacher i E. Upfal . Prawdopodobieństwo i obliczenia: algorytmy losowe i analiza probabilistyczna . Cambridge University Press, Nowy Jork (NY), 2005. Część 1.3, strona 9.