Prozentuelle Wahrscheinlichkeit

[memoryleak]

Hallo
Ich habe eine Tabelle mit Werten, sagen wir

Apfel (23%)
Birne (69%)
Kiwi (38%)
Zu den einzelnen Früchten steht eine prozentuale Wahrscheinlichkeit, wie häufig diese Auftreten werden.

Jetzt möchte ich Programmiertechnisch in einer Schleife mit 1000 Durchgängen zufällig einen dieser Früchte rauspicken. Das Problem: Wie programmiere ich den Zufallsgenerator so, dass die prozentangaben ungefähr hinkommen?

[Jan Krüger]

Erstmal bedenke, dass die Summe aller dieser Wahrscheinlichkeiten 100% betragen muss, sonst ist diese Angabe völlig unbenutzbar.

Es folgt halbwegs performanter Ansatz.

1. Stell sicher, dass du irgendeine definierte Reihenfolge der Tabellenzeilen hast, die sich nicht ändert.
2. Addiere zu jedem Prozentwert die Summe der Prozentwerte in den Zeilen darüber. Beispiel:

1% Apfel => 1 Apfel
2% Birne => 3 Birne
3% Clementine => 6 Clementine
8% Drachenfrucht => 14 Drachenfrucht
10% Erdbeere => 24 Erdbeere
12% Feige => 36 Feige
15% Grapefruit => 51 Grapefruit
18% Himbeere => 69 Himbeere
31% Jackfrucht => 100 Jackfrucht

Jetzt nimmst du eine Zufallszahl von 0 bis 99 (typischerweise schreibt man das rand(100)) und nimmst die Frucht, deren Wert am nächsten über der Zufallszahl liegt. Für die 53 wäre das z.B. die Himbeere.

Hast du Prozentwerte mit Kommastellen, solltest du sie vor Schritt 2 alle mit einem Wert multiplizieren, der sie zu ganzen Zahlen macht, um brauchbare Zufallszahlen erzeugen zu können. Angenommen, du hast bis zu zwei Kommastellen, dann ist eine Multiplikation mit 100 ausreichend.

Die Obergrenze für die Zufallszahlen muss analog multipliziert werden. Hier wäre es dann also rand(10000), also Zufallszahlen von 0 bis 9999.

Prinzip verstanden?

PS. du kannst die Prozentwerte auch in ihrer eigentlichen Darstellung (0-1) verwenden, dann entfällt das mit dem Normalisieren. Zufallsgeneratoren liefern nämlich normalerweise standardmäßig Zahlen in [0,1) zurück.

[Firefall]

Oder einfacher, speichersparender: Du machst ne Zufallszahl zwischen 0 und X und überprüfst, ob diese Zahl in einem bestimmten Bereich liegt (z.B. > 5, <10). Falls dies zutrifft, wählst du die entsprechende Frucht aus. Quasi eine virtuelle Tabelle, wie in Jan's Beispiel ;)

[DarkTom]

Oder einfacher, speichersparenderWo sparst du da denn bitte Speicher?

[Firefall]

Wo sparst du da denn bitte Speicher?
Wenn du eine "reale" Tabelle erzeugst braucht das jenachdem sehr viel Speicher.

[Diogenes]

Ich würd' das (in Pascal) etwa so machen:

function Fruechtchen: string;

var
P: Byte;

begin
Randomize;
P := 100 * Random;
case P of
0 : Fruechtchen := 'Apfel'; // 1 %
01 .. 38: Fruechtchen := 'Birne'; // 38 %
39 : Fruechtchen := 'Stachelbeere'; // 1 % Ogrosl! Ogrosl! O-o-ogrosl!
40 .. 58: Fruechtchen := 'Melone'; // 19 % Ja, eine Beerenfrucht!
59 .. 98: Fruechtchen := 'Marille'; // 41 % Muß man als Österreicher wohl...
else Fruechtchen := 'Mol'
end
end;

[Firefall]

Genau so meinte ich das ;) Jetzt ists vielleicht klarer geworden.

[Diogenes]

Das war ein ad-hoc-Rohentwurf. Das läßt sich natürlich verfeinern: Indexzahlen statt String usw.

[Jan Krüger]

Quasi eine virtuelle Tabelle, wie in Jan's Beispiel ;)
Wenn man die Kontrolle darüber hat, in welchem Format man die Rohdaten verwendet, ist das kein Thema. Ich gehe bei sowas normalerweise davon aus, dass die Tabelle extern ist und unabhängig vom Programm aktualisiert werden kann.

