Verteilung und Verteilungsfunktion einer Zufallsvariable bei der binären Suche

13.11.2010, 15:00	Zitrone21	Auf diesen Beitrag antworten »
Verteilung und Verteilungsfunktion einer Zufallsvariable bei der binären Suche Hallo zusammen, auf meinem aktuellen Stochastikblatt befindet sich eine Aufgabe zur binären Suche. Sei $\begin{eqnarray} n \in \mathbb{R} \end{eqnarray}$ und $\begin{eqnarray} d = 2^n -1 \end{eqnarray}$ . Geben sei eine Liste $\begin{eqnarray} (x_1, .., x_d) \end{eqnarray}$ geördneter Größen $\begin{eqnarray} x_1 < ... < x_d \end{eqnarray}$ . Gesucht wird die Position eines Elements y der Liste. Dazu wird der folgende Algorithmus verwendet: Algorithmus-Schritt: Vergleiche y mit dem mittleren Eintrag $\begin{eqnarray} x_{\frac{d+1}{2}} \end{eqnarray}$ der Liste $\begin{eqnarray} (x_1, .., x_d) \end{eqnarray}$ . Gilt $\begin{eqnarray} y = x_{\frac{d+1}{2}} \end{eqnarray}$ , so ist die Position bestimmt (Position $\begin{eqnarray} \frac{d+1}{2} \end{eqnarray}$ ) und der Algorithmus bricht ab. Gilt $\begin{eqnarray} y < x_{\frac{d+1}{2}} \end{eqnarray}$ , so bilde die Liste $\begin{eqnarray} (x_1, .., x_\frac{d-1}{2}) \end{eqnarray}$ aller Einträge kleiner als $\begin{eqnarray} x_\frac{d+1}{2} \end{eqnarray}$ und wiederhole den Algorithmus-Schritt mit dieser Liste. Gilt $\begin{eqnarray} y > x_{\frac{d+1}{2}} \end{eqnarray}$ , so bilde die Liste $\begin{eqnarray} (x_\frac{d+3}{2}, .., x_n) \end{eqnarray}$ aller Einträge größer als $\begin{eqnarray} x_{\frac{d+1}{2}} \end{eqnarray}$ und wiederhole den Algorithmus-Schritt mit dieser Liste. Dieser Schritt wird solange wiederholt, bis die Position von y bestimmt ist, d.h. bis der Algorithmus von sich aus abbricht. Nehmen Sie an, dass die Position des gesuchten Wertes y zufällig (gleichverteilt) in der Liste auftritt. DIe Zufallsvariable $\begin{eqnarray} N \end{eqnarray}$ gebe die Anzahl der Schritte an, die der Algorithmus braucht, um y zu finden. Aufgaben: a) Geben Sie die maximale ANzahl von benötigten Schritten zum AUffinden von y an. b) Bestimmten SIe die Verteiliung und die Verteilungsfunktion $\begin{eqnarray} F_N \end{eqnarray}$ der Zufallsvariablen $\begin{eqnarray} N \end{eqnarray}$ Meine Lösungen bisher: a) Wir betrachten wir den Worst-Case des Suchalgorithmus. Der ist erreicht, wenn wir die Liste so oft in zwei Teile geteilt haben, das am Ende nur noch eine Liste mit einem Element übrig bleibt. Dabei ist es egal, ob dieses Element dann y ist oder nicht. Die Anzahl der Elemente in der Liste sind ja $\begin{eqnarray} d = 2^{n-1} \end{eqnarray}$ und da der Algorithmus die Liste immer halbiert betrachten wir hier eine logarithmische Anzahl (zur Basis 2) an maximalen Schritten. Dabei gilt: $\begin{eqnarray} 2^{n-1} = 2 2 * ... * 2 \end{eqnarray}$ (also n-1 Faktoren) D.h. wir können die Liste $\begin{eqnarray} n-1 \end{eqnarray}$ -mal halbieren, sodass am ende eine Liste mit zwei Elementent übrig bleibt. Teilen wir anschließend nocheinmal, dann haben wir eine Liste, die nur noch aus einem Element besteht. D.h. die Anzahl der benötigten Schritte ist maximal $\begin{eqnarray} log(d) + 1 = (n-1)+1 = n \end{eqnarray}$ b) Hier wirds für mich jetzt so schwierig, das ich festhänge, das schlussendlich der Grund für diesen Thread ist: Die Zufallsvariable N gebe die Anzahl der Schritte an, die der Algorithmus nraucht um y zu finden. $\begin{eqnarray} N : \Omega \mapsto \left\{ 1, ..., n\right\} \end{eqnarray}$ wobei ich $\begin{eqnarray} B := \left\{ 1, ..., n\right\} \end{eqnarray}$ bezeichne Zu zeigen: 1) Verteilung von $\begin{eqnarray} N \end{eqnarray}$ 2) Verteilungsfunktion $\begin{eqnarray} F_N \end{eqnarray}$ zu 1)* $\begin{eqnarray} P^N : \mathcal{P}(\Omega) \mapsto \left[0,1\right] \end{eqnarray}$ Sei $\begin{eqnarray} B' \subset B \end{eqnarray}$ $\begin{eqnarray} P^N(B') = P(N^{-1}(B') \end{eqnarray}$ Hier hörts bei mir leider auf. Ich weiß z.B.: nicht, wie ich $\begin{eqnarray} \Omega \end{eqnarray}$ richtig modellieren muss. Da ja hier von einer Gleichverteilung ausgegangen wird, benötige ich ja $\begin{eqnarray} \|\Omega\| \end{eqnarray}$ , für den Nenner. Außerdem ist mir nicht klar, was ich in den Zähler schreiben muss. Da ich ja gesagt habe, das die Anzahl der benötigten Suchschritte logarithmisch ist, muss ja auch irgendwie gelten, das die Wahrscheinlichkeit für steigene Werte von N exponentiell zunehmen muss, bis sie schließlich für $\begin{eqnarray} N = n \end{eqnarray}$ 1 sein muss. Doch wie genau modelliere ich das? zu 2) $\begin{eqnarray} F_N(x) : \mathbb{R} \mapsto \left[0,1\right] \end{eqnarray}$ $\begin{eqnarray} F_N(x) := P(Y \leq x) \end{eqnarray}$ Habe ich damit die Verteilungsfunktion schon ausreichend angegeben? Auf jeden Fall würde ich mir diese auch gerne zeichnen. Mir ist klar, das $\begin{eqnarray} \lim_{x \to \infty } F_N(x) = 1 \end{eqnarray}$ gilt. Jedoch brauche ich um die Verteilungsfunktion aufzustellen ja die entsprechenden Werte der Verteilung, damit ich die Sprunghöhen bei dieser Treppenfunktion einzeichnen kann. Oder mache ich hier was falsch?
13.11.2010, 15:44	Zitrone21	Auf diesen Beitrag antworten »
Ich bin bei meiner Suche noch auf ne gute Idee gestoßen: $\begin{eqnarray} \|\Omega\| \end{eqnarray}$ müsste ja dann die Anzahl aller möglichen Elemente in der Liste sein, also $\begin{eqnarray} \|\Omega\| = 2^{n-1} \end{eqnarray}$ Dabei kann ich pro Rekursionsschritt die doppelte Anzahl an Elementen durchsuchen. D.h. pro Schritt habe ich auf $\begin{eqnarray} 2^{x-1} \end{eqnarray}$ Elemente zugegriffen? (naja, zugegriffen ist hier das falsche Wort), wobei x die Anzahl des Schrittes angibt. Also müsste meine Verteilungsfunktion sein: $\begin{eqnarray} F_N(x) = \frac{2^{x-1}}{\|\Omega\|} = 2^{x-n} \end{eqnarray}$ für $\begin{eqnarray} x < n \end{eqnarray}$ , bzw $\begin{eqnarray} 1 \end{eqnarray}$ für $\begin{eqnarray} x \geq n \end{eqnarray}$ Ist das richtig? Obwohl ich nun auf $\begin{eqnarray} \|\Omega\| \end{eqnarray}$ gestoßen bin, wüsste ich nicht, wie ich $\begin{eqnarray} \Omega \end{eqnarray}$ zu modellieren hätte. Weiterhin bleibt offen, wie die Verteilung aussieht :-\|

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »