www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Ziehen mit Zurücklegen
Ziehen mit Zurücklegen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ziehen mit Zurücklegen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Ziehen mit Zurücklegen: Antwort
Status: (Antwort) fertig Status 
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:

    []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

Bezug
                
Bezug
Ziehen mit Zurücklegen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Ziehen mit Zurücklegen: Danke
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
Ziehen mit Zurücklegen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de