Ziehen mit Zurücklegen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:53 Mi 24.09.2014 | | Autor: | t0m |
Guten Abend,
ich arbeite zur Zeit an einer numerischen Simulation und muss im Rahmen dieser Simulation aus einem Datensatz der Größe [mm] n [/mm] mehrere Stichproben durch Ziehen mit Zurücklegen generieren. Alle Stichproben sollen ebenfalls die Größe [mm] n [/mm] haben. Ich möchte nun über alle möglichen Stichproben, die ich durch Ziehen mit Zurücklegen generieren kann, iterieren. Dies habe ich bereits implementiert und scheint auch zu funktionieren. Allerdings bin ich nicht so bewandert im Gebiet der Kombinatorik und hoffe, dass mir jemand bei der Berechnung der Möglichkeiten helfen. Insgesamt gibt es [mm] n^n [/mm] Möglichkeiten / Stichproben.
Die Generierung einer Stichprobe erfolgt in zwei Schritten.
1. Schritt
Als Punkthäufigkeit bezeichne ich einen Vektor aus der Menge [mm] C := \{ (c_1, ... c_n) \in \IN^n_0 : \summe_{i=1}^{n} c_i = n \} [/mm]. Die Komponente [mm] c_i [/mm] gibt an, wie oft der Datenpunkt [mm] i [/mm] des Datensatzes in der Stichprobe enthalten ist. Und die Menge [mm] C [/mm] beinhaltet alle zulässigen Punkthäufigkeiten, die eine Stichprobe der Größe [mm] n [/mm] beschreiben. Diese wird im ersten Schritt generiert.
2. Schritt
Im zweiten Schritt generiere ich aus einer Punkthäufigkeit eine "Permutation" (mir fehlt ein passendes Wort), indem ich den Datenpunkt [mm] i [/mm] genau [mm] c_i [/mm] mal in der Stichprobe verteile. Es kann sogar über alle "Permutationen" iteriert werden. Mit Hilfe des Binomialkoeffizienten kann ich die Anzahl der "Permutationen" / Stichproben zu einer Punkthäufigkeit berechnen. Sei [mm] c [/mm] eine Punkthäufigkeit, dann gibt es
[mm] {n \choose c_1} * {n-c_1 \choose c_2 } * {n-c_1-c_2 \choose c_3} ... = \prod_{i = 1}^{n} {n - \sum_{k = 1}^{i-1} c_k \choose c_i}[/mm]
viele Möglichkeiten aus der Punkthäufigkeit eine Stichprobe zu generieren. Die Formel lässt sich noch vereinfachen, aber so ist sie intuitiver - hoffe ich.
Wenn ich über alle Punkthäufigkeiten iteriere und die Anzahl der möglichen Stichproben (obige Formel) aufsummiere, erhalte ich die erwarteten [mm] n^n [/mm] Stichproben. Deswegen denke ich, dass der Ansatz so funktioniert.
Nun zu meinem eigentlichen Problem:
(1) Wie groß ist die Menge [mm] C [/mm] und kann ich dies "direkt" berechnen? Momentan kann ich nur darüber iterieren und zählen. Das ist aber irgendwie unbefriedigend. Ein direkter Weg ist mir bis heute noch nicht eingefallen.
(2) Ich bin mir ziemlich sicher, dass ich mit Schritt 1 nicht das Rad neu erfunden habe. Gibt es dafür in der Kombinatorik oder einen anderem Gebiet einen Fachbegriff? Dann könnte ich mich selber schlau machen und vielleicht so auf eine Lösung kommen.
Schon mal im Voraus vielen Dank für die Hilfe
Thomas
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:53 Mi 24.09.2014 | | Autor: | Marcel |
Hallo Tom,
> Guten Abend,
>
> ich arbeite zur Zeit an einer numerischen Simulation und
> muss im Rahmen dieser Simulation aus einem Datensatz der
> Größe [mm]n[/mm] mehrere Stichproben durch Ziehen mit Zurücklegen
> generieren. Alle Stichproben sollen ebenfalls die Größe [mm]n[/mm]
> haben. Ich möchte nun über alle möglichen Stichproben,
> die ich durch Ziehen mit Zurücklegen generieren kann,
> iterieren. Dies habe ich bereits implementiert und scheint
> auch zu funktionieren. Allerdings bin ich nicht so
> bewandert im Gebiet der Kombinatorik und hoffe, dass mir
> jemand bei der Berechnung der Möglichkeiten helfen.
> Insgesamt gibt es [mm]n^n[/mm] Möglichkeiten / Stichproben.
>
> Die Generierung einer Stichprobe erfolgt in zwei
> Schritten.
>
> 1. Schritt
> Als Punkthäufigkeit bezeichne ich einen Vektor aus der
> Menge [mm]C := \{ (c_1, ... c_n) \in \IN^n_0 : \summe_{i=1}^{n} c_i = n \} [/mm].
> Die Komponente [mm]c_i[/mm] gibt an, wie oft der Datenpunkt [mm]i[/mm] des
> Datensatzes in der Stichprobe enthalten ist. Und die Menge
> [mm]C[/mm] beinhaltet alle zulässigen Punkthäufigkeiten, die eine
> Stichprobe der Größe [mm]n[/mm] beschreiben. Diese wird im ersten
> Schritt generiert.
>
> 2. Schritt
> Im zweiten Schritt generiere ich aus einer
> Punkthäufigkeit eine "Permutation" (mir fehlt ein
> passendes Wort), indem ich den Datenpunkt [mm]i[/mm] genau [mm]c_i[/mm] mal
> in der Stichprobe verteile. Es kann sogar über alle
> "Permutationen" iteriert werden. Mit Hilfe des
> Binomialkoeffizienten kann ich die Anzahl der
> "Permutationen" / Stichproben zu einer Punkthäufigkeit
> berechnen. Sei [mm]c[/mm] eine Punkthäufigkeit, dann gibt es
>
> [mm]{n \choose c_1} * {n-c_1 \choose c_2 } * {n-c_1-c_2 \choose c_3} ... = \prod_{i = 1}^{n} {n - \sum_{k = 1}^{i-1} c_k \choose c_i}[/mm]
>
> viele Möglichkeiten aus der Punkthäufigkeit eine
> Stichprobe zu generieren. Die Formel lässt sich noch
> vereinfachen, aber so ist sie intuitiver - hoffe ich.
>
> Wenn ich über alle Punkthäufigkeiten iteriere und die
> Anzahl der möglichen Stichproben (obige Formel)
> aufsummiere, erhalte ich die erwarteten [mm]n^n[/mm] Stichproben.
> Deswegen denke ich, dass der Ansatz so funktioniert.
>
>
> Nun zu meinem eigentlichen Problem:
>
> (1) Wie groß ist die Menge [mm]C[/mm] und kann ich dies "direkt"
> berechnen? Momentan kann ich nur darüber iterieren und
> zählen. Das ist aber irgendwie unbefriedigend. Ein
> direkter Weg ist mir bis heute noch nicht eingefallen.
>
> (2) Ich bin mir ziemlich sicher, dass ich mit Schritt 1
> nicht das Rad neu erfunden habe. Gibt es dafür in der
> Kombinatorik oder einen anderem Gebiet einen Fachbegriff?
sofern ich mich nicht täusche, siehe:
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Kombination_%28Kombinatorik%29#Mengendarstellung_2
Deine Menge [mm] $C\,$ [/mm] ist demnach
die „Menge aller Kombinationen mit Wiederholung von [mm] $n\,$ [/mm] Objekten
zur Klasse [mm] $n\,$“.
[/mm]
Demnach sollte sie
$|C|={n+n-1 [mm] \choose [/mm] n}={2n-1 [mm] \choose [/mm] n}$
Elemente haben. Kannst Du das mal überprüfen? (Für [mm] $n=1,2,3,4,5\,.$)
[/mm]
P.S.
[mm] $\{ (c_1, ... c_n) \in \IN^n_0 : \summe_{i=1}^{n} c_i = n \}=\{ (c_1, ... c_n) \in \{0,\ldots,n\}^n : \summe_{i=1}^{n} c_i = n \}$
[/mm]
solltest Du Dir dafür noch klarmachen.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:06 Do 25.09.2014 | | Autor: | Marcel |
Hallo nochmal,
ich finde den erwähnten Begriff der
Multimenge,
der in letztem Link auch erwähnt wird, durchaus beachtenswert.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:00 Do 25.09.2014 | | Autor: | t0m |
Guten Morgen Marcel,
für kleine [mm] n [/mm] habe ich es kurz überprüft und die Anzahl der Iterationen in meinem Programm deckt sich mit der Theorie von dir. Ich kann nur vielen herzlichen Dank sagen. Damit weiß ich jetzt, dass mein Algorithmus funktioniert (funktionieren sollte).
Die beiden Artikel habe ich schon gelesen und genau das habe ich gesucht. Nochmals Danke. Du hast mir sehr weiter geholfen. Die Herleitungen und Beweise werde ich mir die nächsten Tage ansehen. Ich stürze mich jetzt wieder auf meine Simulation.
Viele Grüße
Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Do 25.09.2014 | | Autor: | Marcel |
Hallo,
> Guten Morgen Marcel,
>
> für kleine [mm]n[/mm] habe ich es kurz überprüft und die Anzahl
> der Iterationen in meinem Programm deckt sich mit der
> Theorie von dir.
die Theorie habe ich nicht erfunden, und aus der Kombinatorik ist das
eigentlich, was das Urnenmodell betrifft, auch die einzige Formel, die
ich nicht auf die schnelle herleiten kann (und die Herleitung, die ich mal
gesehen habe, hatte schon einige *Knackpunkte*, wie ich finde; ich hatte
jedenfalls schon etwas gebraucht, um manche Argumente zu verstehen).
Aber ich sah, dass Du ja eigentlich genau das machst; und wenn Du das
damit meinst, dass meine Theorie korrekt sei: Okay. 
> Ich kann nur vielen herzlichen Dank sagen.
> Damit weiß ich jetzt, dass mein Algorithmus funktioniert
> (funktionieren sollte).
Wenn er (fundamental) falsch wäre, wäre jedenfalls zu erwarten, dass sich
das bei einfachen Tests auch schon irgendwann zeigt. 
> Die beiden Artikel habe ich schon gelesen und genau das
> habe ich gesucht. Nochmals Danke. Du hast mir sehr weiter
> geholfen. Die Herleitungen und Beweise werde ich mir die
> nächsten Tage ansehen. Ich stürze mich jetzt wieder auf
> meine Simulation.
Klar. Das ist ja auch Dein Hauptaugenmerk.
Gruß,
Marcel
|
|
|
|
