Bitfeld-Variationen

Neue Frage »

kekso Auf diesen Beitrag antworten »
Bitfeld-Variationen
Hallo, ich habe folgende Frage:

Ich habe ein 64 Bit langes Feld, innerhalb dieses Feldes können verschiedene Bits, als eine zusammenhängende Folge von Bits, gesetzt sein. Wenn ich jetzt von davon ausgehe das sämtliche Variationen also 1 Bit bis 64 Bit lange Folge gleichhäufig vorkommen, wie lang ist dann die mittlere Länge einer Bitfolge?
Wie ist dabei die Herangehensweise?

edit: wie verändert sich das Ergebnis wenn davon ausgegangen wird, das natürlicherweise 1 Bitfelder mehr Variationen haben als 8 oder 64 Bitfelder?
oder gibt es da kein Unterschied?

Gruß Kekso
AD Auf diesen Beitrag antworten »
RE: Bitfeld-Variationen
Zitat:
Original von kekso
Wenn ich jetzt von davon ausgehe das sämtliche Variationen also 1 Bit bis 64 Bit lange Folge gleichhäufig vorkommen, wie lang ist dann die mittlere Länge einer Bitfolge?

Bist du dir wirklich, wirklich sicher, dass du genau das meinst? Oder nicht vielleicht doch eher die Variante, dass jedes Bit unabhängig von den anderen mit gleicher Wkt 0 oder 1 annimmt?
kekso Auf diesen Beitrag antworten »
RE: Bitfeld-Variationen
Naja das Problem ist keines aus einem Lehrbuch oder ner anderen Aufgabenstellung sondern eins aus der Praxis.
Ich habe ein 64 Bit langes Bitfeld aus diesem können beliebige Anzahl (begrenzt durch die Länge 64) zusammenhängende Bits ausgewählt werden. das natürlich auch an beliebiger Stelle im Bitfeld. Nun will ich eine Abschätzung geben wie dabei die wahrscheinlich mittlere Länge eines ausgewählten Bitfeldes ist. ich hoffe das ist verständlich?
AD Auf diesen Beitrag antworten »

Das schon, aber nach welchen (stochastischen?) Gesetzmäßigkeiten wird das 64Bit-Feld gebildet? Das ist entscheidend für Beantwortung der Frage! Bei zufälligen Bitmustern liegt die Antwort knapp unter 2 (bei unendlich langem zufälligem Bitfeld wäre die Antwort genau 2).
kekso Auf diesen Beitrag antworten »

Zitat:
Wenn ich jetzt von davon ausgehe das sämtliche Variationen also 1 Bit bis 64 Bit lange Folge gleichhäufig vorkommen,


ich geh also von einer Gleichverteilung aus - aber ich glaube da reicht schon das arithmetische Mittel: also (64 + 1) / 2 = 32.5 also 33 da ein Bits nur 1 oder 0 sein kann.
AD Auf diesen Beitrag antworten »

Wenn du wirklich davon ausgehen kannst, dann ist 32.5 (nicht 33 - im Mittel können auch "halbe" Bits rauskommen!) richtig. Aber ich habe ja oben meine ernsten Zweifel angemeldet, wie eine solche Verteilung zustande kommen soll.
 
 
kekso Auf diesen Beitrag antworten »

Ja sicher ist die Annahme der Gleichverteilung ein bisschen weithergeholt, aber alle diskreten Werte zu erfassen würde vom Zeitaufwand her in keinerlei Relation stehen.

Aber noch zu den 32.5 Bits, das musst du mir zeigen wie man ein Bit in der Informatik noch weiter unterteilt Augenzwinkern .

Gruß kekso
AD Auf diesen Beitrag antworten »

Die mittlere Würfelaugenzahl ist 3,5. Wie würfelst du eine 3,5 ?

Also den Unterschied solltest du so langsam mal begreifen. Augenzwinkern
kekso Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Die mittlere Würfelaugenzahl ist 3,5. Wie würfelst du eine 3,5 ?

Also den Unterschied solltest du so langsam mal begreifen. Augenzwinkern


Da ich ja Eingangs schon mal erklärt hatte, das es sich hier um eine praktisches Problem und kein theorethisches handelt, denke ich hast du dir deine Antwort selber gegeben. Theorethisch sind 3.5 Augen möglich, aber praktisch hat diese Augenzahl noch keiner gewürfelt. Ich will mit diesem Wert von 33 (genau 32.5) Bit nur etwas verdeutlichen, NICHT weiterrechnen.

mathematisch korrekt aufgerundet bedeutet das:
AD Auf diesen Beitrag antworten »
RE: Bitfeld-Variationen
Dann erinnere ich dich an dein Ausgangsposting:

