Wahrscheindlichkeit: Wiederholung 4 Byte Zufallszahl

Man muss hinsichtlich der Kollionswahrscheinlichkeit zwei Fälle 
unterscheiden:

1. Wie wahrscheinlich ist es, dass eine bestimmte Zahl mehrfach 
auftritt?

2. Wie wahrscheinlich ist es, dass eine beliebige Zahl mehrfach 
auftritt?

Die schon gegebene Antwort behandelt nur Fall 1, wohingegen bei Fall 2 
das Geburtstagsparadoxon gilt. Zwar hat der Ursprungsautor seine 
Aufgabenstellung nicht hinreichend präzise formuliert, aber von der 
typischen Art dieser Aufgabe nehme ich an, dass eher Fall 2 anzuwenden 
ist.

Maximum:  1 zu 2^4
Minimum:  1 zu 1

Da es auf einem PC kein Größe gibt, die wirklich Zufällig ist, wird die 
Zeit, die der PC läuft, als Startwert der Zufallsfunktion genutzt.
(es sei den du gibst was anderes an).
Wenn Du Pech hast und genau die Gleiche Zeit erwischt erhältst Du den 
gleichen Wert.
http://msdn.microsoft.com/de-de/library/f7s023d2%28v=vs.90%29.aspx#Y729

Nimm lieber eine fortlaufende Seriennummer.

Volker

Sepp der Grosse schrieb:
> Wie hoch ist die Wahrscheindlichkeit, das sich diese zufällig wiederholt?
Eine 32-Bit Zufallszahl wiederholt sich, wenn sie mit einem LFSR 
ermittelt wird, bei einem brauchbaren Polynom nach genau 2^32-1 
Abfragen. Eine 0 kommt nicht vor: 
http://www.lothar-miller.de/s9y/categories/38-LFSR
Die Reihenfolge ist zwischen diesen Wiederholungen exakt gleich.

Allerdings gibt es auch noch andere Verfahren, Zufallszahlen 
auszurechnen. Wie gut oder schlecht die VB Funktion ist, kann ich nicht 
sagen.

lrlr schrieb:
> 4 BYTE und nicht 4 BIT !

Tschuldigung, war ein Tippfehler, sollte 64 heißen.

Ansonsten ist es ein typischer Fall der Risikobewertung.
Nicht nur die Häufigkeit eines Fehlers, auch die möglichen Folgen sind 
zu Betrachten, ob eine Sache akzeptable ist.

Sollten durch den Fehler zwei Modelbahnampeln gleichzeitig Grün zeigen, 
ist das nur optische Unschön.
Fliegen zwei A380 auf dem gleichen Kurs(weil gleiche ID) ist es alles 
andere als Unschön.

http://de.wikipedia.org/wiki/Risikomatrix

volker

Hallo,

ich habe mich zwar mit irgendwelchen Formeln da nie rumgeschlagen, aber 
wenn ich den (Pseudo-)-Zufallszahl-Generator einmal mit einer Seed 
gestartet ist, kann die gleiche Zahl doch auch direkt hintereinander 
kommen?

Gruß aus Berlin
Michael

Michael U. schrieb:
> kann die gleiche Zahl doch auch direkt hintereinander kommen?
Nicht bei den üblichen Algorithmen.

Sepp der Grosse schrieb:
> Wie hoch ist die Wahrscheindlichkeit, das sich
> diese zufällig wiederholt? Festgelegt wird die Zahl über die RND
> Funktion von VB2008.

100%

RND liefert immer die gleiche Folge von Zufallszahlen.
Deshalb heißt es auch nur Pseudo-Zufall.

Du brauchst einen echten Zufallswert, welcher den Startwert von RND 
festlegt. Aber dann kannst Du ihn ja gleich nehmen.

Einen echten Zufall zu erzeugen, ist sehr schwer.
Man könnte einen Timer mit hoher Frequenz laufen lassen und den Nutzer 
per Tastendruck einen Interrupt ausführen lassen. Der Nutzer ist mit 
ziemlicher Sicherheit asynchron zum CPU-Takt.
Allerdings können Interrupts auch nicht zu jedem CPU-Zyklus ausgeführt 
werden, sondern Befehle und andere Interrupts müssen beendet sein.
Dieser Zufall ist also auch nicht wirklich gleichverteilt.
Am besten ist daher ein Input-Capture-Interrupt, der zyklusgenau den 
Zeitstempel des Tastendrucks speichert.


