Bitweise XOR-Verknüpfung

Hallo Zusammen,

im Gegensatz zu bitweiser UND-Operation oder ODER-Operation ergibt die bitweise XOR-Verknüpfung unendlich vieler Zufallszahlen wiederum eine Zufallszahl. Dies liegt ja an der "Gleichmäßigkeit" (mir fällt keine andere Bezeichnung ein) der Funktion. Jetzt meine Frage: Gibt es einen mathematischen Begriff, der diesen Sachverhalt erklärt/erläutert.

Peter

p.s.: Ich wusste nicht, in welches Forum ich das Thema packen sollte. Einfach verschieben, wenn in unpassender Kategorie.

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C (C89 und C99) in das Forum Mathematik und Physik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

SG1

Meinst Du wirklich "unendlich", oder meinst Du "beliebig"? Und wenn Du unendlich meinst: Hast Du da 'nen Grenzwertprozess im Kopf, oder wie soll ich mir das vorstellen?

SeppJ

SG1 schrieb:

Meinst Du wirklich "unendlich", oder meinst Du "beliebig"? Und wenn Du unendlich meinst: Hast Du da 'nen Grenzwertprozess im Kopf, oder wie soll ich mir das vorstellen?

Eigentlich geht das sogar mit 2 (oder streng genommen mit einer, aber das ist langweilig :p ). Aber ein mathematisches Schlagwort dazu fällt mir auch nicht ein. Es bleibt halt für jedes Bit die Wahrscheinlichkeit auf gesetzt/ungesetzt 50%, wenn sie bei den Zahlen vorher schon 50% war, wie man an der Wahrheitstabelle von XOR ablesen kann. Vielleicht gibt es irgendeinen Symmetrie- oder Entropiebegriff dafür.

SG1 schrieb:

Meinst Du wirklich "unendlich", oder meinst Du "beliebig"? Und wenn Du unendlich meinst: Hast Du da 'nen Grenzwertprozess im Kopf, oder wie soll ich mir das vorstellen?

Ich meinte tatsächlich unendlich / sehr viele Zufallszahlen (z.B. mit jeweils 64-Bit-Länge). Der Begriff Grenzwert trifft den Sachverhalt schon ganz gut. Würde man die Zufallszahlen alle UND verknüpfen, wäre der Grenzwert eine Zahl bestehend aus nur aus 0-Bits (000...000), bei ODER-Verknüpfungen wäre dies genau umgekehrt (111...111).
Werden XOR-Verknüpfungen benutzt, ist solch ein Grenzwert generell nicht auszumachen, die erzeugte Zahl wäre daher auch eine Zufallszahl.

Ich hoffe, das macht die Sache ein bisschen klarer. Ich suche halt einen Begriff, der diese Eigenschaft des XORs beschreibt.

SG1

Peter1654 schrieb:

SG1 schrieb:

Meinst Du wirklich "unendlich", oder meinst Du "beliebig"? Und wenn Du unendlich meinst: Hast Du da 'nen Grenzwertprozess im Kopf, oder wie soll ich mir das vorstellen?

Ich meinte tatsächlich unendlich / sehr viele Zufallszahlen

Du meinst also NICHT unendlich, sondern beliebig viele. Wichtiger Unterschied! Aber ein Begriff fällt mir dazu auch nicht ein, sorry

Michael E.

Wie wärs mit verteilungserhaltende Operation?

Bashar

Verteilungserhaltend ist sie ja nicht. Die Wahrscheinlichkeit, dass die XOR-Verknüpfung einer Folge von Bits 1 ist, geht (von pathologischen Fällen wie wenn die Einzelwahrscheinlichkeiten alle 0 oder 1 sind abgesehen) gegen 0.5. Das sagt mir jedenfalls meine Intuition und ein paar kleine Experimente

Kann man also mit XOR den Zufall verbessern?

Michael E.

Bashar schrieb:

Verteilungserhaltend ist sie ja nicht. Die Wahrscheinlichkeit, dass die XOR-Verknüpfung einer Folge von Bits 1 ist, geht (von pathologischen Fällen wie wenn die Einzelwahrscheinlichkeiten alle 0 oder 1 sind abgesehen) gegen 0.5. Das sagt mir jedenfalls meine Intuition und ein paar kleine Experimente

Ich verstehe nicht, was du sagen willst. Seien zwei uniform zufällige Zahlen gegeben. Die XOR-Verknüpfung der beiden Zahlen erzeugt wieder eine uniform zufällige Zahl, da jedes Bit mit Wahrscheinlichkeit 1/2 gesetzt ist.

Edit: Klappt aber leider nicht mit allen Verteilungen. Also blödes Wort

Bashar

Michael E. schrieb:

Bashar schrieb:

Verteilungserhaltend ist sie ja nicht. Die Wahrscheinlichkeit, dass die XOR-Verknüpfung einer Folge von Bits 1 ist, geht (von pathologischen Fällen wie wenn die Einzelwahrscheinlichkeiten alle 0 oder 1 sind abgesehen) gegen 0.5. Das sagt mir jedenfalls meine Intuition und ein paar kleine Experimente

Ich verstehe nicht, was du sagen willst.

Sei eine Folge x_1, x_2, ... von Bits gegeben, und seien p_1, p_2 ... die Wahrscheinlichkeiten, dass das jeweilige Bit 1 ist. Dann geht die Wahrscheinlichkeit dafür, dass x_1 ^ x_2 ^ ... = 1 ist, unabhängig von den p's gegen 1/2.