Zitat:
Original von kekso
Wenn ich jetzt von davon ausgehe das sämtliche Variationen also 1 Bit bis 64 Bit lange Folge gleichhäufig vorkommen, wie lang ist dann die mittlere Länge einer Bitfolge?

Und das hat nichts mit Unterschied von Theorie und Praxis zu tun, die mittlere Bitlänge ist 32,5, allenfalls die auf ganze Bit gerundete mittlere Bitlänge ist 33. Aber danach hattest du zunächst nicht gefragt. Augenzwinkern
kekso Auf diesen Beitrag antworten »
RE: Bitfeld-Variationen
Ok, dann habe ich es nicht bis in alle Einzelheiten spezifiziert. Aber es ging auch nicht unbedingt um die Tatsache das, dass Ergebniss nun 32.5 oder 33 ist, sondern um den Ansatz. Ich habe auch geschrieben das ich nur eine Abschätzung vornehmen will. Diese Abschätzung sollte nur als Grundlage einer Betrachtung dienen. Dabei ist eine Nachkommastelle nicht von Belang.

Was mich eigentlich an der Antwort gestört hat war dieser Kommentar:

Zitat:
Also den Unterschied solltest du so langsam mal begreifen.


Der Unterschied ist mir schon klar, nur eben nicht wichtig. Pi kann auch je nach Aufgabenstellung mit 3,14 oder weit mehr Stellen angegeben werden.

MFG kekso
AD Auf diesen Beitrag antworten »

Entschuldigung, wenn das beleidigend gewirkt hat. Aber in meiner Antwort vor deinem Einwurf "es gibt keine halben Bits" habe ich ausdrücklich auf das "mittlere" Bezug genommen. Und dann ärgert mich so ein sinnloser Einwurf.

Um zum Thema zurückzukommen: Deine Gleichverteilung auf 1..64 Bit ist schon etwas seltsam, sie bedeutet nämlich - wenn du genauer darüber nachdenkst - folgendes:

Jedes 64Bit-Wort darf höchstens zwei solche ununterbrochenen Bitfolgen enthalten, also von

00000000000000000000000000000000000000000000000000000000000000
00
0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000011
................................................................
0111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111


oder entsprechend noch

11111111111111111111111111111111111111111111111111111111111111
10
1111111111111111111111111111111111111111111111111111111111111100
................................................................
1000000000000000000000000000000000000000000000000000000000000000
kekso Auf diesen Beitrag antworten »

Entschuldigung angenommen.
Zum Thema: Genau aus diesem Grund habe ich mich an dieses Board gewendet - ich bin nicht so bewandert in Fragen der Stochastik.
Also natürlich ist diese Art der Verteilung Unsinn, die Verteilung der zusammenhängenden Bitbereiche kann auch folgendermaßen aussehen:

00000000000111111100000000000000000
00000110000000000000000000000000000
00000000000000000000000001000000000
00000111111111111111100000000000000
(nur examplarisch: nicht genau 64 Bit)

Wichtig dabei ist nur das, dass Bitfeld zusammenhängend ist!

Wie sieht denn in diesem Fall die Verteilungsannahme aus?


ps: kann leider erst morgen wieder reinschauen - schönen tag noch
AD Auf diesen Beitrag antworten »

Wenn die 64 Einzelbits wirklich "zufällig" (also jeweils mit Wkt. 1/2) die Werte 0 und 1 annehmen, und das unabhängig voneinander - also in Informatikersprache mit "random" erzeugt - dann ist die Länge der ersten ununterbrochenen Bitfolge "abgebrochen" geometrisch verteilt, d.h.



Mit ersten meine ich dabei, dass wirklich bei Bit 1 begonnen wird und nicht irgendwo in der Mitte des Bitfeldes. Dort muss das etwas angepasst werden.

Ein gutes Beispiel für solche scheinbar zufälligen Bitmuster sind komprimierte Dateien guter Komprimierer wie RAR oder ZIP (natürlich exklusive Header). Diese Bitfolgen sind zwar nicht zufällig, haben aber ähnliche statistischen Eigenschaften.

Die meisten üblichen Rohdaten wie ASCII-Texte o.a. passen hingegen nicht in dieses Modell.
kekso Auf diesen Beitrag antworten »

Ok, um ein bessere Wertung der auftretenen Bitfelder abzugeben müsste ich zu viele Daten untersuchen, wobei Aufwand und Nutzen in keinem Verhältnis stehen. Deswegen such ich eine "grobe" Abschätzung. Ich nehme mal an das die geometrische Verteilung gegenüber der Gleichverteilung dem wahrscheinlichen Wert näher kommt. Wie Berechne ich daraus die mittlere Länge eines zusammenhängenden 1-Bitfeldes?

Thx Kekso
AD Auf diesen Beitrag antworten »