Windows selber kann keinen Zufall erzeugen, alles ist ja mit dem 
CPU-Takt synchron. Man braucht 2 voneinander unabhängige Takte.

Man könnte mit Google nach einem Begriff suchen und dann die Zeitdauer 
und die (hohe) Trefferanzahl verarbeiten. Das dürfte recht zufällig 
sein, wenn man das einen Tag später wiederholt.


Peter

Nimm doch nen Maxim Seriennummer-IC, die haben ne weltweit einmalige 
6Byte-ID.


Peter

Lothar Miller schrieb:
> Michael U. schrieb:
>> kann die gleiche Zahl doch auch direkt hintereinander kommen?
> Nicht bei den üblichen Algorithmen.

Dann sind diese Algorithmen aber schlecht. Die Wahrscheinlichkeit sollte 
für jede beliebige Zahl identisch sein, unabhängig davon, wann sie schon 
mal erwürfelt wurde oder nicht.

Sepp der Grosse schrieb:
> Will in meinen Geräten (zwecks Softwarezuordnung) eine 4 Byte
> Zufallszahl integrieren.

Da du die Zufallszahlen als Identifikationsnummern nutzen möchtest,
wirst du sie wahrscheinlich in einer Datenbank o.ä. zusammen mit
anderen Infromationen zum Produkt registrieren. Um zu vermeiden, dass
zweimal die gleiche Zahl auftritt, brauchst du ja nur in der Datenbank
nachzuschauen (oder durch ein Tool nachschauen lassen), ob die Zahl
schon verwendet wird und ggf. eine neue Zufallszahl generieren.

Aber viel besser ist doch das:

Volker Zabe schrieb:
> Nimm lieber eine fortlaufende Seriennummer.

Wenn der Endanwender aus der Nummer die Seriennummer nicht
rekonstruieren können soll, kannst ja noch dies tun:

Tip schrieb:
> Nimm doch einen Hash-Wert von der Seriennummer. Das ist übersichtlicher
> als wilde Zufallszahlen.

Lothar Miller schrieb:
> Michael U. schrieb:
>> kann die gleiche Zahl doch auch direkt hintereinander kommen?
> Nicht bei den üblichen Algorithmen.

Doch, gerade bei den üblichen Algorithmen. Diese verwenden für die
interne Berechnung meist die doppelte Bitzahl. Auf PCs wird also intern
mit 64 Bit gerechnet, um eine 32-Bit-Pseudozufallszahl zu generieren.
Ein Zufallsgenerator, der zwei gleiche aufeinanderfolgende Zahlen
grundsätzlich ausschließt, taugt allenfalls als Rauschgenerator für
Soundeffekte.

Lothar Miller schrieb:
> Michael U. schrieb:
>> kann die gleiche Zahl doch auch direkt hintereinander kommen?
> Nicht bei den üblichen Algorithmen.

Wieso nicht? Falls das nicht möglich wäre, hätte der 
Zufallszahlengenerator eine massive Schwäche. Nur relativ 
unwahrscheinlich ist es bei 2^32 verschiedenen Zahlen.

Gruß, Alex

Pragmatische Lösung: Teil die 64 bit auf, füll 32 Bit mit nem 
Unix-Timestamp o.Ä., die anderen 32 mit irgendwas, z.B. einer 
Pseudozufallszahl.
So kannst du bis 2037 jede Sekunde ein Gerät bauen und verkaufen, und es 
wird sich nie eine Seriennnummer wiederholen.

Peter Dannegger schrieb:
> Windows selber kann keinen Zufall erzeugen, alles ist ja mit dem
> CPU-Takt synchron. Man braucht 2 voneinander unabhängige Takte.

In einem PC gibt es eine Menge Dinge die zufällig (im Sinne von nicht 
vom CPU-Takt ableitbar) sind:
- Festplattenzugriffe
- Benutzereingaben
- Netzwerkereignisse

Jedes aktuelle Betriebssystem enthält einen Zufallszahlengenerator der 
diese Entropie einsammelt und so verwurstet dass hinten zuverlässige, 
gleichverteilte Zufallszahlen herauskommen. Unter Unix/Linux kommt man 
da über /dev/random ran, unter Windows z.B. so: 
http://msdn.microsoft.com/en-us/library/system.security.cryptography.rngcryptoserviceprovider.aspx

Alexander v. Grafenstein schrieb:
> Wieso nicht? Falls das nicht möglich wäre, hätte der
> Zufallszahlengenerator eine massive Schwäche.
J.-u. G. schrieb:
> Dann sind diese Algorithmen aber schlecht.
Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in 
zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der 
selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt 
vor, und schon gar nicht hintereinander.

