Urnenproblem mit zurücklegen < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 05:48 Mo 10.08.2009 | | Autor: | wurgel |
| Aufgabe | Gegeben sei eine Urne mit 100 unterschiedlichen Kugeln.
Wie oft muss man eine Kugel ziehen und zurücklegen, um mit >= 80% Wahrscheinlichkeit 4 Kugeln jeder Art zu ziehen? |
Mein Problem liegt eigentlich nur in den 4 Kugeln jeder Art.
Die Permutationen für 4 Kugeln einer Art zu bekommen ist kein Problem. Nur bekomme ich irgendwie dens chritt von 4 Kugeln einer Art zu 4 Kugeln jeder Art nicht hin, ohne Permutationen doppelt zu zählen.
und aufgrund der größe der Zahlen lässen sich alle Permutationen leider nicht per hand aufschreiben und auswerten
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Da fehlen Angaben zur Lösung: "Kugeln jeder Art", was meinst du damit? Oder soll jede Kugel eine eigene Art bezeichnen? Dann hätte man doch aber sicher formuliert: "um mit ... jede Kugel mindestens 4mal zu ziehen".
???
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:21 Mo 10.08.2009 | | Autor: | abakus |
> Da fehlen Angaben zur Lösung: "Kugeln jeder Art", was
> meinst du damit? Oder soll jede Kugel eine eigene Art
> bezeichnen? Dann hätte man doch aber sicher formuliert:
> "um mit ... jede Kugel mindestens 4mal zu ziehen".
>
> ???
Hallo,
im Text steht sicher noch so etwas wie "von den 100 Kugeln sind 30 blau, 25 rot ...."
Lies nochmal nach.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:40 Mo 10.08.2009 | | Autor: | rabilein1 |
Um mich auch am Spökenkieken zu beteiligen:
Die Kugeln sind alle verschieden. Da sie aber wieder zurück gelegt werden, kann man auch eine Kugel vier Mal ziehen.
Frage:
Wie oft muss man ziehen, um mit 80%iger Wahrscheinlichkeit mindestens eine Kugel vier Mal gezogen zu haben?
Übirgens:
Die Frage "Wie oft muss man ziehen, um mit 100%iger Wahrscheinlichkeit mindestens eine Kugel vier Mal gezogen zu haben?" lässt sich sehr leicht beantworten....
(Jede der 100 Kugeln wurde genau drei Mal gezogen = 300 Ziehungen. Mit der 301sten Ziehung hat man dann garantiert eine Kugel vier Mal gezogen)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:18 Mo 10.08.2009 | | Autor: | wurgel |
> Um mich auch am Spökenkieken zu beteiligen:
>
> Die Kugeln sind alle verschieden. Da sie aber wieder
> zurück gelegt werden, kann man auch eine Kugel vier Mal
> ziehen.
>
> Frage:
> Wie oft muss man ziehen, um mit 80%iger Wahrscheinlichkeit
> mindestens eine Kugel vier Mal gezogen zu haben?
>
> Übirgens:
> Die Frage "Wie oft muss man ziehen, um mit 100%iger
> Wahrscheinlichkeit mindestens eine Kugel vier Mal gezogen
> zu haben?" lässt sich sehr leicht beantworten....
> (Jede der 100 Kugeln wurde genau drei Mal gezogen = 300
> Ziehungen. Mit der 301sten Ziehung hat man dann garantiert
> eine Kugel vier Mal gezogen)
Das Triffts genau. Es sind hundert verschiedene Kugeln. (zur verständniss: kugeln mit den Nummern 1-100)
Das problem ist hallt, dass JEDE Kugel 4 mal gezogen werden soll und nicht nur eine.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:24 Mo 10.08.2009 | | Autor: | abakus |
> > Um mich auch am Spökenkieken zu beteiligen:
> >
> > Die Kugeln sind alle verschieden. Da sie aber wieder
> > zurück gelegt werden, kann man auch eine Kugel vier Mal
> > ziehen.
> >
> > Frage:
> > Wie oft muss man ziehen, um mit 80%iger
> Wahrscheinlichkeit
> > mindestens eine Kugel vier Mal gezogen zu haben?
> >
> > Übirgens:
> > Die Frage "Wie oft muss man ziehen, um mit 100%iger
> > Wahrscheinlichkeit mindestens eine Kugel vier Mal gezogen
> > zu haben?" lässt sich sehr leicht beantworten....
> > (Jede der 100 Kugeln wurde genau drei Mal gezogen = 300
> > Ziehungen. Mit der 301sten Ziehung hat man dann garantiert
> > eine Kugel vier Mal gezogen)
>
> Das Triffts genau. Es sind hundert verschiedene Kugeln.
> (zur verständniss: kugeln mit den Nummern 1-100)
>
> Das problem ist hallt, dass JEDE Kugel 4 mal gezogen werden
> soll und nicht nur eine.
Wenn du ein ganz großer Pechvogel bist, ziehst du immer wieder die Kugel Nr. 23 und die anderen nie.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:39 Mo 10.08.2009 | | Autor: | statler |
> Wenn du ein ganz großer Pechvogel bist, ziehst du immer
> wieder die Kugel Nr. 23 und die anderen nie.
Was aber nichts macht, denn dieser Fall gehört zu denen mit 20 % Wahrscheinlichkeit.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:43 Mo 10.08.2009 | | Autor: | wurgel |
Das ist klar. Daher ist keine 100%ige chance möglich. Darum ja auch die 80%+ chance auf mindestens 4 Kugeln jeder "Art". Je öfter man zieht, um so höher wird ja die Chance, das geünschte ergebnis zu erhalten.
Um das auszurechnen (über kombinatorik) bräuchte ich hallt die zahlenkombinationen, die nicht zum gewünschten ergebnis führen. Leider bekomme ich die nur für einzelne zahlen hin und kann diese ergebnisse nicht zusammenführen, weil dann kombinationen doppelt vorkommen.
z.B. für die Kugeln mit einer 1 ist eine Kombination 2,2,2,2......,2
Diese ist allerdings auch bei den kombinationen für 3-100 dabei.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:39 Mo 10.08.2009 | | Autor: | rabilein1 |
> Das Triffts genau. Es sind hundert verschiedene Kugeln.
> (zur verständniss: kugeln mit den Nummern 1-100)
>
> Das problem ist hallt, dass JEDE Kugel 4 mal gezogen werden
> soll und nicht nur eine.
Ich stelle mir die Vorgehensweise so vor:
Gesucht ist x (die Zahl der Ziehungen)
Kannst du die Wahrscheinlichkeit p ausrechnen, mit der die Kugel mit der Nummer 1 bei x Versuchen mindestens vier mal gezogen wird?
Die selbe Wahrscheinlichkeit trifft ja auch auf alle anderen 99 Kugeln zu.
Also ist die Wahrscheinlichkeit, dass alle 100 Kugeln mindestens vier Mal gezogen werden = [mm] p^{100} [/mm]
Und dieses [mm] p^{100} [/mm] soll mehr als 0.8 ergeben
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:05 Di 11.08.2009 | | Autor: | wurgel |
> Ich stelle mir die Vorgehensweise so vor:
>
> Gesucht ist x (die Zahl der Ziehungen)
>
> Kannst du die Wahrscheinlichkeit p ausrechnen, mit der die
> Kugel mit der Nummer 1 bei x Versuchen mindestens vier mal
> gezogen wird?
>
> Die selbe Wahrscheinlichkeit trifft ja auch auf alle
> anderen 99 Kugeln zu.
>
> Also ist die Wahrscheinlichkeit, dass alle 100 Kugeln
> mindestens vier Mal gezogen werden = [mm]p^{100}[/mm]
>
> Und dieses [mm]p^{100}[/mm] soll mehr als 0.8 ergeben
>
>
Das währe die wahrscheinlichkeit in 100 spielen hintereinander 4 mal die Kugel zu ziehen.
davon abgesehen würde man so eine Wahrscheilichteit > 0% erhalten, jede Kugel mind 4 mal zu ziehen, mit einer Ziehanzahl von unter 400
müsste es da nicht eher so sein:
Wahrscheinlichkeit 4 gleiche zu ziehen * wahrscheinlichkeit 4 gleiche zu ziehen bei 4 mal ziehen weniger*..... * wahrscheinlichkeit 4 gleiche zu ziehen bei 396 mal ziehen weniger ?
|
|
|
| |
|
> > Ich stelle mir die Vorgehensweise so vor:
> >
> > Gesucht ist x (die Zahl der Ziehungen)
> >
> > Kannst du die Wahrscheinlichkeit p ausrechnen, mit der die
> > Kugel mit der Nummer 1 bei x Versuchen mindestens vier mal
> > gezogen wird?
> >
> > Die selbe Wahrscheinlichkeit trifft ja auch auf alle
> > anderen 99 Kugeln zu.
> >
> > Also ist die Wahrscheinlichkeit, dass alle 100 Kugeln
> > mindestens vier Mal gezogen werden = [mm]p^{100}[/mm] ![[notok]](/images/smileys/notok.gif "[notok]")
Das Problem ist, dass diese Ereignisse nicht unabhängig
voneinander sind !
> > Und dieses [mm]p^{100}[/mm] soll mehr als 0.8 ergeben
> Das wäre die Wahrscheinlichkeit in 100 Spielen
> hintereinander 4 mal die Kugel zu ziehen. ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
Da komm' ich nicht mit ...
> davon abgesehen würde man so eine Wahrscheilichkeit > 0%
> erhalten, jede Kugel mind 4 mal zu ziehen, mit einer
> Ziehanzahl von unter 400
???
> müsste es da nicht eher so sein:
> Wahrscheinlichkeit 4 gleiche zu ziehen *
> wahrscheinlichkeit 4 gleiche zu ziehen bei 4 mal ziehen
> weniger*..... * wahrscheinlichkeit 4 gleiche zu ziehen bei
> 396 mal ziehen weniger ?
Ich bin nicht so sicher, dass wir eine zutreffende
Formulierung der Fragestellung haben. Nach meiner
Auffassung würde das bisher Gesagte der Aufgabe
entsprechen:
Es werden nacheinander n Zufallszahlen [mm] a_1,a_2,\,.....\,a_n [/mm]
aus der Grundmenge [mm] G=\{0,1,2,\,.....\,98,99\} [/mm] gezogen
(Gleichverteilung; p=1/100 für jede einzelne Zahl
im einzelnen Zug). Wie gross muss n mindestens sein,
damit die Wahrscheinlichkeit dafür, dass jedes der
100 Elemente von G mindestens vier mal in der Folge
[mm] [/mm] vorkommt, mindestens 0.8 beträgt ?
Falls diese Interpretation korrekt ist, ist die
Aufgabe wohl kaum durch die einfache Anwendung
einer simplen bekannten Formel zu lösen.
Ich habe aber noch gewisse Zweifel, ob die Aufgabe
wirklich so gemeint war. Deshalb ist auch meine Lust,
mich in die entsprechenden Rechnungen zu stürzen,
bei vorgerückter Stunde eher gering ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:45 Di 11.08.2009 | | Autor: | rabilein1 |
> > > Also ist die Wahrscheinlichkeit, dass alle 100 Kugeln
> > > mindestens vier Mal gezogen werden = [mm]p^{100}[/mm]
>
> Das Problem ist, dass diese Ereignisse nicht unabhängig
> voneinander sind !
Da hast du völlig Recht.
Aber: Die Frage ist doch: Spielt das bei dieser Größenordnung überhaupt eine Rolle?
>
>
> Falls diese Interpretation korrekt ist, ist die
> Aufgabe wohl kaum durch die einfache Anwendung
> einer simplen bekannten Formel zu lösen.
Richtig. Es wird nicht einfach, und man muss Kompromisse eingehen. Aber ich will mich dem Ergebnis auch nur asymptotisch nähern.
Und dann habe ich raus, dass es etwa 433 Ziehungen sein müssen.
Meine endgültige Formel dafür ist recht kompliziert, aber jede einzelne Komponente ist nachvollziehbar:
[mm] 0.99^{x}*(x-1)^{3} [/mm] = [mm] \bruch{(1-e^{(\bruch{ln0.8}{100})})*3!}{0.01^{3}}
[/mm]
Grob erklärt:
Ich bin so vorgegangen, wie ich es eingangs beschrieben hatte. Also habe ich die Wahrscheinlichkeit ausgerechnet, dass Kugel 1 mindestens 4 Mal gezogen wird.
Mein Kompromiss im linken Teil der Formel (damit diese nicht noch komplizierter wird): Ich berücksichtige nur, dass die Kugeln nicht genau drei Mal gezogen werden (weil 0 bis 2 Mal sehr unwahrscheinlich ist)
Und das [mm] (x-1)^{3} [/mm] müsste eigentlich lauten x*(x-1)*(x-2).
Aber macht das den Kohl fett?
|
|
|
| |
|
Hallo,
ich habe nun auch einen Rechenversuch gestartet,
wobei ich einmal so tue (obwohl mir das nicht so
ganz koscher scheint) als ob es nicht viel ausmache
wenn man setzt:
$\ P(jede\ Kugel\ mind.\ 4\ Mal)\ [mm] \approx\ (\underbrace{P(Kugel\ Nr.\,1\ mind.\ 4\ Mal)}_{p})^{100}$
[/mm]
Für p habe ich:
$\ p\ =\ [mm] 1-S_n\ [/mm] =\ [mm] 1-\summe_{k=0}^{3}\vektor{n\\k}*0.01^k*0.99^{n-k}$
[/mm]
Dann habe ich den Term [mm] S_n [/mm] entwickelt und kam auf
$\ [mm] S_n\ [/mm] =\ [mm] \frac{1}{6}*0.99^{\,n-3}*\left[\,n^3+294\,n^2+58511\,n+5821794\,\right]$
[/mm]
(Mathematica bestätigte meine Handrechnung)
Dann geht es darum, die Ungleichung
[mm] $(1-S)^{100}\ge [/mm] 0.8$
aufzulösen. Dies führt auf [mm] S\le0.0022289477
[/mm]
Die Gleichung $\ [mm] S_n=0.0022289477$ [/mm] löst zwar
der Solve-Befehl von Mathematica nicht auf,
aber durch Probieren kam ich dann darauf,
dass obige Ungleichung für n=1200 erfüllt
ist, aber für n=1199 noch nicht.
Dies ist ein deutlich anderes Ergebnis als das
(433 Ziehungen) von rabilein - jetzt wären wir
froh, wenn jemand die Aufgabe übernähme, die
Rechnungen zu überprüfen. 433 erscheint mir
aber "vom Schiff aus betrachtet" doch irgendwie
zu klein, denn dies liegt ja doch noch sehr nahe
bei der äusserst unwahrscheinlichen "Idealver-
teilung", wo jede Kugel genau 4 mal gezogen wird.
Ich werde nun versuchen, mittels einer Computer-
Simulation der richtigen Lösung auf die Spur
zu kommen.
LG Al-Chwarizmi
|
|
|
| |
|
Hallo Leute,
ich habe nun ein Pascal-Programm erstellt, das
die Ziehungen simuliert. Man kann darin die
Anzahl n der Ziehungen pro Lauf als Konstante
eingeben (im Programmtext). Ebenso setzt man
die Anzahl "Laeufe" der Ziehungsserien fest.
Mit n=1200 und Laeufe=100 werden also 100
Serien zu je 1200 Zufallszahlen aus [mm] $\{1,2,3,\,.....\,100\}$ [/mm]
gebildet und dann gezählt, in wievielen (z) dieser
Läufe jede Zahl aus [mm] $\{1,2,3,\,.....\,100\}$ [/mm] mindestens 4 Mal
aufgetreten ist.
In einigen Versuchen mit Laeufe=100 erhielt
ich die Ergebnisse
$\ 80,80,73,84,81,76,72,81,82,81$
Im einzigen durchgeführten Versuch mit 10000
Laeufen kam ich (wohl mit ein wenig Glück) auf
$\ 8001$
also sehr ekakt auf 0.8 für die relative Häu-
figkeit.
Mit n=433 erhalte ich eine blanke Null für
die relative Häufigkeit, mit n=800 noch
weniger als 1 Prozent. Mit n=1180 entstand
(mit jeweils 5000 Läufen) etwa 0.77, mit
n=1220 etwa 0.83, beide Werte schon deutlich
von 0.8 entfernt, der eine zu klein, der andere
zu groß. Offensichtlich war also die Vermutung,
dass man näherungsweise Unabhängigkeit an-
nehmen könne, obwohl sie eigentlich überhaupt
nicht gegeben ist, ganz akzeptabel. Die Lösung
für die Mindestzahl der Ziehungen liegt in der
Nähe von 1200. Auf einen ganz exakten Wert
möchte ich mich aber nicht festlegen, weil
eben die Argumentation nicht wirklich exakt
ist.
LG Al-Chwarizmi
Und hier noch das Programm:
PROGRAM Urne100;
const n=1200;laeufe=100;
var a:array[1..100] of integer;
i,k,r,z,lauf: integer;
ok: boolean;
BEGIN
z:=0;
for lauf:=1 to laeufe do
begin
for i:=1 to 100 do a[i]:=0;
for k:=1 to n do
begin
r:=urandom1n(100);
a[r]:=a[r]+1
end;
ok:=true;
i:=0;
while ok and (i<100) do
begin
i:=i+1;
if a[i]<4 then ok:=false
end;
if ok then
begin
write('+');
z:=z+1
end
else write('-');
end;
writeln;writeln;
writeln(z:3)
END.
Dateianhänge:
Anhang Nr. 1 (Typ: unbekannt) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:12 Mi 12.08.2009 | | Autor: | rabilein1 |
Mal unsere Interpretation der Aufgabe als richtig vorausgesetzt:
Da sowohl deine Formel als auch die Simulation ergeben hat, dass man etwa 1200 Ziehungen braucht, um mit 80%iger Wahrscheinlichkeit jede der 100 Kugeln mindestens vier Mal gezogen zu haben, sollten wir davon ausgehen, dass das so richtig ist.
Mit meiner Formel käme ich zwar auf nur 1162 Ziehungen, aber da hatte ich bewusst vereinfacht (indem ich sagte: mit 80%iger Wahrscheinlichkeit darf keine der Kugeln genau drei Mal gezogen werden)
|
|
|
| |
|
Hmm... also ich hab auch mal eine Simulation in C++ geschrieben, aber ich komme auf ein anderes Ergebnis...
Ich bin sehr unerfahren in solchen Simulationen, und das Programm ist auch sehr umständlcih geschrieben (aber gut nachvollziehbar^^)
ich komme auf 550 nötige Ziehungen, damit zu 80% Wahrscheinlichkeit alle Kugeln 4mal erwischt wurden.
Und so unwahrscheinlich finde ich das gar nicht, denn selbst der Idealfall von 400 Zügen ist gar nicht so unwahrscheinlich wie man denkt...
und da klingt 550 gar nicht mal so schlimm, oder hab ich da n riesen Denkfehler drinne!
Hier ist der Quellcode:
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
int n;
cin >> n;
vector <int> vec(100);
for (int k=0; k<100; k++)
vec[k] = 0;
srand ( time(NULL) );
int zufall;
for (int i=0; i<n; i++)
{
zufall = rand() % 100 + 1;
if( vec[zufall - 1] < 5)
vec[zufall - 1]++;
}
vector <bool> ok(100);
for (k=0; k<100; k++)
if (vec[k] > 3) ok[k]=true;
int summe = 0;
for (k=0; k<100; k++)
if (ok[k]) summe++;
cout << summe;
return 0;
}
lg Kai
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:15 Di 11.08.2009 | | Autor: | rabilein1 |
> [mm]\ p\ =\ 1-S_n\ =\ 1-\summe_{k=0}^{3}\vektor{n\\k}*0.01^k*0.99^{n-k}[/mm]
Das war mir schon klar, dass dieses die "richtige" Formel ist.
Dann hatte ich die Summe der "Einfachheit halber" umgewandelt auf:
[mm] \vektor{n\\3}*0.01^3*0.99^{n-3} \Leftarrow [/mm] hatte also 0 , 1 und 2 Treffer weggelassen.
War das der entscheidende Fehler ???
Du könntest mit deinem Simulations-Programm mal prüfen, welches Ergebnis man bekäme, wenn man unterscheidet zwischen 0,1,2,4,5 etc. Treffern einerseits und exakt 3 Treffern andererseits (Keine der Zahlen darf genau 3 Treffer aufweisen).
P.S.
Bei solchen Aufgaben/Problemen führen Simulations-Programme im allgemeinen schneller zum Ziel als endloses Überlegen und Rechnen.
|
|
|
| |
|
>
> > [mm]\ p\ =\ 1-S_n\ =\ 1-\summe_{k=0}^{3}\vektor{n\\k}*0.01^k*0.99^{n-k}[/mm]
>
> Das war mir schon klar, dass dieses die "richtige" Formel
> ist.
>
> Dann hatte ich die Summe der "Einfachheit halber"
> umgewandelt auf:
>
> [mm]\vektor{n\\3}*0.01^3*0.99^{n-3} \Leftarrow[/mm] hatte also 0 ,
> 1 und 2 Treffer weggelassen.
>
> War das der entscheidende Fehler ???
> Du könntest mit deinem Simulations-Programm mal prüfen,
> welches Ergebnis man bekäme, wenn man unterscheidet
> zwischen 0,1,2,4,5 etc. Treffern einerseits und exakt 3
> Treffern andererseits (Keine der Zahlen darf genau 3
> Treffer aufweisen).
Hallo rabilein,
das habe ich soeben durchgeführt, habe also in
meinem Programm die Zeile
if a[i]<4 then ok:=false
ersetzt durch
if a[i]=3 then ok:=false
Es zeigt sich, dass sich dann das kritische n
von 1200 etwa zu 1164 verschiebt. Der Haupt-
fehler in deiner Rechnung muss also anderswo
liegen !
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:16 Di 11.08.2009 | | Autor: | rabilein1 |
> Es zeigt sich, dass sich dann das kritische n
> von 1200 etwa zu 1164 verschiebt. Der Haupt-
> fehler in deiner Rechnung muss also anderswo
> liegen !
Also haben meine "Vereinfachungen" (Nichtbeachten der Abhängig und der Summe) zu keiner allzu wesentlichen Verschiebung geführt.
Aber mir fällt auf: [mm] 0.99^{1164}*1163^{3} [/mm] = 13064
So eine ungefähre Zahl (um die 13373) kommt auch auf der anderen Seite meiner Formel raus... Wie kam ich da nur auf die 433 ???
|
|
|
| |
|
> > Es zeigt sich, dass sich dann das kritische n
> > von 1200 etwa zu 1164 verschiebt. Der Haupt-
> > fehler in deiner Rechnung muss also anderswo
> > liegen !
>
> Also haben meine "Vereinfachungen" (Nichtbeachten der
> Abhängig und der Summe) zu keiner allzu wesentlichen
> Verschiebung geführt.
> ......
> Wie kam ich da nur auf die 433 ???
Das müsstest du selber am ehesten herausfinden
können 
Ich habe deine Gleichung nochmals angeschaut
und etwas umgeformt:
[mm] $0.99^x*(x-1)^3\ [/mm] =\ [mm] 6'000'000\,a$
[/mm]
wobei $\ [mm] a=1-e^{ln(0.8)/100}$
[/mm]
Diese Gleichung hat eine Lösung zwischen
1160 und 1161.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:26 Mi 12.08.2009 | | Autor: | wauwau |
Sei [mm] ^ka_{s,n} [/mm] die Anzahl bei n Ziehungen aus k Kugeln mindestens jede Kugel s mal gezogen zu haben.
Gesucht ist in dieser Aufgabe: [mm] \bruch{^{100}a_{4,n}}{100^n}
[/mm]
Jetzt gilt ja:
[mm]^ka_{s,n} = 0 , n
und
[mm] ^ka_{2,n} [/mm] = [mm] \summe_{i=k}^{n}^ka_{1,i}*^ka_{1,N-i}
[/mm]
und allgemein
[mm] ^ka_{2r,n} [/mm] = [mm] \summe_{i=rk}^{n}^ka_{r,i}*^ka_{r,N-i}
[/mm]
Naja das würde sich, würde man [mm] ^ka_{1,n} [/mm] kennen, was auch schon schwierig ist, doch für numerische Auswertungen halbwegs eignen
oder??
|
|
|
| |
|
> Sei [mm]^ka_{s,n}[/mm] die Anzahl bei n Ziehungen aus k Kugeln
> mindestens jede Kugel s mal gezogen zu haben.
Etwas deutlicher:
Sei [mm]^ka_{s,n}[/mm] die Anzahl der Variationen
(Wiederholungen erlaubt) der Länge n
aus der Grundmenge [mm] K=\{1,2,\,.....\,,k\} [/mm] , in
welchen jedes der k Elemente von K
mindestens s Mal vorkommt.
> Gesucht ist in dieser Aufgabe:
> [mm]\bruch{^{100}a_{4,n}}{100^n}[/mm]
>
> Jetzt gilt ja:
>
> [mm]^ka_{s,n} = 0 , n
>
> und
>
> [mm]^ka_{2,n}[/mm] = [mm]\summe_{i=k}^{n}^ka_{1,i}*^ka_{1,N-i}[/mm]
>
> und allgemein
>
> [mm]^ka_{2r,n}[/mm] = [mm]\summe_{i=rk}^{n}^ka_{r,i}*^ka_{r,N-i}[/mm]
>
> Naja das würde sich, würde man [mm]^ka_{1,n}[/mm] kennen, was auch
> schon schwierig ist, doch für numerische Auswertungen
> halbwegs eignen
> oder??
Wow wauwau,
danke für deinen Anstoß. Ich habe mir zwar deine
Formeln noch nicht im Detail klar gemacht, aber
mich gleich auf die Frage nach [mm]^ka_{1,n}[/mm] verlegt,
zunächst einmal am Beispiel mit k=4 und n=7.
Die gesamte Anzahl der Variationen ist in diesem
Fall
[mm] \overline{V}_{4,7}=4^7=16'384
[/mm]
Ich teile die Menge dieser Variationen auf in
jene, die aus genau j Elementen bestehen,
wobei [mm] j\in\{1,2,3,4\} [/mm] . Die Anzahl der Variationen
mit genau j unterschiedlichen Elementen sei [mm] m_j [/mm] .
Dann ist in diesem Beispiel:
[mm] $m_1\ [/mm] =\ [mm] \vektor{4\\1}*1^7\ [/mm] =\ 4$
[mm] $\red{m_2\ =\ \vektor{4\\2}*2^7-m_1\ =\ 768-4\ =\ 764}$
[/mm]
[mm] $\red{m_3\ =\ \vektor{4\\3}*3^7-m_2-m_1\ =\ \vektor{4\\3}*3^7-\vektor{4\\2}*2^7=7'980}$
[/mm]
[mm] $\red{m_4\ =\ \vektor{4\\4}*4^7-\vektor{4\\3}*3^7\ =\ 7'636}$
[/mm]
Siehe die Korrektur weiter unten !
Letzteres ist genau die gesuchte Anzahl der
Variationen, welche jedes der 4 Elemente
wenigstens einmal enthalten, also:
$\ [mm] ^4a_{1,7}\ [/mm] =\ [mm] \vektor{4\\4}*4^7-\vektor{4\\3}*3^7=\ 4^7-4*3^7\ [/mm] =\ 7'636$
Die Verallgemeinerung für beliebige k und n
müsste also lauten:
$\ [mm] ^ka_{1,n}\ [/mm] =\ [mm] \vektor{k\\k}*k^n-\vektor{k\\k-1}*(k-1)^n\ [/mm] =\ [mm] k^n-k*(k-1)^n$
[/mm]
Nun befürchte ich aber allerdings, dass eine
numerische Auswertung so ihre Tücken haben
könnte. Mit k=100 und n=1200 hat man
zum Beispiel:
$\ [mm] ^{100}a_{1,1200}\ [/mm] =\ [mm] 100^{1200}-100*99^{1200}$
[/mm]
Mit derartigen Zahlen ist jeder gewöhnliche
Arithmetik-Prozessor hoffnungslos überfordert.
Mathematica liefert aber trotzdem im Nu eine
2400-stellige Zahl (ungefähr ein A5-Blatt voll).
Vielleicht werde ich es also mit Mathematica
versuchen, auf eine exakte Lösung der gestellten
Urnen-Aufgabe zu kommen.
Bevor ich aber dran gehe: könntest du deine
Rekursionsformeln doch noch erläutern ?
Reichen sie - mit meiner obigen Formel
zusammen - wirklich aus ?
LG Al
Korrektur:
Die oben rot dargestellten Formeln können nicht
stimmen, wie eine Überprüfung durch Berechnung
aller 16384 Variationen ergeben hat.
Ich habe aber leider noch nicht gemerkt, wo mein
Überlegungsfehler steckt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:57 Mi 12.08.2009 | | Autor: | wauwau |
1. Deine Formel für [mm] ^ka_{1,n} [/mm] kann nicht stimmen, denn für n=k sollte ja
[mm] ^ka_{1,k}=k! [/mm] gelten
2. Rekursion ist so zu erklären:
Anzahl bei n Ziehungen aus k Kugeln
mindestens jede Kugel 2 mal gezogen zu haben
Mögl. 1: bei den ersten k Ziehungen ziehe ich jede Kugel mind. 1 mal und bei den restlichen n-k ebenfalls mindestens einmal
Mögl. 2: bei den ersten k+1 Zieheung ziehe ich jede Kugel mind. 1 mal und bei den restlichen n-k+1 ebenfalls mindestens einmal
usw - Aufsummieren.....verallg. ergibt REkursion (an der ich jetzt wieder zweifle
|
|
|
| |
|
Hallo,
ich habe den Fall mit k=4 und n=7 auf dem
Computer durchgespielt: alle [mm] 4^7=16384
[/mm]
Variationen berechnet und für jede gezählt,
wieviele unterschiedliche Elemente sie
enthält. Dabei ergaben sich aber andere
Anzahlen als nach meiner vorher vorgestellten
Formel. Die Ergebnisse:
[mm] $\pmat{&Formel&Simulation\\m_1&4&4\\m_2&764&756\\m_3&7980&7224\\m_4&7636&8400}$
[/mm]
Ich habe also irgendetwas übersehen.
Ein Widerspruch ergibt sich auch, wenn
ich in der Formel für $\ [mm] ^ka_{1,n}$
[/mm]
n=k setze. Es sollte ja k! herauskommen,
tut es aber nicht.
Wo liegt also der Fehler ?
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Mi 12.08.2009 | | Autor: | wauwau |
Der Subtrahend [mm] k(k-1)^{n-1} [/mm] deiner Formel ist genau die Anzahl von Möglichkeiten, dass eine Kugel in den Ziehungen nicht vorkommt.
Das Gegenteil davon ist aber nicht jede Kugel mindestens einmal
Das Gegenteil von jede Kugel mindestens einmal ist es gibt genau eine Kugel, oder genau 2 Kugeln, oder genau 3 Kugeln oder genau n-1 Kugeln die gar nicht vorkommen
Da muss man dann mit Inklusion/Exklusion arbeiten glaub ich..
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:37 Mi 12.08.2009 | | Autor: | wauwau |
Andere Idee:
Es sei [mm] (x_1+x_2+x_3+....+x_k)^n [/mm] = [mm] \summe_{i_1+i_2+...+i_k=n}^{}\vektor{n \\ i_1,i_2,....i_k}x_1^{i_1}x_2^{i_2}...x_k^{i_k}
[/mm]
mit Multinomialkoeffizient
[mm] \vektor{n \\ i_1,i_2,....i_k} [/mm] = [mm] \bruch{n!}{i_1!i_2!...i_k!}
[/mm]
Das ist sozusagen die erzeugende Funktion von n Ziehungen aus k Elementen.
Daher ist
[mm] ^ka_{r,n} [/mm] = [mm] \summe_{i_1+i_2+...+i_k=n, i_k \ge r}^{}\vektor{n \\ i_1,i_2,....i_k}
[/mm]
|
|
|
| |
|
> Andere Idee:
>
> Es sei [mm](x_1+x_2+x_3+....+x_k)^n[/mm] =
> [mm]\summe_{i_1+i_2+...+i_k=n}^{}\vektor{n \\ i_1,i_2,....i_k}x_1^{i_1}x_2^{i_2}...x_k^{i_k}[/mm]
>
> mit Multinomialkoeffizient
> [mm]\vektor{n \\ i_1,i_2,....i_k}[/mm] =
> [mm]\bruch{n!}{i_1!i_2!...i_k!}[/mm]
>
> Das ist sozusagen die erzeugende Funktion von n Ziehungen
> aus k Elementen.
> Daher ist
>
> [mm]^ka_{r,n}[/mm] = [mm]\summe_{i_1+i_2+...+i_k=n, i_k \ge r}^{}\vektor{n \\ i_1,i_2,....i_k}[/mm]
>
Sehr schön,
aber das sieht für die numerische Umsetzung auch
nicht gerade nach Zuckerschlecken aus ...
Doch liesse sich dies immerhin irgendwie program-
mieren, grob (und unfertig) skizziert:
summe:=0;
for [mm] i_1:=r [/mm] to n do
for [mm] i_2:=r [/mm] to [mm] n-i_1 [/mm] do
for [mm] i_3:=r [/mm] to [mm] n-i_1-i_2 [/mm] do
.....
.....
for [mm] i_k:=r [/mm] to [mm] n-i_1-i_2.....-i_{k-1} [/mm] do
summe:=summe+multinomial [mm] (i_1,i_2,.....,i_k)
[/mm]
(dies lässt sich natürlich viel eleganter machen)
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:34 Mi 12.08.2009 | | Autor: | wauwau |
Einige Summanden kannst du schon noch sparen...
> Sehr schön,
>
> aber das sieht für die numerische Umsetzung auch
> nicht gerade nach Zuckerschlecken aus ...
> Doch liesse sich dies immerhin irgendwie program-
> mieren, grob (und unfertig) skizziert:
>
> summe:=0;
> for [mm]i_1:=0[/mm] to n do
for [mm] i_1:=r [/mm] to n-(k-1)r
> for [mm]i_2:=r[/mm] to [mm]n-i_1[/mm] do
for [mm] i_2:=r [/mm] to [mm] n-i_1-(k-2)r
[/mm]
> for [mm]i_3:=r[/mm] to [mm]n-i_1-i_2[/mm] do
> .....
> .....
> for [mm]i_k:=r[/mm] to [mm]n-i_1-i_2.....-i_{k-1}[/mm] do
> summe:=summe+multinomial [mm](i_1,i_2,.....,i_k)[/mm]
>
> (dies lässt sich natürlich viel eleganter machen)
>
>
> LG Al
|
|
|
| |
|
> Einige Summanden kannst du schon noch sparen...
>
> > Sehr schön,
> >
> > aber das sieht für die numerische Umsetzung auch
> > nicht gerade nach Zuckerschlecken aus ...
> > Doch liesse sich dies immerhin irgendwie program-
> > mieren, grob (und unfertig) skizziert:
> >
> > summe:=0;
> > for [mm]i_1:=0[/mm] to n do
> for [mm]i_1:=r[/mm] to n-(k-1)r
>
> > for [mm]i_2:=r[/mm] to [mm]n-i_1[/mm] do
>
> for [mm]i_2:=r[/mm] to [mm]n-i_1-(k-2)r[/mm]
>
> > for [mm]i_3:=r[/mm] to [mm]n-i_1-i_2[/mm] do
> > .....
> > .....
> > for [mm]i_k:=r[/mm] to [mm]n-i_1-i_2.....-i_{k-1}[/mm] do
> > summe:=summe+multinomial [mm](i_1,i_2,.....,i_k)[/mm]
> >
> > (dies lässt sich natürlich viel eleganter machen)
> >
> >
> > LG Al
Hab' ich mir alles schon gedacht - deshalb auch die
Ausdrücke "grob" und "unfertig". Ich dachte, dass die
Grundidee deutlicher rüberkommt, wenn ich zuerst
einmal diese Überhänge stehen lasse ...
Gruß und ![[gutenacht]](/images/smileys/gutenacht.gif "[gutenacht]") Al
|
|
|
| |
|
---Hat sich erledigt---
!!!Bitte schließen!!!
|
|
|
| |
|
> Da muss man dann mit Inklusion/Exklusion arbeiten glaub ich..
>
>
Davon bin ich eigentlich auch ausgegangen, hab' es aber
offenbar nicht richtig hingekriegt ...
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:55 Mi 12.08.2009 | | Autor: | rabilein1 |
> > Wie kam ich da nur auf die 433 ???
>
> Das müsstest du selber am ehesten herausfinden
> können
Ich habe da einen Verdächtigen = meinen Taschenrechner
Wenn ich 3*5 mit dem TR rechne, und er gibt mir als Ergebnis "22" raus, dann weiß ich, dass er spinnt.
Aber was ist mit [mm] 0.99^{433} [/mm] oder [mm] 0.99^{1161}.
[/mm]
An alle Mathematiker weltweit, gebt es zu: auch ihr würdet hier eurem TR blind vertrauen !!!
>
> ... Diese Gleichung hat eine Lösung zwischen 1160 und 1161.
Also waren meine Überlegungen doch irgendwie richtig.
|
|
|
| |
|
> Ich habe da einen Verdächtigen = meinen Taschenrechner
> Wenn ich 3*5 mit dem TR rechne, und er gibt mir als
> Ergebnis "22" raus, dann weiß ich, dass er spinnt.
>
> Aber was ist mit [mm]0.99^{433}[/mm] oder [mm]0.99^{1161}.[/mm]
> An alle Mathematiker weltweit, gebt es zu: auch ihr
> würdet hier eurem TR blind vertrauen !!!
Nicht, wenn zum Beispiel ein negatives oder ein
Ergebnis grösser als Eins angezeigt würde ...
Welche Ergebnisse liefert denn dein Rechner für
diese Potenzen ?
Und was für ein Rechner ist es ?
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:40 Mi 12.08.2009 | | Autor: | rabilein1 |
Zur Erinnerung:
Meine Formel lautete [mm] 0.99^{x}*(x-1)^{3} \approx [/mm] 13300
Nun wollte ich durch Probieren das x rauskriegen.
Und wenn ich eintippe 0.99 hoch 433 mal 432 hoch 3, dann kommt da raus 13382.26
Ich weiß aber nicht, was der TR hier genau rechnet....
Jetzt rechne ich mal einzeln:
[mm] 0.99^{433} [/mm] = 0.01288366
[mm] 432^{3} [/mm] = 80821568
und nun 80821568 * 0.01288366 = 1038700.871
Hey - das ist was ganz anderes als die anfängliche Kombi-Rechnung ergeben hat.
> Und was für ein Rechner ist es ?
Es ist ein No-Name "Scientific-Rechner", den ich mal für 7 Euro bei ebay ersteigert habe.....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:49 Mi 12.08.2009 | | Autor: | rabilein1 |
Jetzt weiß ich auch, wo mein Fehler liegt:
Ich hatte zwei Mal auf die "Ergebnis-Taste" gedrückt. Also rechnete der TR:
80821568 * 0.01288366 * 0.01288366
Und hier kam was mit etwa 13300 raus. Und da mir das Ergebnis "plausibel"*) erschien, hatte ich es nicht weiter hinterfragt.
plausibel*) : Bei so einer Art von Aufgabe kann man sehr schlecht abschätzen, was da wohl ungefähr raus kommen könnte.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:49 Mi 12.08.2009 | | Autor: | Herby |
Hi,
> Zur Erinnerung:
> Meine Formel lautete [mm]0.99^{x}*(x-1)^{3} \approx[/mm] 13300
>
> Nun wollte ich durch Probieren das x rauskriegen.
>
> Und wenn ich eintippe 0.99 hoch 433 mal 432 hoch 3, dann
> kommt da raus 13382.26
>
> Ich weiß aber nicht, was der TR hier genau rechnet....
>
>
> Jetzt rechne ich mal einzeln:
>
> [mm]0.99^{433}[/mm] = 0.01288366
>
> [mm]432^{3}[/mm] = 80821568
>
> und nun 80821568 * 0.01288366 = 1038700.871
ich erhalte in allen Fällen (Kombi und Einzel) [mm] 1038700,8\red{84}
[/mm]
Liebe Grüße
Herby
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:55 Mi 12.08.2009 | | Autor: | rabilein1 |
> ich erhalte in allen Fällen (Kombi und Einzel) [mm]1038700,8\red{84}[/mm]
Das war hier völlig unwichtig.
Es ging nicht um die Stellen nach dem Komma, sondern darum, ob da dreizehntausend raus kommt oder eine Million....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:59 Mi 12.08.2009 | | Autor: | Herby |
Hallo Rabilein,
> > ich erhalte in allen Fällen (Kombi und Einzel)
> [mm]1038700,8\red{84}[/mm]
>
> Das war hier völlig unwichtig.
> Es ging nicht um die Stellen nach dem Komma, sondern darum,
> ob da dreizehntausend raus kommt oder eine Million....
ich weiß
Lg
Herby
|
|
|
| |
|
> Meine Formel lautete [mm]0.99^{x}*(x-1)^{3} \approx[/mm] 13300
>
> Nun wollte ich durch Probieren das x rauskriegen.
>
> Und wenn ich eintippe 0.99 hoch 433 mal 432 hoch 3, dann
> kommt da raus 13382.26
>
> Ich weiß aber nicht, was der TR hier genau rechnet....
> > Und was für ein Rechner ist es ?
>
> Es ist ein No-Name "Scientific-Rechner", den ich mal für 7
> Euro bei ebay ersteigert habe.....
Dann hast du ja immer noch die Chance, das Ding
(allenfalls sogar mit Gewinn) weiter zu versteigern
Schlaf gut ! Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:20 Fr 14.08.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](/images/popup.gif){kind=small}
Wiki