Którą z przepadających szans wybrać?

Problem. Dana jest maszyna losująca liczby z przedziału [0,1] z rozkładem jednostajnym. Wiemy, że w jednej serii zostanie wykonanych n losowań. Po każdym losowaniu z danej serii możemy powiedzieć “zamawiam” i “zamówić” w ten sposób wylosowaną liczbę. Możemy powiedzieć “zamawiam” tylko raz podczas jednej serii losowań. Po wykonaniu wielu serii dostaniemy wypłatę będącą sumą wszystkich liczb, które zamówiliśmy. Naszym celem jest zarobić jak najwięcej. Jaką stragią powinniśmy grać, aby zmaksymalizować zysk? Jaka będzie średnia wartość wybranych przez nas liczb po dużej ilości serii n losowań?

Niech (mierzalna) funkcja f(x,k) przyjmująca wartości ze zbioru \{0, 1\} będzie funkcją decyzyjną, w tym sensie, że jeżeli f(x,k) = 1 gdzie k - 1 jest ilością losowań w serii które jeszcze pozostały do wykonania, zaś x jest wartością obecnie wylosowaną, to zamawiamy obecnie wylosowaną liczbę x. Będziemy szukali optymalnej funkcji f.

Niech I_k = \{x\in[0,1]:f(x,k) = 1 \}. Niech d(I_k) oznacza “sumaryczną długość” (miarę) zbioru I_k. Niech e(I_k) oznacza wartość średnią zbioru I_k.

Zauważmy, że f(x,1) = 1 dla dowolnego x\in[0,1]. A zatem znamy już naszą optymalną strategię dla n = 1.

Załóżmy, że optymalna strategia jest już znana dla n - 1.

Niech E_{n-1} oznacza średnią wartość “zamówionej” liczby z serii n - 1 losowań.

Rozpatrujemy teraz serię n > 1 losowań.
Zauważmy, że we wszystkich sytuacjach, w których pierwsza wylosowana liczba zawiera się w I_n, “zamówioną” liczbą będzie właśnie ona. Zdarzenie losowe, które polega na tym, że zostaje zamówiona pierwsza liczba oznaczymy jako A_n. A więc średnia warunkowa “zamówionej” liczby pod warunkiem zajścia zdarzenia A_n będzie po prostu e(I_n). Zaś średnią warunkowa “zamówionej” liczby w przypadku zajścia zdarzenia A^c_n będzie oczywiście E_{n-1}. Ze średnich warunkowych możemy łatwo wyznaczyć średnią ogólną.

E_n = e(I_n)P(A_n) + E_{n-1}P(A^c_n) = e(I_n)d(I_n) + (1 - d(I_n))E_{n-1}.

Zauważmy, że dla zadanej d(I_n), e(I_n) będzie największe jeżeli I_n będzie postaci [x_n, 1]. A zatem w naszej optymalnej strategii musi zachodzić I_n = [x_n,1]. Zadanie sprowadza się zatem do wyznaczenia takiego x_n, które maksymalizuje E_n.

Przepiszmy wobec tego E_n w zależności od x_n.

E_n = \cfrac{1 + x_n}{2}(1 - x_n) + x_nE_{n-1} = \cfrac{1 - x^2_n}{2} + x_nE_{n - 1}.

E_n jest więc funckją kwadratową x_n. Zagadnienie maksymalizacji jest więc trywialne. \cfrac{\partial E_n}{\partial x_n} = -x_n + E_{n-1}. A zatem x_n = E_{n - 1} maksymalizuje E_{n}.

Zatem

E_{n} = \cfrac{1 + E^2_{n - 1}}{2},

czyli tym samym

x_n = \cfrac{1 + x^2_{n - 1}}{2}.

Znaleźliśmy więc postać optymalnej strategii.
Niech x_1 = 0 i x_k = \cfrac{1 + x^2_{k - 1}}{2} dla k > 1. Jeżeli czeka nas jeszcze k - 1 losowań należy “zamówić” wylosowaną liczbę x jeżeli x \geq x_k.

Podamy teraz kilka wartości ciągu x_n zaokrąglonych do 4 miejsc po przecinku.

x_1 = 0

E_1 = x_2 = 0.5

E_2 = x_3 = 0.625

E_3 = x_4 = 0.6953

E_4 = x_5 = 0.7417

E_5 = x_6 = 0.7751.

  1. Podgląd live
    Nie opublikowałeś jeszcze tego komentarza! Aby opublikować naciśnij przycisk Opublikuj Komentarz.

Dodaj komentarz