« poprzedni punkt   następny punkt »


14.6. Zastosowania

Na zakończenie tego wykładu przedstawimy trzy proste przykłady zastosowania poznanych pojęć.

Przykład 14.6.1

Dla ustalenia liczby ryb w jeziorze odławiamy pewną liczbę ryb, np. 1000sztuk. Złapane ryby znakujemy i wpuszczamy je do jeziora. Po upływie pewnego czasu dokonujemy odłowu uzyskując np.: 1200 ryb, wśród których było 25 znakowanych. Jak oszacować na tej podstawie liczbę ryb w jeziorze?

Przyjmijmy następujące interpretacje i oznaczenia:

N liczba ryb = liczba kul w urnie

B ryby znakowane = kule białe

C ryby nieznakowane = kule czarne

n ryby odłowione = liczba losowań zależnych

b wyłowione ryby znakowane = wylosowane białe

c wyłowione ryby nieznakowane = wylosowane czarne

Prawdopodobieństwo wylosowania b kul białych i c kul czarnych w n losowaniach

Aby na podstawie tych danych empirycznych oszacować liczbę ryb w jeziorze zastosujemy zasadę największej wiarygodności, polegającej na wyznaczeniu takiej liczby N, aby prawdopodobieństwo PN miało wartość największą.

Mamy

PN > PN-1 dla N<B ⋅ n/b,

PN < PN-1 dla N> B ⋅ n/b.

Zatem, PN osiąga największą wartość dla N = [B ⋅ n/b]. Czyli najbardziej wiarygodna liczba ryb w jeziorze wynosi 48000.


Przykład 14.6.2

Rozważmy program

Π : {
x:= 0; p := false;
while not p do

x := x+1;
p := random({true, false})

od
}.

Niech X oznacza zmienną losową taką, że X = i, jeśli program Π zatrzyma się po i-krokach (tzn. numer iteracji, w której po raz pierwszy wypadło 'true'). Niech prawdopodobieństwo wyboru obu wartości w zbiorze {true, false}wynosi1/2. Ile wynosi średni czas oczekiwania na zatrzymanie się tego programu?

Ponieważ P(X=k) = 1/2k. Zatem E(X) = Σ k ∈ N (k/ 2k) = 2. Zatem, średnio, program zakończy działanie po dwóch iteracjach.

Przykład 14.6.3

Niech będzie dany uporządkowany ciąg liczb rzeczywistych e1, e2, e3, ..., en należących do pewnego przedziału [a, b]. Niech zadanie polega na znalezieniu takiego i, że dana liczba x ∈ [a, b] należy przedziału [ei, ei+1). Przyjmijmy, że e0 = a, en+1 = b. Jeśli dany element x jest mniejszy od pierwszego elementu ciągu, to wynikiem algorytmu będzie 0, a jeśli element x jest większy od wszystkich elementów ciągu, to wynikiem algorytmu będzie n. Rozwiązaniem tego zadania może być algorytm przestawiony na Rys.14.6.1, przeszukujący sekwencyjnie elementy ciągu, tak długo, aż znajdzie odpowiedni przedział.

if (x< e1) then i := 0 else

if (x ≥ en) then i:= n else
i := 1;
while (x ≥ei+1) do
i := i+1
 od fi fi

Rys. 14.6.1 Sekwencyjne poszukiwania w ciągu uporządkowanym.

Koszt tego algorytmu, wyrażony liczbą wykonanych porównań elementów, zależy od danych, tzn. od konkretnych wartości elementów ei oraz od wartości x. Oczywiście w najgorszym razie porównamy x z wszystkimi elementami. Jest rzeczą interesującą zbadanie kosztu średniego tego algorytmu.

Niech X będzie zmienną losową, której wartością jest liczba porównań wykonanych przez nasz algorytm. Załóżmy, że dla dowolnego i = 0,1,..n prawdopodobieństwo tego, że ei ≤ x < ei+1 wynosi p, czyli

P(x ∈ [ei, ei+1)) = p = 1/(n+1).

Wartością zmiennej X jest 1, jeśli x należy do przedziału [e0,e1) (tzn. wtedy wykonujemy tylko 1 porównanie), oraz wartością zmiennej X jest 2, jeśli x należy do przedziału [en,en+1). Dla wszystkich pozostałych przypadków wartość zmiennej X jest większa od 2 i

X = i + 2 wtedy i tylko wtedy gdy x ∈ [ei, ei+1).

Zatem wartość oczekiwana zmiennej X wynosi:

E(X) = 1 ⋅ p + 2 ⋅ p + Σ i=1...(n-1) (2+i) ⋅ p = p(1+2+3+...+ (n+1)) = p(n+1)(n+2)/2 = 1 + n/2.



« poprzedni punkt   następny punkt »