Byte Match Wahrscheinlichkeit

Neue Frage »

Max89 Auf diesen Beitrag antworten »
Byte Match Wahrscheinlichkeit
Meine Frage:
Ich versuche ne Formel aufzustellen wie hoch die Wahrscheinlichkeit ist, das X Bits in einem Byte (8 Bits) mit den Werten aus einem anderen Byte übereinstimmen. D.h. wir haben zwei zufällig generierte Zahlen (Binär und 8 Stellen lang) und wollen berechnen wie hoch die Wahrscheinlichkeit das X Stellen übereinstimmen. 0 Übereinstimmungen sind 1/256 => ~0.4% und 8 Übereinstimmungen ebenfalls 1/256 => ~0.4%. Doch wo liegen die Prozentzahlen bei 1-7 Übereinstimmungen? Welche Formel deckt alle Fälle ab?

Meine Ideen:
Keine sinnvolle Ideen und Ansaetze. Wenn ich welche hätte, würd ich selbst auf die Lösung kommen, und bräuchte die Frage nicht zu stellen Augenzwinkern
peda Auf diesen Beitrag antworten »

kann sein dass ich mich grad bissl wegtragen lass.. aber kann man das ganze nicht so betrachten?

ich habe 8 mögliche stellen wo eine übereinstimmung auftreten kann.
und jetzt will ich mir überlegen wie viele verschiedene möglichkeiten es gibt x übereinstimmungen auf die 8 "laden" zu verteilen (ich rutsch da in den kombinatorik slang smile sry)
also man hätte dann quasi x kugeln die auf 8 plätze verteilt werden sollen.

das entspricht doch eigentlich der formel einer auswahl einer teilmultimenge, nämlich

(8-1+x) über x . bei einer übereinstimmung gibts dann zb 8 möglichkeiten.

und das ergebnis k nimmt man noch 1/k dann hat man die wahrscheinlichkeit dass einer dieser fälle auftritt?

smile sehr weit aus dem fenster gelehnt
mfg
peda Auf diesen Beitrag antworten »

korrekterweise glaub ich müsste man statt 1/k dann wohl doch k/(2^8) also k/256 nehmen? dann komm ich auch auf die äusseren beiden 0,4% ca
Max89_2 Auf diesen Beitrag antworten »
Hm..
Danke für die schnelle Antwort. Es sind 8 Stellen und die Change bei einer einzelnen spezifischen Stelle richtig zu liegen betrifft 50% (0 oder 1). Die Change exakt 7 richtig zu haben liegt bei 8/256 (3.125%), da exakt eine Stelle falsch sein muss (was bei 8 Stellen 8 verschiedene Möglichkeiten ergibt). Die selbe Change gilt fuer exakt 1 Stelle richtig.

Somit die Liste:
0 von 8 => 1/256 (0.390625%)
1 von 8 => 8/256 (3.125%)
2 bis 6 von 8 => ?
7 von 8 => 8/256 (3.125%)
8 von 8 => 1/256 (0.390625%)

Doch Try and Error ist nicht die Lösung hier. Ich brauch die entsprechende Formel die alle Fälle abdeckt. Btw: Denke dein Ansatz mit den Kugeln macht keinen Sinn.
Kasen75 Auf diesen Beitrag antworten »

Hallo,

meine Idee ist die Binomialverteilung.

Mit freundlichen Grüßen.
Dopap Auf diesen Beitrag antworten »

hallo Max89 !

bleib bitte bei deinem ersten Namen unter dem du auch angemeldet bist.

Und wie schon gesagt: Binomialverteilung mit p=q=0.5 und n=8
 
 
peda Auf diesen Beitrag antworten »

Zitat:
Original von Kasen75
Hallo,

meine Idee ist die Binomialverteilung.

Mit freundlichen Grüßen.


ist das nicht ca. das was ich auch schon gesagt habe?

also eine allgemeingültige formel wäre dann



?
Kasen75 Auf diesen Beitrag antworten »

Hallo peda,

allein von den Werten her stimmt deine Formel nicht mit der Binomialverteilung überein.
Bei p=0,5 kann man die Binomialverteilung auf folgenden Ausdruck zusammendampfen (geht bei der Hitze ganz gut):



Diese Formel sieht schon mal ein bisschen anders aus als deine Formel.

Mit freundlichen Grüßen.
peda Auf diesen Beitrag antworten »

Zitat:
Original von Kasen75
Hallo peda,

allein von den Werten her stimmt deine Formel nicht mit der Binomialverteilung überein.
Bei p=0,5 kann man die Binomialverteilung auf folgenden Ausdruck zusammendampfen (geht bei der Hitze ganz gut):



Diese Formel sieht schon mal ein bisschen anders aus als deine Formel.

Mit freundlichen Grüßen.


hm ja ich glaube das was du schreibst is das was ich im endeffekt gerechnet hab. so wie ichs aufgeschrieben habe würden auch 2 bit an einer stelle erlaubt sein, was ja nicht geht.
hast natürlich recht smile
Max89 Auf diesen Beitrag antworten »

