Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Urnenproblem / Variante Geburtstagsproblem
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Urnenproblem / Variante Geburtstagsproblem
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2235
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-03-30


Kann mir jemand einen Tipp geben für eine möglichst effiziente Lösung folgenden Problems:


In einer Urne befinden sich $N = n \cdot k$ Kugeln.

Jeweils $n$ Kugeln sind mit der Zahl $z \in \{0;1;2;\dots;k-1\}$ beschriftet.

Wir ziehen nun ohne Zurücklegen solange, bis zwei der gezogenen Kugeln zusammen den Wert $k$ ergeben.

Gesucht ist der Erwartungswert der benötigten Züge.

Mein erster Ansatz war, den jeweiligen Zustand als Tupel $(N_Z, N_0, N_{k/2}, N_x)$ darzustellen.
$N_Z$: Anzahl gezogener Kugeln
$N_0$: Anzahl gezogener Nullen
$N_{k/2}$: Anzahl gezogener Kugeln mit Wert $\frac{k}{2}$
$N_x$: Anzahl verschiedener Kugeln mit sonstigen Werten

Die Wahrscheinlichkeit dieses Zustand könnte ich dann (rekursiv/dynamisch) aus den Zuständen von $(N_Z-1)$ Zügen berechnen.
Das erscheint allerdings aufwendig, da es durch die Nullen oder Zahlwiederholungen recht viele Zustände gibt.


Wie kann man dieses etwas modifizierte Geburtstagsproblem besser lösen?


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3467
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-04-01


Hallo,

ich habe noch ein paar kleine Probleme mit deinem skizzierten Lösungsansatz.

Du arbeitest mit N_k/2, es kann aber sein, dass k ungerade ist, und die geforderten zwei Kugeln mit Summe k kann man doch auf sehr verschiedene Arten erhalten, zB (k-1) und 1, oder (k-2) und 2, etc.

Ein weniger aufwendiges Verfahren ist da bisher für mich auch nicht zu sehen, ausser eben mit einer Kette von verschiedenen Zuständen zu arbeiten, deren Übergangswahrscheinlichkeit beim Ziehen einer neuen Kugel zu bestimmen (was, da wir ohne zurücklegen arbeiten, etwas komplizierter wird), und dann kann man hoffen, für die Wahrscheinlichkeiten entlang der Kette aus der rekursiven Folge etwas zu gewinnen, das die Wahrscheinlichkeit in Abhängigkeit der Anzahl n der bereits gezogenen Kugeln ergibt.

Ich fürchte allerdings, dass man da nicht wirklich auf etwas "einfaches" kommt... Aber wenn du magst können wir uns dem ja gemeinsam annähern.

Grüße aus dem Harz
Gerhard/Gonz






  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6373
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-04-02


Eine Bemerkung, die das Problem etwas vereinfacht:

Man kann vermutlich die Kugeln mit einer Null komplett ignorieren, sie können nie einer der beiden Summanden sein.
Wenn man ermittelt hat, wie viele Nicht-Nullen man im Mittel ziehen muss, dann kann zusätzlich berechnen, wie viele Nullen man dabei im Mittel "mit gezogen" hat.




  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2235
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-04-02


Danke euch schonmal für die Antworten.

@gonz: $k$ ist in der konkreten Aufgabe (Euler-Project) gerade.

Am Wochenende werde ich mich wohl wieder dransetzen und ein paar Dinge probieren.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  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: 6373
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-04-02


Welche Größenordnungen haben k und n?

Ich habe es für ungerade k in der Größenordnung k=101;n=1000; (ohne Nullen) durchgerechnet.



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