WENN jetzt aber statt der 32 Bit einfach 64 Bits für den Generator 
verwendet werden, und aus diesen 64 Bit dann nur 32 Bits nach aussen 
dringen, DANN kannund wird durchaus auch eine mehrfache Wiederholung von 
Zahlen drin sein.

Andreas Schwarz schrieb:
> In einem PC gibt es eine Menge Dinge die zufällig (im Sinne von nicht
> vom CPU-Takt ableitbar) sind:
> - Festplattenzugriffe
> - Benutzereingaben
> - Netzwerkereignisse

Es ist aber nicht trivial, diese so zu verwursten, daß kein Einfluß des 
CPU-Taktes mehr besteht. Man muß dazu schon über die Internas gut 
Bescheid wissen, wie und wann die CPU diese Ereignisse auswertet.
Tasten- und Mauseingaben werden z.B. über den USB-Takt synchronisiert 
(alle 10ms).


Mal ein einfaches Beispiel:
AVR-Mikrokontroller:
Mainloop = Endlosschleife (RJMP = 2 Zyklen).
Taste an Interruptpin und oh Wunder, man kriegt nur gerade Zahlen vom 
Timer geliefert.
Die Erklärung: der 2-Zyklen-Befehl RJMP kann nicht unterbrochen werden.

Aber:
Taste an Pin-Change Interrupt: echter Zufall, da der Timestamp jeden 
CPU-Zyklus von der Hardware gelatcht werden kann.


Meistens braucht man aber keinen sehr guten Zufall und daher reichen die 
PC-Funktionen.
Ich hab z.B. zweimal hintereinander das gleiche Sudoku gelöst und es 
erst danach gemerkt.


Peter

micha schrieb:
> Lothar Miller schrieb:
>> Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in
>> zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der
>> selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt
>> vor, und schon gar nicht hintereinander.
> Mit Verlaub, das is Quatsch.
Was davon denn?
Ich sehe eigentlich nur, dass deine ganze Argumentation im Grunde das 
selbe sagt, nur eben mit anderen Worten...

Lothar Miller schrieb:
> micha schrieb:
>> Lothar Miller schrieb:
>>> Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in
>>> zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der
>>> selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt
>>> vor, und schon gar nicht hintereinander.
>> Mit Verlaub, das is Quatsch.
> Was davon denn?
> Ich sehe eigentlich nur, dass deine ganze Argumentation im Grunde das
> selbe sagt, nur eben mit anderen Worten...

nein, bildlich gesprochen propagierst du einen Zufallsgenerator ohne 
zurücklegen. und wenn keine Kugeln mehr da sind, ziehst du sie in der 
selben reihenfolge erneut.

Das entsprcht aber keinem Zufallsgernator, weil sich hier die 
Wahrscheinlichkeit, eine bestimmte Kugel zu ziehen erhöht, je mehr 
andere ich gezogen hab und somit die Zahlen nicht mehr gleichverteilt 
sind.

edit:
Ein gleichverteilter Zufallsgernator ist ein Zufallsexperiment mit 
zurücklegen.

Vlad Tepesch schrieb:
> nein, bildlich gesprochen propagierst du einen Zufallsgenerator ohne
> zurücklegen.
Naja, ich habe lediglich Hardware beschrieben. In der Realität wird das 
(unter strenger Missachtung der Zufallstheorie) einfach so einfach 
gemacht. Das nennt sich dann z.B. LFSR und reicht in gut 99% der Fälle 
für einen Zufall aus...

micha schrieb:
> Nichts für Ungut + gute WE
Dito. ;-)

Lothar Miller schrieb:
> Naja, ich habe lediglich Hardware beschrieben. In der Realität wird das
> (unter strenger Missachtung der Zufallstheorie) einfach so einfach
> gemacht. Das nennt sich dann z.B. LFSR und reicht in gut 99% der Fälle
> für einen Zufall aus...

Dann lies deinen Beitrag nochmal:
der redet von etwas völlig anderem.
du hast behautpted, dass der Zufallsgerator für n-bittige Zahlen eine 
Periode von genau 2^n hat und jede Zahl genau einmal vorkommt.

vom prinzip her also:
alle 2^n Kugeln in einen Sack schmeißen, kräftig schütteln und in einem 
Kreis hinlegen und nun der reihe nach die Zahlen vorlesen.

