Verteilung von 500 Zufallswerten von 0-1500; wie viele Überschneidungen?

19.01.2009, 10:39

HSE

Verteilung von 500 Zufallswerten von 0-1500; wie viele Überschneidungen?

Moin!
Ich habe mal ein Problem, das sich nicht aus einer Aufgabe herleitet sondern eher praktischer Natur ist.
Für ein Funksystem was ich gerade entwickle muss die Steuereinheit die Möglichkeit haben, alle "Endgeräte" kennen lernen zu können. Dazu wird ein Befehl "Meldet euch" per Funk geschickt. Die Endgeräte berechnen nun aus diversen Werten einen pseudo-Zufallswert X zwischen 0 und 1500. Dieser Wert gibt den Zeitpunkt in Millisekunden an, wann sich das entsprechende Gerät beim "Master" melden wird.
Sollten zwei Endgeräte zufällig die gleiche Wahl treffen, werden beide Funknachrichten verworfen.
Nach der Prozedur teilt der Master den Endgeräten mit, welche von ihnen er erkannt hat und wiederholt die Prozedur mit X zwischen 0 und X/2.
Damit das Verfahren richtig abgeschlossen werden kann, müssen mehr als 1/2 der antwortetenden Endgeräte ihren Funkbefehl ohne Störung absetzen können.

Daher meine Frage: Wie kann ich ausrechnen wie viele Geräte bei Geräteanzahl Z und verfügbaren "Funkslots" X im Schnitt erfolgreich ihre "ich bin da"-Nachricht absetzen können? Und wie kann ich die Wahrscheinlichkeit berechnen, dass (nur) genau Y Geräte erfolgreich sind?

Ich hab mir schon einiges angesehen, z.B. Würfeln mit 3 Würfeln, welche Wahrscheinlichkeit für mindestens 2 gleiche Augenzahlen usw aber ich komme nicht weiter da dort meist die günstigen und ungünstigen Ergebnisse "abgezählt" werden, das scheint bei meinem Problem nicht so einfach zu sein. Gibts da eventuell eine Verallgemeinerung?

Danke für jeden Denkanstoß,

- Tobi

19.01.2009, 16:36

Auf diesen Beitrag antworten »

Du solltest mal deine Symbolik ordnen: Es ist dem Verständnis nicht förderlich, wenn du X einmal als Zufallsgröße der zugeordneten Nummer und das andere Mal als feste Anzahl der verfügbaren Funkslots verwendest...

Egal, es ist in etwa klar, was du meinst: Du suchst die Verteilung der Anzahl der "nur einfach" vergebenen Nummern. Oder zumindest Charakteristika (wie z.B. Erwartungswert) dieser Verteilung.

Explizit sehe ich da bisher keinen vernünftigen Zugang, aber vielleicht bin ich da momentan auch nur zu blind.

Rekursiv kann man allerdings sofort loslegen, indem man sukzessive die Nummern zuteilt. Sei $\begin{eqnarray*} s \end{eqnarray*}$ die Anzahl der verfügbaren Funkslots sowie

$\begin{eqnarray*} p_n(m,k) \end{eqnarray*}$ ... Wkt. für genau $\begin{eqnarray*} m \end{eqnarray*}$ vergebene Nummern, darunter genau $\begin{eqnarray*} k \end{eqnarray*}$ einfach vergeben, bei insgesamt $\begin{eqnarray*} n \end{eqnarray*}$ Nummernvergaben

Dann lässt sich schnell eine rekursive Berechnungsvorschrift für $\begin{eqnarray*} p_n(m,k) \end{eqnarray*}$ angeben:

$\begin{eqnarray*} p_{n+1}(m,k) = \frac{1}{s} \left[ (s-m+1)p_n(m-1,k-1) + (k+1)p_n(m,k+1) + (m-k)p_n(m,k) \right] \end{eqnarray*}$

Zusammen mit diversen Start- bzw. Randwerten lässt sich dann numerisch direkt loslegen. Das $\begin{eqnarray*} m \end{eqnarray*}$ ist eine für diese Rekursion nötige Hilfsgröße, denn eigentlich ist man an der Wkt.

$\begin{eqnarray*} q_n(k) = \sum_{m=k}^n p_n(m,k) \end{eqnarray*}$ ... Wkt. für genau $\begin{eqnarray*} k \end{eqnarray*}$ nur einfach vergebene Nummern bei insgesamt $\begin{eqnarray*} n \end{eqnarray*}$ Nummernvergaben

interessiert, die fällt dann bei der Berechnung mit ab.

Der Speicherbedarf dieses Algorithmus ist $\begin{eqnarray*} O(n^2) \end{eqnarray*}$ , der Aufwand $\begin{eqnarray*} O(n^3) \end{eqnarray*}$ . Wird natürlich alles hinfällig, wenn jemand doch was explizites findet, aber bisweilen...

Nachtrag: Hab mal gemäß obiger Rekursion ein bisschen gerechnet - für Z=500 Anmeldeversuche und X=1500 Funkslots ergibt sich für die Anzahl Y erfolgreicher Anmeldungen

Erwartungswert $\begin{eqnarray*} E(Y) = 358.465 \end{eqnarray*}$

