Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Anzahl aller empirischen Verteilungen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Anzahl aller empirischen Verteilungen
mathemufflon2
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 20.04.2021
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-04-20 18:21


Hallo zusammen,

ich arbeite momentan mit dem Buch von Csiszár und Korner, Information Theory: Coding Theorems For Discrete Memoryless Systems.

Darin gibt es eine Übungsaufgabe, bei der ich nicht so recht weiterkomme.
Zwar steht im Titel etwas, was vielleicht auf Statistik schließen lässt, tatsächlich ist es m.M.n. aber ein gänzlich kombinatorisch zu lösendes Problem:

fed-Code einblenden

Letztlich reduziert sich das Problem aus dem Englischen darauf, dass ich die obige Formel für die Anzahl aller mögichen empirischen Verteilungen auf einer Menge mit |X| Elementen zeigen möchte. Dabei ist die ursprüngliche Verteilung Q ja unerheblich.

Ich würde mich sehr freuen, wenn mir hier jemand helfen könnte!

Viele Grüße🤗

Edit:
Meiner Meinung nach ist das so eigentlich gar nicht richtig, wie es oben steht.
Haben wir ein Alphabet von |X| vielen Elementen, dann habe ich je Ziehung |X| Möglichkeiten.
Das heißt, bei k Ziehungen habe ich |X|^k Möglichkeiten.
Jetzt ist für die empirische Verteilung natürlich unerheblich, in welcher Reihenfolge ich die Stichproben gezogen habe, ich teile also durch k! .

Wo ist hier mein Denkfehler? Oder habe ich überhaupt einen?
Ich komme also auf (|X|^k)/k! ...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6815
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-04-20 21:02


$|X|^k/k!$ ist in der Regel nicht ganzzahlig. Das kann nicht die Anzahl der Kombinationen (mit Wiederholungen ohne Berücksichtigung der Reihenfolge) sein. Das liegt daran, dass es nur dann $k!$ verschiedene Kombinationen gibt, die zur selben Verteilung führen, wenn alle $k$ Einträge verschieden sind. Sind z.B. alle gleich, gibt es nur eine Möglichkeit.

Ansonsten ist das die klassische Formel für die Zahl der Kombinationen mit Wiederholungen ohne Berücksichtigung der Reihenfolge siehe hier.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathemufflon2
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 20.04.2021
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-04-21 10:11


Vielen Dank, das hat geholfen. Die Herleitung von der Formel ist ja leider nicht gerade sehr schön. :D



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6815
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-04-21 12:36


Was, das ist doch einer der Glanzpunkte der Kombinatorik. Ich kenne die Herleitung so:

Problem: Du willst aus n Objekten k auswählen, Du darfst das gleiche Objekt auch mehrfach wählen, aber die Reihenfolge spielt keine Rolle. Wie viele Kombinationen gibt es?
Lösung: Ich nehme k Steine und n-1 Stäbe. Diese n-1+k Objekte ordne ich in einer beliebigen Reihenfolge an. Das lässt sich leicht zählen, indem ich mich frage: Welche k Positionen sind durch Steine besetzt? Dafür gibt es fed-Code einblenden Möglichkeiten.
Was hat das mit den Kombinationen mit Wiederholung, ohne Berücksichtigung der Reihenfolge zu tun? -- Die Anzahl der Steine links vom ersten Stab gibt an, wie oft Element 1 gewählt wurde, die Anzahl der Steine zwischen dem ersten und zweiten Stab gibt an, wie oft Element 2 gewählt wurde usw. Die Anzahl der Steine rechts vom letzten Stab gibt schließlich an, wie oft Element n gewählt wurde. Die Bijektion zwischen beiden Mengen ist offensichtlich, daher sind beide Mengen auch gleich mächtig.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]