[Diogenes]

OK. Wenn wir also die Form der Tabelle so annehmen, daß die Einträge als

type

TEntry = record
P: Extended; // Wahrscheinlichkeit
S: string; // Der Eintrag
end;

und weiter annehmen, daß die Funktion GetEntry( var Entry:TEntry); den nächsten Eintrag holt und EoT: Boolean; True ist, wenn das Ende erreicht ist, dann kann das so aussehen:

function Fruechtchen: string;

var
Sum, R: Extended;
Entry: TEntry;

begin
Sum := 0;
Randomize;
R := Random; // erzeugt 0 <= R < 1
{Einlesen der Tabelle initialisieren: Arrayindex, Datei, was auch immer}
GetEntry( Entry);
while not EoT do
begin
Sum := Sum + Entry.P;
if Sum < R
then Exit
else GetEntry( Entry)
end;
Fruechtchen := Entry.S
end;

[memoryleak]

Erstmal bedenke, dass die Summe aller dieser Wahrscheinlichkeiten 100% betragen muss, sonst ist diese Angabe völlig unbenutzbar.

Es folgt halbwegs performanter Ansatz.

1. Stell sicher, dass du irgendeine definierte Reihenfolge der Tabellenzeilen hast, die sich nicht ändert.
2. Addiere zu jedem Prozentwert die Summe der Prozentwerte in den Zeilen darüber. Beispiel:
....


Das beispiel is zwar schön, aber da ich mit diesen Zufallszahlengenerator arbeite: Was stellt denn in deinem Beispiel sicher, dass das prozentuale Auftreten der Einträge auch ungefähr zutrifft?

[mnemonic]