Tatsächlich kommt in einer Periode eines (halbwegs brauchbaren) 
Generators jede Zahl merhfach vor.

Quasi:
x*2^n Kugeln in einen Sack schmeißen ...
je größer x, desto besser natürlich. die c-standard rand() methode 
erzeugt 2^16 Zufallszahlen und arbeitet intern meist mit 32-Bit 
Variablen. Hier ist x quasi 2^16

Damit können nämlich tatsächlich die gleiche Zahl mehrmals 
hintereinander auftreten.

das ein LFSR natürlich kein allzuguter RNG ist, kann man an vielen 
stellen nachlesen, aber auf jden Fall um Längen besser, als der von dir 
erklärte Generator

Peter Dannegger schrieb:
> Andreas Schwarz schrieb:
>> In einem PC gibt es eine Menge Dinge die zufällig (im Sinne von nicht
>> vom CPU-Takt ableitbar) sind:
>> - Festplattenzugriffe
>> - Benutzereingaben
>> - Netzwerkereignisse
>
> Es ist aber nicht trivial, diese so zu verwursten, daß kein Einfluß des
> CPU-Taktes mehr besteht.

Aber auch nicht sehr schwierig:

> Mainloop = Endlosschleife (RJMP = 2 Zyklen).
> Taste an Interruptpin und oh Wunder, man kriegt nur gerade Zahlen vom
> Timer geliefert.

Mach das 10 Mal, berechne über die Zahlen einen Hash (z.B. MD5) und 
verwende 8 Bit davon; da wirst du mit normalen Mitteln keine Systematik 
mehr finden können.

> Meistens braucht man aber keinen sehr guten Zufall und daher reichen die
> PC-Funktionen.

Für Kryptographie ist guter Zufall sehr wichtig, deshalb bringt jedes 
halbwegs aktuelle Betriebssystem einen sehr gut funktionierenden 
Zufallsgenerator mit.

> Ich hab z.B. zweimal hintereinander das gleiche Sudoku gelöst und es
> erst danach gemerkt.

Da wurde wahrscheinlich der triviale rand()-Pseudozufallszahlengenerator 
verwendet.

Irgent wie haben wir den TO verloren. Er meldet sich gar nicht mehr.

Praktikable Lösung:
Speichere alle erzeugten IDs und vergleiche, ob du sie schon mal 
vergeben hast.

Hängt aber von deiner Anwendung ab, ob das eine gute Lösung ist.
Von der wir allerdings nicht viel Wissen. Nur das sie mit Geräten 
zusammen hängt.

volker

Vlad Tepesch schrieb:
> du hast behautpted, dass der Zufallsgerator für n-bittige Zahlen eine
> Periode von genau 2^n hat und jede Zahl genau einmal vorkommt.
Und dabei implizit vorausgesetzt, dass die Generatorbreite gleich der 
Ausgangsbreite ist. Das mag für ein direkt druchverdrahtetes LFSR 
stimmen, aber Yalu hat es ja schon angemerkt:
Yalu X. schrieb:
> bei den üblichen Algorithmen. Diese verwenden für die
> interne Berechnung meist die doppelte Bitzahl. Auf PCs wird also intern
> mit 64 Bit gerechnet, um eine 32-Bit-Pseudozufallszahl zu generieren.

Ungeachtet des Sinns oder Unsinns, (Pseudeo-)Zufallszahlen zur Identifi-
zierung von Produktexemplaren zu verwenden, ist hier noch eine Antwort
auf die ursprüngliche Frage:

Die Diagramme zeigen für eine gegebene Anzahl von 32-Bit-Zufallszahlen
die Wahrscheinlichkeit, dass sich darunter mindestens zwei gleiche
befinden. Man sieht, dass bei 10000 Zahlen die Wahrscheinlichkeit schon
über 1%, für 77000 etwa 50% und für 200000 sogar über 99% beträgt.

Für Großserienprodukte ist das Verfahren mit den Zufallszahlen ohne
spezielle Vorkehrungen zur Vermeidung von Dubletten also nicht geeignet.

Das ist eigentlich erstaunlich, weil die 200000 Zahlen gerade einmal
einen Anteil von 0,047 Promille der Gesamtanzahl (2³²) ausmachen. Das
Erstaunen legt sich aber wieder, wenn man das Geburtstagsparadoxon
kennt:

  http://de.wikipedia.org/wiki/Geburtstagsparadoxon

Warum muss das ne Zufallszahl und keine fortlaufende Seriennummer sein?