Ich befülle das Array mit einem zufälligen Muster aus 0 und 1. Addiere
ich nun den Inhalt des Array, lande ich immer zwischen 40 und 60. Es
findet somit eine fast ausgewogene Verteilung von 0 und 1 statt. Für
meine Anwendung benötige ich aber auch den Fall, dass ich zwischen 10
und 90 komme. Wie kann ich das lösen?
Viele Grüße
Felix
Felix schrieb:> lande ich immer zwischen 40 und 60.Felix schrieb:> benötige ich aber auch den Fall, dass ich zwischen 10> und 90 komme
Die Verteilung folgt im Idealfall einer Gauß-Normalverteilung.
Mach das oft genug dann ist auch 10% und 90% dabei.
Für unendliche Anzahl von Durchläufen sogar 0% und 100%.
Max M. schrieb:> Die Verteilung folgt im Idealfall einer Gauß-Normalverteilung.> Mach das oft genug dann ist auch 10% und 90% dabei.> Für unendliche Anzahl von Durchläufen sogar 0% und 100%.
Super, vielen Dank für die Information.
Das mit der Gauß-Verteilung (die typische Glockenkurve) müsste man
meiner Meinung nach, mal durch eine Quelle belegen. Ich kenne allerdings
keine.
Eine kurze Suche führt zu dem Ergebnis, dass der C++ Standard (welcher
genau, habe ich auf die Schnelle nicht feststellen können) nichts über
die Verteilung sagt. Also haben die Zahlen irgendeine Verteilung.
(Nichts desto Trotz wird aufgrund des konkreten Verfahrens die
Verteilung schon eine bestimmbare sein. Das Gegenteil will ich damit
nicht sagen). Ich würde also mal in dem konkret anwendbaren Standard
nachschauen.
An anderer Stelle wird darauf hingewiesen, dass POSIX sehr wohl
vorschreibt, dass die Verteilung eine Gleichverteilung ist. Es wäre also
die Frage, ob der Compiler bzw. die verwendete Bibliothek den Anspruch
hat POSIX-konform ist und ob sich das auch auf die rand-Funktionen
bezieht. Das kann man sicher in der Doku zum Compiler resp. der
Bibliothek feststellen.
Zu beachten ist auch, dass die modulo-Operation zu einer leichten
Bevorzugung der kleineren Zahlen innerhalb der Spanne 0 und n (bei
Anwendung von rand () % n) führt. Siehe:
http://www.cplusplus.com/reference/cstdlib/rand/ Leider habe ich die
math. Begründung dafür auf die Schnelle nicht finden können.
Vorsicht bitte also bei der Annahme, es handele sich hier fraglos um
eine Gauss-Verteilung. :-)
Hallo Theor,
Theor schrieb:> Vorsicht bitte also bei der Annahme, es handele sich hier fraglos um> eine Gauss-Verteilung. :-)
so aus dem Kopf:
Dem zentralen Grenzwertsatz von ??? nach, folgt die Summe von
Zufallswerten aus beliebigen Verteilungen immer einer Gauss'schen
Verteilung.
Felix schrieb:> Ich befülle das Array mit einem zufälligen Muster aus 0 und 1. Addiere> ich nun den Inhalt des Array, lande ich immer zwischen 40 und 60. Es> findet somit eine fast ausgewogene Verteilung von 0 und 1 statt. Für> meine Anwendung benötige ich aber auch den Fall, dass ich zwischen 10> und 90 komme. Wie kann ich das lösen?
Deiner Frage fehlt die Angabe der von Dir gewünschten Zielverteilung.
Sind 10 und 90 harte Grenzen?
Dann solltest Du mit der Formel 10 + 80*zufall() gleichverteilte
Zufallszahlen erzeugen können unter der Voraussetzung, dass zufall()
gleichverteilt im Intervall [0;1[ ist.
Ob bei Deiner Zufallsfunktion die obere Intervallgrenze dazugehört,
müsstest Du mal überprüfen.
Sollen die Zahlen Gauss-verteilt sein, gibt es eine Formel, mit der Du
gleichverteilte Zufallszahlen in standardnormalverteilte (µ=0, sigma=1)
überführen kannst.
<random> hat verschiedene Generatoren auch gleichverteilte,
da stellst du die oberen und untern grenzen ein, dann tauchen die Werte
innerhalb der Grenzen auch öfters auf. So wie du das oben machst
erreichst du bei array-size=100 praktisch nie diese Werte die du
anvisierst.
Ich weiss auch nicht was du genau vor hast, wenn es nur um Werte
innerhalb eines Intervals geht, also deine "sum" dann geht das ohne
Array.
http://www.cplusplus.com/reference/random/
Dirk K. schrieb:> Ich finde die Verwendung des Arrays seltsam:> Benötigst du solch ein Array, dass die Anforderungen> erfüllt (Summe aller Elemente in einem Bereich)> oder benötigst du eine Zahl die in einem Bereich liegt?Franko S. schrieb:> Ich weiss auch nicht was du genau vor hast, wenn es nur um Werte> innerhalb eines Intervals geht, also deine "sum" dann geht das ohne> Array.
Es geht darum, dass ich mehrere Arrays benötige, die jeweils eine
unterschiedliche Anzahl an 0 und 1 haben (Reihenfolge egal). Damit meine
ich, dass z.B. ein Array mit nur 1en genau so wahrscheinlich ist wie ein
Array mit nur 0en und natürlich alles dazwischen.
Viele Grüße
Peter M. schrieb:> Hallo Theor,>> Theor schrieb:>> Vorsicht bitte also bei der Annahme, es handele sich hier fraglos um>> eine Gauss-Verteilung. :-)>> so aus dem Kopf:>> Dem zentralen Grenzwertsatz von ??? nach, folgt die Summe von> Zufallswerten aus beliebigen Verteilungen immer einer Gauss'schen> Verteilung.> [...]
Ich vermute, Du willst einwenden, dass die wiederholte Ausführung des
Programmes oben, zu Summen führt, die Normalverteilt sind, richtig?
Ich vermute weiter Du willst damit sagen, dass es für den Zweck des TOs
unwichtig ist, welche konkrete Verteilung vorliegt. Dem stimme ich unter
dem Vorbehalt zu, dass die restlichen Voraussetzungen der endlichen
und positiven Varianz zutreffen.
Mein Einwand richtet sich im Kern aber auf die Aussage, rand liefere
definitiv eine Normalverteilung. Das eben ist im Standard nicht
beschrieben, aber in POSIX. Darum ging es mir. Falls nämlich die Lib
nicht POSIS konform ist (falls zugegeben eher unwahrscheinlich ist),
dann ist auch die Varianz nicht zwingend positiv und endlich.
Theor schrieb:> Das mit der Gauß-Verteilung (die typische Glockenkurve) müsste man> meiner Meinung nach, mal durch eine Quelle belegen. Ich kenne allerdings> keine.
Die Anzahl der 1-Bits folgt einer Binomialverteilung
https://de.wikipedia.org/wiki/Binomialverteilung
Die Wahrscheinlichkeit, dass 90 von 100 Bits den Wert 1 haben, ist nur
1.37E-17, so dass man ziemlich viele Versuche starten muss, um einmal
diesen Fall zu erhalten. Lange vorher wird man schon an die Grenzen des
Zufallsgenerators aus der Standardbibliothek stoßen.
Felix schrieb:> Es geht darum, dass ich mehrere Arrays benötige, die jeweils eine> unterschiedliche Anzahl an 0 und 1 haben (Reihenfolge egal).
Dann erzeuge einfach eine gleichverteilte Zufallszahl n mit 0≤n≤100 und
fülle die ersten n Elemente des Arrays mit 1, den Rest mit 0.
Yalu X. schrieb:> Theor schrieb:>> Das mit der Gauß-Verteilung (die typische Glockenkurve) müsste man>> meiner Meinung nach, mal durch eine Quelle belegen. Ich kenne allerdings>> keine.>> Die Anzahl der 1-Bits folgt einer Binomialverteilung>> https://de.wikipedia.org/wiki/Binomialverteilung>> [...]
Und wo steht, dass der Compiler resp. die verwendete Lib Zufallszahlen
mit Binomialverteilung erzeugt?
Theor schrieb:> Und wo steht, dass der Compiler resp. die verwendete Lib Zufallszahlen> mit Binomialverteilung erzeugt?
Ja, die Verteilung bzw. der Algorithmus der rand-Funktion ist nicht
spezifiziert. Üblicherweise sind die von rand() erzeugten Zufallszahlen
aber gleichverteilt, und mir ist auch keine C-Bibliothek bekannt, die
sich diesbezüglich anders verhält.
Die Binomialverteilung bezog sich auf die Anzahl der 1-Bits im Array
unter der Annahme, dass rand() gleichverteilte Zufallszahlen liefert.
Wenn man aber sowieso C++ verwendet, sollte man die mit C++11
eingeführten Zufallszahlenklassen/-templates verwenden, für
gleichverteilte Zahlen also std::uniform_int_distribution.
https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution
Felix schrieb:> Es geht darum, dass ich mehrere Arrays benötige, die jeweils eine> unterschiedliche Anzahl an 0 und 1 haben (Reihenfolge egal). Damit meine> ich, dass z.B. ein Array mit nur 1en genau so wahrscheinlich ist wie ein> Array mit nur 0en und natürlich alles dazwischen.
Lösungsvorschlag:
n ist Deine Array-Länge
m (m<n) ist die Anzahl der Einsen
Die bestimmst mit einer Ziehung aus dem Zufallsgenerator die Zahl Deiner
Einsen.
p ist dann die Anzahl der Nullen. (p=n-m)
Nun richtest Du Dir gedanklich einen Puffer der Länge n ein, in dem die
erst die Nullen und Einsen stehen.
Den verwaltest Du mit zwei Variablen r und s
r ist die Restpufferlänge (Ausgangswert n)
s ist die letzte Stelle, an der 0 steht: s=n-m
Nun ziehst Du ein Element per Zufallsgenerator aus Deinem Puffer.
Nun ziehst Du einen zufälligen Indexwert i zum Puffer.
Steht dort eine Null, wird die Null entnommen und die Anzahl der Nullen
verringert und die Pufferlänge verkürzt:
s=s-1 und r=r-1.
Steht dort eine Eins, wird die Eins entnommen und die Anzahl der Einsen
verringert und die Pufferlänge verkürzt:
r=r-1
Das geht solange bis der Puffer leer ist, bzw. das letzte Element, das
ja bekannt ist, gezogen werden muss.
Beispiel:
n=5 (Array ist 5 Elemente lang)
p=3 (3 Nullen).
Dann ist r=5 und s=3.
Gedanklich bilden wir den Puffer 00011.
Wir indexieren von 1 bis n, bzw. 1 bis r.
Erster Zufallswert aus dem Intervall [1;r=5] ist der Index 2.
Da 2 <=s=3 ist, haben wir die zweite Null gezogen.
Das Ergebnisarray hat als erstes Element also die Null.
Nun schrumpfen wir den Puffer um eine Null:
r=r-1 also ist r=4 und s=s-1=2
Der Puffer sieht jetzt so aus:
0 011, also 0011.
Wir ziehen jetzt den Index 4 aus dem Intervall [1;r=4]
4>s=2 also haben wir eine 1 gezogen.
Ergebnisarray: 01
Wir schrumpfen den Puffer:
001_ = 001
r=3 und s hat sich nicht verändert.
Wir ziehen jetzt den Index 2 aus dem Intervall [1;r=3]
2<=s=2 also haben wir eine 0 gezogen.
Ergebnisarray: 010
Wir schrumpfen den Puffer:
0_1 = 01
Wir ziehen jetzt den Index 2 aus dem Intervall [1;r=2]
2<=s=2 also haben wir eine 1 gezogen.
Ergebnisarray: 0101
Wir schrumpfen den Puffer:
0_ = 0
Der letzte Wert ist eine Null, wir brauchen dafür keine Zufallszahl zu
berechnen.
Ist es das, was Du brauchst?
Die rand-Funktion hat einen miesen Ruf, da sie in vielen
Implementationen in den unteren Bits nur sehr wenig Zufall hat (kurze
Periode). Aus der Linux-Man-Page von rand(3):
1
The versions of rand() and srand() in the Linux C Library
2
use the same random number generator as random(3) and
3
srandom(3), so the lower-order bits should be as random as
4
the higher-order bits. However, on older rand() implemen‐
5
tations, and on current implementations on different sys‐
6
tems, the lower-order bits are much less random than the
7
higher-order bits. Do not use this function in applica‐
8
tions intended to be portable when good randomness is
9
needed. (Use random(3) instead.)
Ich brauchte auch mal Zufallbits für "graue" Bilder und war erschrocken,
wie regelmäßig die Bits waren (mod 2, wie oben), die aus rand(3)
rauskamen - als Rauschmuster vollkommen ungeeignet. (Das war zu nem
Zeitpunkt, wo der Hinweis, dass jetzt random(3) benutzt wird, noch nicht
drin war ;-) )
Was hängengeblieben ist: Finger weg von rand(3), wenn's gar nicht anders
geht, dann die höchsten Bits nehmen. Besser ist aber immer random(3).
> Ja, die Verteilung bzw. der Algorithmus der rand-Funktion ist nicht> spezifiziert.
Posix liefert eine Beispielimplementation, die leider den Weg in
genügend Libraries gefunden hat:
1
staticunsignedlongnext=1;
2
3
/* RAND_MAX assumed to be 32767 */
4
intrand(void){
5
next=next*1103515245+12345;
6
return((unsigned)(next/65536)%32768);
7
}
8
9
voidsrand(unsignedseed){
10
next=seed;
11
}
Das ist der Algorithmus, von dem man bei rand(3) ausgehen muß. Wenn ein
spezielles System nen besseren hat - Glück gehabt ;-)
Oh je, geht das hier alles ein bisschen durcheinander.
Zuerst mal zu rand(). Wie jemand schon schrieb gibt es klassische
Implementierungen die das Problem haben, dass das LSB (das letzte Bit,
das man mit % 2 oder & 1 erhält) nicht so gleichmäßig verteilt ist, wie
man es gerne hätte. Das ist altbekannt.
Der Workaround, wenn man wirklich nichts besseres als rand() hat, ist
ebenso alt. Statt dem LSB das MSB nehmen. Dabei gibt es eine Bedingung.
Das MSB nehmen setzt voraus das RAND_MAX eine Zahl (2^N - 1) ist, d.h.
RAND_MAX | (RAND_MAX >> 1) == RAND_MAX.
Dann das MSB nehmen bedeutet, man unterteilt den Wertebereich [0,
RAND_MAX] in zwei Bereiche [0, int(RAND_MAX >> 1)] und [int(RAND_MAX >>
1) + 1, RAND_MAX]. Jedes Intervall hat gleich viel Werte, da RAND_MAX
ungerade ist plus die 0, und man schaut über das MSB nach, in welchem
Bereich man liegt.
Die Maske zum Testen des MSB ist RAND_MAX ^ (RAND_MAX >> 1), und damit
erhält man die gewünschten Werte als !!(rand() & (RAND_MAX ^ (RAND_MAX
>> 1)))
Wenn RAND_MAX nicht 2^N - 1 ist, dann ist ein anderer Workaround rand()
/ ((RAND_MAX >> 1) + 1). ABER, der Workaround funktioniert nur, wenn
RAND_MAX wenigstens ungerade ist. Ist RAND_MAX gerade, lässt sich der
Wertebereich nicht in zwei gleich große Intervalle teilen.
Daher sollte man rand() wirklich nur nehmen wenn man nichts Besseres hat
oder wenn es nicht so genau drauf an kommt.
Zur Erzeugung anderer Verteilungen als Gleichverteilungen mittels
gleichverteilter Zufallszahlen:
Das Verfahren nennt sich Inversionsmethode. Leider haben sich beim
entsprechenden Wikipedia-Artikel
https://de.wikipedia.org/wiki/Inversionsmethode mal wieder Mathematiker
ausgetobt um das allgemeine Verfahren so unverständlich wie möglich zu
beschreiben.
Das konkrete Beispiel
(https://de.wikipedia.org/wiki/Inversionsmethode#Beispiel_einer_Verteilung_mit_zwei_Werten)
einer 75%:25% Verteilung ist allerdings noch lesbar. Es zeigt das
Prinzip, das man ebenso zur Erzeugung der hier gesuchten 90%:10%
Verteilung anwenden kann. Im Beispiel werden allerdings keine
Integer-Zahlen verwendet. Das dortige Intervall [0, 1] enthält unendlich
viele Werte.
Hannes J. schrieb:> Oh je, geht das hier alles ein bisschen durcheinander.>> [...]
Ja. Es ist noch schlimmer, als ich dachte.
Ich kann nicht einmal eine Bestätigung dafür finden, dass POSIX eine
bestimmte Verteilung für rand() vorschreibt.
https://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html
Ich ziehe diese, meine obige Behauptung also, - mit Bedauern -, zurück.
Ich habe nicht genügend recherchiert.
Aber in C++ gibts ja nun <std::...> Das hilft schonmal weiter. :-)
Felix schrieb:> Damit meine> ich, dass z.B. ein Array mit nur 1en genau so wahrscheinlich ist wie ein> Array mit nur 0en und natürlich alles dazwischen.
Bei rand() wird ein Array von nur 1en genauso wahrscheinlich sein, wie
das von nur 0en. Die Wahrscheinlichkeit, dass das passiert ist aber sehr
klein.
Kleines Rechenbeispiel:
Annahme, dass eine 1 kommt ist 50%
Bei einem Array der Länge 10, hätte man damit bereits eine
Wahrscheinlichkeit von nur 0.1%, dass das gesamte Array eine 1
beinhaltet.
Nun, ich kenne deine Arraylänge nicht, aber besser werden die Chancen
nicht.
https://www.wolframalpha.com/input/?i=binomial+distribution+10+0.5
Hier kannst du einmal etwas mit deinen Zahlen spielen. Wie du in der
untersten Tabelle siehst, liegt die Wahrscheinlichkeit, dass mindestens
eine Zahl anders ist, bei 99.9%.
Hast du aber nicht 10 sondern 100 oder 1000 Zahlen in deinem Array, ist
die Wahrscheinlichkeit, dass du irgendwo zwischen 40 und 60 landest
immer grösser.
Wenn du zum testen ein „zufälliges“ Array mit 10% 1 oder 0 brauchst,
dann füll dein Array komplett mit 1/0, und wähle dann 10 zufällige
Positionen für 0/1.
Oliver
Thread beobachten
Seitenaufteilung abschalten