Reduktion von n Summen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Implementiere folgende Wahrscheinlichkeitsverteilung:
[mm]
P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}}
[/mm]
Ein Vereinfachen der verschachtelten Summen kann dabei hilfreich sein. |
Tachchen,
erst mal vorweg:
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: ![[]](/images/popup.gif) https://dev-community.de/threads/rekursion-vermeiden-abh%C3%A4ngige-summen-laufzeitanalyse.443/
Dort wurde mir dann auch dieses Forum empfohlen. Da es sich hierbei nicht um eine Uni-Aufgabe (eher weiterführendes Interesse) handelt, habe ich mir eine entsprechende Aufgabenformulierung zu dem, was ich erreichen möchte, ausgedacht. Dementsprechend ist auch die angegebene Zeitbegrenzung für dieses Thema irrelevant, da es mich wohl auch noch in nem Jahr aus dem Schlaf reißen wird, wenn ich dieses Ding nicht geknackt bekomm' :P
Mein Problem ist, dass die Anzahl der Summen variabel ist und diese auch noch voneinander abhängen. Leider hab ich keine Idee, wie man das vereinfachen könnte. Als erstes ist mir das Multinomial Theorem in den Sinn gekommen, jedoch funktioniert das nicht, da die Summen nicht alle immer bei [mm]1[/mm] anfangen.
Ich hab das ganze testweise mit Rekursion implementiert, dies ist jedoch viel zu langsam, als dass ich da sinnvoll Daten extrahieren kann.
Zum Kontext: Diese Verteilung beschreibt das Laufzeitverhalten eines Algorithmus, den ich mit einem anderen vergleichen will. Der Algorithmus soll dabei einen einfachen, ungerichteten (und ungewichteten) Graphen erzeugen, mit [mm]N[/mm] Knoten und [mm]M[/mm] zufällig verteilten Verbindungen. [mm]|E|_\text{max} = \frac{N\cdot (N-1)}{2}[/mm] ist dabei die maximale Anzahl an möglichen Verbindungen in einem einfachen, ungerichteten Graphen.
Der entsprechende Algorithmus zieht eine zufällige Verbindung (d.h. zwei zufällige Knoten) und setzt die Verbindung, falls sie noch nicht existiert. Andernfalls wird einfach neu gezogen; das ganze wird wiederholt, bis alle [mm]M[/mm] Verbindungen gesetzt wurden. Dieser Algorithmus wird logischerweise mit einem höheren Verhältnis zwischen [mm] \(M\) [/mm] und [mm] \(N\) [/mm] immer schlechter. Die Frage ist nur "wie schlecht" :) D.h. eigentlich interessiert mich im Endeffekt nur der Erwartungswert der Verteilung.
So, ich hoffe, ich habe euch hier nicht komplett zugetextet ^^ Wenn euch was gescheites einfällt, wäre ich sehr daran interessiert :)
Mfg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:33 Sa 06.11.2021 | | Autor: | felixf |
Moin!
> Implementiere folgende Wahrscheinlichkeitsverteilung:
> [mm]
P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}}
[/mm]
>
> Ein Vereinfachen der verschachtelten Summen kann dabei
> hilfreich sein.
Eine gute Idee das symbolisch zu vereinfachen habe ich nicht, aber ausrechnen kann man das sehr effizient, also solange $n - M$ und $M - 1$ nicht zu gross sind (bis ein paar tausend ist kein Problem). Wobei auch bei so grossen Werten die Zahlen vermutlich schon so stark explodieren, dass die Anzahl der Rechenoperationen das kleinere Problem sind.
Und zwar kannst du dir folgende Teilausdrücke anschauen:
[mm]
T(k, s) := \sum_{i_k=s}^{M-1} i_k \sum_{i_{k+1}=i_k}^{M-1} i_{k+1} \cdots \sum_{i_{n-M}=i_{n-M-1}}^{M-1} i_{n-M}$
[/mm]
mit $1 [mm] \le [/mm] k [mm] \le [/mm] n - M$ und $1 [mm] \le [/mm] s [mm] \le [/mm] M - 1$. Und zwar musst du ausnutzen, dass $T(k, s) = [mm] \sum_{i_k=s}^{M-1} i_k [/mm] T(k + 1, [mm] i_k)$ [/mm] ist.
Zuerst rechnest du in einer Schleife $T(n - M, s)$ für $s = 1, [mm] \dots, [/mm] M - 1$ aus. Das ist einfach, da $T(n - M, s) = s$ ist.
Dann rechnest du in einer Schleife $T(n - M - 1, s)$ für $s = 1, [mm] \dots, [/mm] M - 1$ aus. Dazu brauchst du die $T(n - M, s)$. Die Werte $T(n - m, s)$ kannst du danach wegwerfen, die brauchst du nicht mehr.
Danach rechnest du in einer Schleife $T(n - M - 2, s)$ für $s = 1, [mm] \dots, [/mm] M - 1$ aus. Danach kannst du die Werte $T(n - M - 1, s)$ wegwerfen.
So kämpfst du dich Schritt für Schritt weiter nach vorne, bis du schliesslich aus den $T(2, s)$ die Werte $T(1, s)$, $1 [mm] \le [/mm] s [mm] \le [/mm] M - 1$ ausrechnest. Dann kannst du schliesslich $P( n ) = [mm] \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} [/mm] T(1, 1)$ ausrechnen.
(Also eigentlich bauchst du von den $T(1, s)$ nur $T(1, 1)$ auszurechnen, der Rest kann weg. Aber wenn du genauer hinschaust, kannst du sehen wie du allgemein die $T(k, s)$ für ein festes $k$ schneller ausrechnen kannst, als für jedes $s$ eine Schleife für die Summe zu berechnen... Dann weisst du warum es am einfachsten ist gleich alle davon auszurechnen.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:53 Di 09.11.2021 | | Autor: | lord_haffi |
Moin :)
Danke für deine Antwort, sie war sehr hilfreich! Hab auch schon drüber nachgedacht, wie ich zumindest den Schritt von $P(n) [mm] \rightarrow [/mm] P(n+1)$ bewerkstelligen könnte, da ich eh an der ganzen Verteilung interessiert bin. Hab mich da aber n paar mal selbst verwirrt mit den Summen ^^
Allerdings müsste $ T(n - M, s) = 1 $ sein und nicht $ T(n - M, s) = s $. Sonst hat man für $ T(n - M-1, s) $ die Summanden quadriert.
> (Also eigentlich bauchst du von den [mm]T(1, s)[/mm] nur [mm]T(1, 1)[/mm]
> auszurechnen, der Rest kann weg. Aber wenn du genauer
> hinschaust, kannst du sehen wie du allgemein die [mm]T(k, s)[/mm]
> für ein festes [mm]k[/mm] schneller ausrechnen kannst, als für
> jedes [mm]s[/mm] eine Schleife für die Summe zu berechnen... Dann
> weisst du warum es am einfachsten ist gleich alle davon
> auszurechnen.)
>
> LG Felix
>
Ja ne, die Summe geh ich natürlich von oben nach unten nur einmal durch und summiere den jeweils letzten drauf ;) Für den interessierten Leser: $ T(k, s) = T(k, s+1) + s T(k + 1, s) $
Das hat die Ausführungszeit auf jeden Fall enorm gedrückt :) Das Explodieren der Zahlen hab ich dadurch verhindert, dass ich die $ [mm] |E|_\text{max}^{n-1} [/mm] $ im Nenner so gesplittet habe, dass nun in jeder Iteration einmal durch [mm] $|E|_\text{max}$ [/mm] geteilt wird. Also im Prinzip hab ich's in $ T(k,s) $ reingezogen.
Mfg
|
|
|
|