(8/k)/(2^8) und das k soll für die Anzahl richtigen Bits stehen? Euch ist wohl schon klar, dass das nicht aufgehen kann, oder? Der Ansatz mag ja richtig sein, doch da fehlt noch was. Die Frage ist nur 'was'?
peda Auf diesen Beitrag antworten »

nicht , und das geht eigentlich schon auf. rechnes doch mal nach, dann siehst dass es passen sollte smile
Max89 Auf diesen Beitrag antworten »

Und für was steht dann das ?
peda Auf diesen Beitrag antworten »

das ist der binomialkoeffizient.

also generell gilt:

und das n! ist n faktorielle bzw n fakultät:

in der kombinatorik bezeichnet n! die anzahl der möglichen permutationen von n unterscheidbaren elementen (deine stellen an denen eine übereinstimmung vorliegen kann)

was genau man rechnet ist mir zwar schon klar aber es ist für mich voll schwer das in worte zu fassen smile

auf jedenfall hast du oben im zähler deine gesamten permutationen von 8elementen
und im nenner einerseits die anzahl der elemente die du rausnehmen willst und den rest der überbleiben soll. ich überleg grade wie man das schön erklären könnte smile sry besser bring ich das auf die schnelle nicht hin.

im endeffekt hast du mit dieser formel aber dann amal die anzahl der möglichkeiten wie du aus 8 unterscheidbaren elementen 2 auswählen kannst. wobei die reihenfolge egal ist (übereinstimmung an stelle 5 und 2 ist ja das selbe wie an 2 und 5)

das ergebnis musst du jetzt durch die gesamtanzahl der möglichen binärzahlen mit 8 stellen dividieren dann weisst genau wieviele fälle prozentuell zur gesamtanzahl betroffen sind und tadaa du hast deine whs.

war das halbwegs verständlich? hoffe doch smile
mfg
Max89 Auf diesen Beitrag antworten »

Oh, das könnte passen. Ich rechne das gleich nach.
Besten Dank für die ausführliche Erklährung.
peda Auf diesen Beitrag antworten »

bitte gern, ich hab in 5 wochen prüfung und das ist im stoffgebiet smile also danke fürs fragen :P
Max89 Auf diesen Beitrag antworten »

Ja, stimmt alles soweit. Das war die Formel nach der ich suchte:

n!/k!/(n-k)!/(b^n)

n => Anzahl totale Ziffern (in meinem Fall 8)
k => Anzahl Ziffern die übereinstimmen (in meinem Fall ne Ganzzahl von 0 bis 8)
b => Anzahl Moeglichkeiten pro Ziffer (in meinem Fall 2 [0 oder 1])

Kann fuer jegliche herkömmliche Lotto-Varianten verwendet werden, um die mögliche Gewinne bzw. Langzeitverlust auszurechnen Augenzwinkern .
Dopap Auf diesen Beitrag antworten »

muss dich etwas bremsen.
1.)Lotto ist keine Binomialverteilung
2.) deine Formel gilt nur für b=2
Max89 Auf diesen Beitrag antworten »

Oh, sorry für die Fehlinformation und danke für die Korrektur.
War wohl etwas voreilig mit der Schlussfolgerung für das 'b'.
Dopap Auf diesen Beitrag antworten »

du könntest deine Formel mal umschreiben zu:



Zwar gilt immer noch b=2, aber es tritt schon optisch die Wahrscheinlichkeit 1/b und die Gegenwahrscheinlichkeit 1/b auf.

Als Modell für eine Erweiterung könnte man Toto ansetzen. n=12 b=3 ( 0,1,2)

Wie muss die Formel jetzt noch abgeändert werden?
wokey Auf diesen Beitrag antworten »

hallo ich weis nicht ob es weiter hilft..
aber du kannst die 2 bytes von denen du die stellen vergleich willst ein wenig umschreiben.
also zwei bytes
(x0,x1,...,x7)
(y0,y1,...,y7)

jetzt vergleicht man immer die bits mit den selben index.
da ergeben sich dann 4 kombinationen daraus pro bit
(xi,yi)=(0,0)
(xi,yi)=(0,1)
(xi,yi)=(1,0)
(xi,yi)=(1,1)

jetzt kann man das ganze als ein byte darstellen in dem jedes "bit" die wahrscheinlichkeit von 1/4 hat das es 1 ist. da es sich um 8bit handelt würde ich einfach mal sagen das 2 bits im schnitt
beide die werte 1 annehmen.
wokey Auf diesen Beitrag antworten »

ergänzung:
ich habe mich verlesen in deinen ersten beitragt.
du suchst alle stellen die yi xor zi ==0

also treffen 2 von den 4 paaren zu und es ergibt sich eine wahrscheinlich keit von 1/2
also sind im schnitt 4 von den 8 bit gleich.
ich weis das das nicht die eigentliche fragestellung beantwortet aber vielleicht bringt es ja jemanden auf eine idee.

lg wokey
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »