Kelly-Problem

Ein interessantes Problem im Zusammenhang mit dem aus der Finanztheorie bekannten Kelly-Wert (vgl. http://www.wallstreet-online.de/ws/community/board/thread.php?fid=84&tid=527991&offset=0&):
In einer Urne befinden sich 60 weiße und 40 schwarze Kugeln. Es werden alle Kugeln (ohne Zurücklegen) gezogen: Schwarz bedeutet Verlust des Einsatzes, bei Weiß kriege ich meinen Einsatz doppelt raus. Wie stark kann ich unter diesen Voraussetzungen mein Startkapital völlig sicher vermehren?
Der wichtige Unterschied zur Kelly-Berechnung: Die Gewinnwahrscheinlichkeit liegt nicht mehr konstant bei 60%! Aus diesem Grunde kann man insgesamt selbst dann gewinnen, wenn weniger weiße Kugeln in der Urne sind als schwarze.

Für die theoretische Durchleuchtung dieses Problems betrachte man zunächst den einfachen Fall, daß nur eine Kugel in der Urne ist. Ist sie schwarz, setzt man 0, und das Kapital bleibt erhalten, Kapitalvermehrung: K' = 1 · K. Ist sie dagegen weiß, so setzt man alles: Kapitalvermehrung: K' = 2 · K.
Nun sollen sich zwei Kugeln in der Urne befinden. Bei zwei weißen setzt man jedes Mal alles und erhält Kapitalvermehrung: K' = 4 · K; bei zwei schwarzen setzt man jedes mal 0 und erhält Kapitalvermehrung: K' = 1 · K.
Aber wieviel muß man anfangs setzen bei einer weißen und einer schwarzen Kugel in der Urne?
Dieser Anteil vom Kapital K sei r.
Zieht man zunächst die schwarze Kugel, ergibt sich K'(-) = K · (1 - r), und danach die weiße Kugel: K''(-) = 2 · K'(-) = 2 · K · (1 - r)
Zieht man zunächst die weiße Kugel, ergibt sich K'(+) = K · (1 + r), und danach die schwarze Kugel: K''(+) = 1 · K'(+) = K · (1 + r)
Da man nicht wissen kann, welche Kugel zuerst kommt, setzt man, um hundertprozentig sicher zu gehen, K''(-) und K''(+) gleich, also 2 · K · (1 - r) = K · (1 + r) und somit r = 1/3. Die Kapitalvermehrung beträgt dann K'' = K · (1 + 1/3) = K · 4/3
So könnte man bei drei Kugeln in der Urne den Starteinsatz r und die resultierende Kapitalvermehrung bei 1 oder 2 weißen Kugeln auf die Fälle mit insgesamt zwei Kugeln reduzieren, während 0 oder 3 weiße Kugeln bei insgesamt 3 Kugeln in der Urne auf die trivialen Lösungen K''' = K bzw. K''' = 2³ · K führen.
Betrachten wir aber gleich den allgemeinen Fall mit N Kugeln in der Urne, davon w weiße (0 <= w <= N). Die Kapitalvermehrung v(w; N) sei bekannt für alle w bei diesem N.
Nun seien N+1 Kugeln in der Urne, darunter w weiße (0 <= w <= N+1). Die Kapitalvermehrung bei w=0 ist trivialer Weise v(0; N+1) = 1, d. h., man setzt grundsätzlich gar nichts; die Kapitalvermehrung bei w=N+1 ist v(N+1; N+1) = 2 · v(N; N), d. h., man setzt natürlich alles. Es ist leicht zu zeigen, daß v(N; N) = 2^N.
Alle anderen Fälle, also 0 < w < N+1 führt man auf Fälle mit insgesamt nur N Kugeln zurück:
Zieht man zuerst eine schwarze Kugel, so ist der Einsatz futsch: K'(-) = K · (1 - r). Danach wird K'(-) aber gemäß der Kapitalvermehrung v(w, N) gesteigert. Insgesamt hat man die Kapitalvermehrung v-(w, N+1) = v(w, N) · (1 - r)
Zieht man zuerst eine weiße Kugel, so gewinnt man den Einsatz: K'(+) = K · (1 - r). Danach wird K'(+) aber gemäß der Kapitalvermehrung v(w-1, N) gesteigert - eine von weißen Kugeln ist ja schon weg! Insgesamt hat man die Kapitalvermehrung v+(w, N+1) = v(w-1, N) · (1 + r)
Da man nicht wissen kann, welche Kugel zuerst kommt, setzt man, um hundertprozentig sicher zu gehen, v-(w, N+1) und v+(w, N+1) gleich, also v(w, N) · (1 - r) = v(w-1, N) · (1 + r).
Somit: r = (v(w, N) - v(w-1, N)) / (v(w, N) + v(w-1, N)) und v(w, N+1) = v(w-1, N) · (1 + r) = 2 · v(w, N) · v(w-1, N) / (v(w, N) + v(w-1, N))
Mit der so erhaltenen Rekursionvorschrift
v(0, N) = 1
v(N, N) = 2^N
v(w, N+1) = 2 · v(w, N) · v(w-1, N) / (v(w, N) + v(w-1, N)) mit 0 < w < N+1
kann man nun nacheinander die Kapitalvermehrung bei gegebenem N zu allen Möglichkeiten für w berechnen, was in der folgenden Tabelle bis N=12 durchgeführt ist.
Die Tabelle ist so zu lesen: Angegeben ist die Kapitalvermehrung v(w; N) als Teiler von 2^N. So beträgt bspw. v(7; 10) = 1024/192 = 16/3
Interessanter Weise ergibt dabei die Summe aus jeweils zwei Einträgen in einer Zeile (Kugelzahl: N) einen neuen Wert in der nächsten Zeile (Kugelzahl: N+1).
Um auf den anfänglichen Faktor r zurückzurechnen, benutzt man bei N+1 Kugeln die oben hergeleitete Formel für r, also bspw. bei (N+1)=10 und w=7 liest man zunächst ab v(6; 9) = 512/142, v(7; 9) = 512/50 und berechnet damit r = (v(7, 9) - v(6, 9)) / (v(7, 9) + v(6, 9)) = (512/50 - 512/142) / (512/50 + 512/142) = 23/48.
Wenn man also zehn Kugeln in der Urne hat, wovon sieben weiß sind, dann setzt man zunächst 23/48 seines Kapitals und erreicht damit, nachdem alle Kugeln gezogen sind, völlig sicher eine Kapitalvermehrung von 1024/192 = 16/3.

\ w |
N \ |   0   1    2    3    4    5    6    7    8    9   10   11   12
----+-----------------------------------------------------------------
1   |   2   1
    |    \  |
    |      \|
2   |   4   3    1
    |    \  | \  |
    |      \|   \|
3   |   8   7    4    1
    |    \  | \  | \  |
    |      \|   \|   \|
4   |  16  15   11    5    1
    |    \  | \  | \  | \  |
    |      \|   \|   \|   \|
5   |  32  31   26   16    6    1
    |    \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|
6   |  64  63   57   42   26    7    1
    |    \  | \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|   \|
7   | 128  127  120  99   68   33    8    1
    |    \  | \  | \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|   \|   \|
8   | 256  255  247  219  167  101  41    9    1
    |    \  | \  | \  | \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|   \|   \|   \|
9   | 512  511  502  466  388  268  142  50   10    1
    |    \  | \  | \  | \  | \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|   \|   \|   \|   \|
10  | 1024 1023 1011 968  854  656  410  192  60   11    1
    |    \  | \  | \  | \  | \  | \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|   \|   \|   \|   \|   \|
11  | 2048 2047 2036 1979 1823 1510 1066 602  252  71   12    1
    |    \  | \  | \  | \  | \  | \  | \  | \  | \  | \  | \  |
    |      \|   \|   \|   \|   \|   \|   \|   \|   \|   \|   \|
12  | 4096 4095 4083 4015 3802 3333 2576 1668 854  323  83   13    1

Ich hege die Vermutung, daß v(N; 2N) gegen 2 geht für große N (Getestet bis N = 1800).