Auf den ersten Blick erscheint es einfach zu sagen, was "mittlere Länge eines zusammenhängenden Blocks" bedeutet. Auf den zweiten Blick hingegen nicht:

Nehmen wir zunächst mal an, wir haben einen unendlichen Bitstrom. Das lässt sich einfacher rechnen und erklären als mit der 64-Bit-Begrenzung, außerdem unterscheidet sich das Ergebnis für 64 Bit dann gar nicht mehr so sehr von dem für unendlich viele Bits. Dann gibt es im wesentlichen zwei vernünftige Möglichkeiten, einen Block davon auszuwählen:

(1) Man wählt gleichberechtigt unter allen zusammenhängenden Blöcken einen aus.

(2) Man wählt gleichberechtigt irgendein Bit aus, und betrachtet dann den "rundherum" liegenden zusammenhängenden Block.

Beide Auswahlvarianten unterscheiden sich erheblich, denn bei Variante (2) kommen längere Blöcke öfter zur Auswahl als mit Variante (1) ! Bei rein zufälliger Bitverteilung (siehe mein letzter Beitrag) hat das zur Folge, dass nach Variante (1) die mittlere Blocklänge genau 2 beträgt, während es nach Variante (2) genau 3 ist. Die Begründung - ohne allzu ausführliche Rechnung - lautet so:

Bei Variante (1) geht es um den Erwartungswert der geometrischen Verteilung , und der ist nunmal .

Bei Variante (2) ist es ähnlich, nur dass man da zwei geometrische Blocklängenverteilungen hat: Eine vom ausgewählten Bit in Vorwärtsrichtung (Länge ) und eine in Rückwärtsrichtung (Länge ). Die Gesamtlänge des zugehörigen Blocks ist dann , denn das ausgewählte Bit darf ja nicht doppelt gezählt werden. Insgesamt ergibt sich somit .

Die entsprechenden Werte bei der Beschränkung auf 64Bit-Blöcke sind schon deutlich schwieriger zu berechnen, aber dennoch möglich. Das spare ich mir hier lieber, denn inhaltlich kommt da wenig neues bei raus, nur ziemlich eklige Summen, an deren Ende bei (1) ein Wert sehr wenig kleiner als 2 und bei (2) ein Wert sehr wenig kleiner als 3 stehen wird.
kekso Auf diesen Beitrag antworten »

Vielen Dank erstmal für deine sehr ausführliche Ausführung. Leider passt dieses Ergebnis nicht ganz zu meinen Beobachtungen der reellen Werte. Ich glaube es ist dann fast besser stichprobenartig die Längen zufällig ausgewählter Bitfelder zu entnehmen und daraus dann das arithmetische Mittel zu bilden.
Andere Möglichkeit wäre eine Gewichtung der Längen vorzunehmen. Ich denke aber dafür ist der Aufwand zu groß.

Gruß kekso
AD Auf diesen Beitrag antworten »

Wie gesagt: Wenn man keinerlei Informationen über die statistische Verteilung der auftretenden Bitmuster hat, kann man auch schwerlich was rechnen, bzw. diese Rechnungen sind dann ungenau. Nimm ein zufälliges Bitfeld, und dann wirst du sehen, dass meine Rechnung stimmt. Zu deinen Bitfeldern hast du ja außer

Zitat:
Original von kekso
00000000000111111100000000000000000
00000110000000000000000000000000000
00000000000000000000000001000000000
00000111111111111111100000000000000
(nur examplarisch: nicht genau 64 Bit)

keinerlei Angaben gemacht, und das ist dann doch etwas dürftig, nicht wahr? Also entweder du hast großes statistisches Zahlenmaterial, dann kannst du die mittlere Bitlänge durch statistische Auswertung selbst ermitteln. Oder du hast ziemlich präzise Angaben darüber, nach welchen Mechanismen (Algorithmen) deine Bitfelder entstehen, dann kann man auch theoretisch noch was rausholen.

Aber ohne Informationen gibt es nun mal keine zuverlässigen Ergebnisse, das sollte klar sein.
kekso Auf diesen Beitrag antworten »

Ist angekommen, leider habe ich weder das Eine noch das Andere. Ich hab zwar umfangreiches Zahlenmaterial, aber kein statistisches. Die statistischen Daten müsste ich erst daraus extrahieren, aber so entscheidend ist es dann auch wieder nicht.

Danke für den Ausflug in die Welt der Stochastik Freude

Gruß kekso
AD Auf diesen Beitrag antworten »

Zitat:
Original von kekso
Ich hab zwar umfangreiches Zahlenmaterial

Na das reicht doch, falls diese Daten repräsentativ für die Gesamtheit der zu betrachtenden Daten sind - nur das meinte ich mit "statistisch", nichts weiter.
Neue Frage »
Antworten »



Verwandte Themen

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