Wir leiten jetzt die obige Lösungsstrategie her und gehen dabei von einer beliebigen
Anzahl n von Tagen aus, wobei man dafür auch allgemeiner die Bezeichnung "Objekte" oder "Gelegenheiten" wählen kann:
Die Wahrscheinlichkeit, die optimale Wahl zu treffen, hängt
von der Anzahl j der Tage ab, an denen man nur beobachtet.
Für jedes k ∈
{j+1,...,n
}
sei A
k das Ereignis, dass I) der k-te Tag T
k der beste ist und II)
T
k ausgewählt wird. Die Wahrscheinlichkeit von I) beträgt 1/n, und die Wahrscheinlichkeit von II)
beträgt j/(k-1), weil T
k genau dann ausgewählt wird, wenn sich der beste der ersten k-1 Tage
unter den ersten j Tagen befindet. Das Ereignis A
k tritt also mit der Wahrscheinlichkeit
P(A
k) = 1/n
·j/(k-1) ein.
Die besagte Strategie, exakt j Tage lediglich zu beobachten, ist genau dann erfolgreich, wenn
A
j+1∪ A
j+2 ∪ ... ∪ A
n eintritt.
Weil die Ereignisse A
j+1, A
j+2, ... A
n
paarweise disjunkt sind, erhalten wir für alle j mit
1 ≤ j < n die zugehörige Erfolgswahrscheinlichkeit:
Pj : = P(Aj+1) + P(Aj+2) + ... + P(An)
= j/n·(1/j + ... + 1/n-1).
Die Differenz P
j - P
j+1 =
1/n
·(1 - 1/j+1 - 1/j+2 - ... - 1/n-1)
wächst für alle j streng monoton und ist nichtnegativ für hinreichend große Zahlen j.
Folglich ergibt die kleinste Zahl j mit 1/j+1 + 1/j+2 + ... + 1/n-1 ≤ 1 die optimale Wartezeit, die wir mit
j
o bezeichnen. Gemäß der obigen Ausführungen ist dann
P
jo
= j
o/n
·(1/j
o + ... + 1/n-1)
die maximale Erfolgswahrscheinlichkeit.