Das beispiel is zwar schön, aber da ich mit diesen Zufallszahlengenerator arbeite: Was stellt denn in deinem Beispiel sicher, dass das prozentuale Auftreten der Einträge auch ungefähr zutrifft?
Nichts.
Beim Würfeln hast Du auch keine "Garantie". Davon mal abgesehen hast Du in der Technik sowieso meist nur Pseudozufallszahlen (http://de.wikipedia.org/wiki/Pseudozufall), aber das will ich jetzt mal nicht vertiefen.
Das einzige, an was Du Dich da orientieren kannst, ist das Gesetz der großen Zahlen (http://de.wikipedia.org/wiki/Gesetz_der_gro%C3%9Fen_Zahlen).

[memoryleak]

Nichts.
Beim Würfeln hast Du auch keine "Garantie". Davon mal abgesehen hast Du in der Technik sowieso meist nur Pseudozufallszahlen (http://de.wikipedia.org/wiki/Pseudozufall), aber das will ich jetzt mal nicht vertiefen.
Das einzige, an was Du Dich da orientieren kannst, ist das Gesetz der großen Zahlen (http://de.wikipedia.org/wiki/Gesetz_der_gro%C3%9Fen_Zahlen).

Es geht mir ja nich darum, möglichst gute Zufälle zu produzieren. Sondern darum, dass bei sagen wir 100 Ziehungen die Prozentangaben stimmen. Dazu suche ich ein Mechanismus der sichert, dass die prozentzahlen ungefähr zutreffen.

[mnemonic]

Es geht mir ja nich darum, möglichst gute Zufälle zu produzieren. Sondern darum, dass bei sagen wir 100 Ziehungen die Prozentangaben stimmen. Dazu suche ich ein Mechanismus der sichert, dass die prozentzahlen ungefähr zutreffen.
100 ist nicht unbedingt eine grosse Zahl. ;)
Bei so wenig "Ziehungen" wirst Du immer Ausreisser haben, das liegt aber in der Natur der Sache. Ein wenig theoretisches Wissen über Zufall und Statistik wäre schon angebracht.
Du könntest natürlich versuchen einen Algorithmus zu bauen, der ab einem bestimmten Grad in die Generierung der Zufallszahlen eingreift, aber dann wäre das Endprodukt berechenbar und zu einem gewissen Grad unbrauchbar.

Ausserdem habe ich nicht die Güte Deiner Zufallszahlen kritisiert, sondern nur pauschal drauf hingewiesen, wie die Sachlage meist ist.

[Jan Krüger]

Was stellt denn in deinem Beispiel sicher, dass das prozentuale Auftreten der Einträge auch ungefähr zutrifft?
Was widerspricht dem denn (außer, dass Pseudozufallszahlengeneratoren niemals wirklich zufällige Zahlen liefern)?

[memoryleak]

100 ist nicht unbedingt eine grosse Zahl. ;)
Bei so wenig "Ziehungen" wirst Du immer Ausreisser haben, das liegt aber in der Natur der Sache. Ein wenig theoretisches Wissen über Zufall und Statistik wäre schon angebracht.
Du könntest natürlich versuchen einen Algorithmus zu bauen, der ab einem bestimmten Grad in die Generierung der Zufallszahlen eingreift, aber dann wäre das Endprodukt berechenbar und zu einem gewissen Grad unbrauchbar.

Ausserdem habe ich nicht die Güte Deiner Zufallszahlen kritisiert, sondern nur pauschal drauf hingewiesen, wie die Sachlage meist ist.

Ich habe beispielsweise ein Programm dass für mich diese Ziehungen macht. Er gibt mir jeweils die Früchte zurück, mit folgendem Ergebnis:

200 Durchgänge:
85x Apfel
55x Birne
58x Kiwi
2x Kirsche
Nach 1000 Wiederholungen schwanken die Ergebnisse um bis zu 15 - nicht mehr. Bedeutet das also, dass beim Generieren bestimmte Eingangsparameter (z.B. das Datum) verwendet wurden?

[Jan Krüger]

Dazu müsste man jetzt wissen, wie dieses Programm funktioniert...

[Firefall]

Bedeutet das also, dass beim Generieren bestimmte Eingangsparameter (z.B. das Datum) verwendet wurden?Jede "Zufallsfunktion" benötigt Eingabeparameter. Diese können z.B. aus den vergangenen Sekunden seit Mitternacht, den vergangenen Millisekunden in der aktuellen Sekunde, der PID (Prozess ID) oder auch dem Datum gewonnen werden. Daher sind diese Zahlen auch Pseudozufallszahlen. Sie können z.B. davon abhängen, ob du den Cursor während der Generierung bewegst. Oder ob der Mediaplayer im Hintergrund läuft, usw. Einen richtigen Zufall gibt es nirgends im Leben, ausser auf der Ebene der Elektronen. Und da gibt's ne Warscheinlichkeitsverteilung, also auch Pseudo auf eine Art ;)

[DarkTom]

Wenn du eine "reale" Tabelle erzeugst braucht das jenachdem sehr viel Speicher.Wir hatten wohl unterschiedliche Vorstellungen davon, wie Jans Vorgehen zu implementieren wäre. Ich stellte mir einen Datenarray vor und eine Schleife, in etwa so wie in Diogenes' zweiter Version. Da dürfte der (Maschinen)Programmcode kürzer sein als in deinem Ansatz, dafür kommt eben der Speicherplatz des Array hinzu. Alles in allem sollten sich beide Ansätze speicherplatztechnisch kaum unterscheiden.



Da es mittlerweile eher generell um das Generieren von (Pseudo)Zufallszahlen geht, trage ich noch einen Link bei:
http://random.mat.sbg.ac.at/

[eViL_oNe]

nicht zu verachten ist auch http://random.org/ *g*

Einen richtigen Zufall gibt es nirgends im Leben, ausser auf der Ebene der Elektronen. Und da gibt's ne Warscheinlichkeitsverteilung, also auch Pseudo auf eine Art ;)

naja -- an physikalischen Prozessen ist nix Pseudo -- Elektronen und andere Kleinstteilchen haben aufgrund der Heisenbergschen Unschärferelation entweder einen nicht definierten Ort, oder einen nicht definierten Impuls. Da in einer Atomhülle der Impuls von Elektronen sich aus deren Energiezustand ergibt, ist somit der Ort der Elektronen unbestimmt. Das Problem solche Effekte für die Zufallsbestimmung zu nutzen ist (außer der nicht ganz trivialen Meßtechnik natürlich), dass man durch die Messung das System beeinflusst und damit wieder eine Art Determinismus einbringt ;)

hier noch ein interessanter Artikel: http://en.wikipedia.org/wiki/Determinism

PS: "Gott würfelt nicht"

[Jan Krüger]

Und da gibt's ne Warscheinlichkeitsverteilung, also auch Pseudo auf eine Art ;)
Ich bin sicher, dass man sich aus echt stochastischen Ereignissen eine Gleichverteilung zusammenzaubern kann, und wenn man dafür ein bisschen rechnen muss.
Mir bekannte echte Zufallszahlengeneratoren basieren meines Wissens auf der Polarisierung von Photonen.