Standardabweichung $\begin{eqnarray*} \sqrt{\operatorname{var}(Y)} = 12.593 \end{eqnarray*}$ .

19.01.2009, 23:09

Zahlenschubser

Auf diesen Beitrag antworten »

RE: Verteilung von 500 Zufallswerten von 0-1500; wie viele Überschneidungen?
Ich habe die Problemstellung nicht ganz verstanden, aber gibt es eine bestimmte Verteilung, nach der die Zufallszahlen gezogen werden? Mein Problem ist der darauf folgende Satz in deiner Beschreibung, dass dies irgendetwas mit der Dauer bis zur Meldung zu tun hätte.

Wenn eine konkrete Verteilung vorliegt, könnte man das auf Basis dieser geschlossen bestimmen (denke ich).

19.01.2009, 23:11

Auf diesen Beitrag antworten »

Zitat:

Original von Zahlenschubser
aber gibt es eine bestimmte Verteilung, nach der die Zufallszahlen gezogen werden?

Ich bin von diskreter Gleichverteilung ausgegangen - wie üblicherweise in solchen Fällen. Und natürlich unabhängig voneinander (die Funkteilnehmer kennen sich vorher nicht).

19.01.2009, 23:16

Zahlenschubser

Auf diesen Beitrag antworten »

Macht absolut Sinn aus meiner Sicht, aber ich verstehe halt den Hinweis mit den Millisekunden nicht...

Zitat:

Die Endgeräte berechnen nun aus diversen Werten einen pseudo-Zufallswert X zwischen 0 und 1500. Dieser Wert gibt den Zeitpunkt in Millisekunden an, wann sich das entsprechende Gerät beim "Master" melden wird.

Ist der Master in der Lage die Funkeingänge im Millisekundenbereich auseinander zu halten? Oder wie ist das gemeint?

Und wenn man das mal komplett ignoriert, ist das denn nicht praktisch das Geburtstagsproblem?

19.01.2009, 23:31

Auf diesen Beitrag antworten »

Ich hab's ignoriert und mich nur an das gehalten:

Zitat:

Original von HSE
Sollten zwei Endgeräte zufällig die gleiche Wahl treffen, werden beide Funknachrichten verworfen.

Zitat:

Original von Zahlenschubser
Und wenn man das mal komplett ignoriert, ist das denn nicht praktisch das Geburtstagsproblem?

Beim Geburtstagsproblem geht es meines Wissens nach nur darum, ob es Mehrfachtreffer gibt. Hier dagegen wird nach der Verteilung der Anzahl der Einzeltreffer gesucht - das ist schon ein bisschen mehr. Das Geburtstagsprobem ist lediglich der Spezialfall $\begin{eqnarray*} q_n(n) \end{eqnarray*}$ bzw. $\begin{eqnarray*} 1-q_n(n) \end{eqnarray*}$ (s.o.).

19.01.2009, 23:41

HSE

Auf diesen Beitrag antworten »

Hi!
Danke für die fixe Hilfe. Ich hatte zwischenzeitlich auch ein kleines Progrämmchen gebaut, das die Werte einfach mit je 2000 Durchläufen statistisch ermittelt hat. Stimmt vor dem Komma ziemlich gut überein smile

[ot]

Und ja, die Funkpakete werden im Prinzip im Millisekunden-Takt abgesetzt. Real belegt ein Befehl etwas mehr Zeit (3ms) bis die anderen Teilnehmer ihn empfangen und daraufhin ihre internen Zähler unterbrechen bis der Befehl des "fremden" komplett verschickt wurde. Innerhalb dieser Zeit können jedoch Kollisionen auftreten - aus dem Grund die Vereinfachung auf 1ms pro Funkbefehl. Real rechne ich auch nicht mit 1500ms sondern mit 5000, um da noch etwas Spielraum zu haben.
Das Protokoll sieht vor diese Zeit jeweils nach einem Durchgang zu halbieren. Die Anzahl der "entdeckten" Funksender muss dann also > 60% liegen, damit die Sache funktioniert.
Experimentell (Simulation durch PC-Software) funktioniert das ganze relativ gut und ich habe z.B. bei 500 Sendern mit dem Wert 5000 noch 3-4 Durchläufe "Reserve" in denen ich verbliebene Module noch aufspüren kann.

Die gesamte für die Suche notwendige Zeit ist dann:
n = 12
$\begin{eqnarray*} \sum_{k=1}^n~5000 / k \end{eqnarray*}$
Das ganze konvergiert für n = INF gegen 2 * t = 10000ms.
Dazu kommt die Zeit die ein Funkbefehl jeweils dauert (ca. 15ms) die natürlich addiert werden muss (hier 500 * 15ms) und die Zeit die der Master braucht um die Sender zu informieren das sie entdeckt wurden (jeweils 3ms pro Empfänger).
Zusammen ergibt sich also:
10000ms + (15ms + 3ms) * 500 = 19 Sekunden.
Um 500 Geräte zu finden finde ich das durchaus akzeptabel.

So viel zum Hintergrund falls es jemand interessiert..

[/ot]

Gruß,

Tobi

Neue Frage »

Antworten »

Verteilung von 500 Zufallswerten von 0-1500; wie viele Überschneidungen?

Verwandte Themen