Periodische Wahrscheinlichkeit < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:08 Fr 13.01.2012 | | Autor: | Aslan |
Hallo zusammen,
ich versuche momentan einen zeitabhängigen Algorithmus zu optimieren.
Ich habe eine große Menge mit Elementen A und eine vergleichsweise kleine Teilmenge B.
Der Algorithmus wählt nun T (Zeit) Mal ein zufälliges Element aus der Menge A. Danach wird geprüft, ob sich das Element E auch in der Menge B befindet und schließlich eine Operation darauf ausgeführt.
Hier sieht man ja schnell, dass der Aufwand linear mit der Zeit zunimmt.
Da mich im Grunde genommen aber nur die Elemente aus B interessieren und B eine recht kleine Menge darstellt, dachte ich mir folgendes:
* Ich berechne eine Art statistischen Mittelwert, welcher angibt, wie oft ein Element aus B im Schnitt abhängig von der Zeit getroffen wird.
* Nun iteriere ich lediglich alle Elemente aus B und führe Mittelwert-Mal die Operation für jedes Element aus
Soweit so gut. Leider scheitere ich kläglich an der Berechnung besagten Mittelwertes.
Kann mir hier jemand auf die Sprünge helfen?
Viele Grüße
Aslan
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:21 So 15.01.2012 | | Autor: | felixf |
Moin Aslan!
> ich versuche momentan einen zeitabhängigen Algorithmus zu
> optimieren.
>
> Ich habe eine große Menge mit Elementen A und eine
> vergleichsweise kleine Teilmenge B.
>
> Der Algorithmus wählt nun T (Zeit) Mal ein zufälliges
> Element aus der Menge A. Danach wird geprüft, ob sich das
> Element E auch in der Menge B befindet und schließlich
> eine Operation darauf ausgeführt.
Eine Frage: wie verhaelt sich die Groesse $T$ in Bezug zu $|A|$? Ist $|A|$ viel groesser als $T$? Oder ist $T$ viel kleiner als $|A|$? Oder sind beide etwa gleich gross?
Und was meinst du mit "waehlt zufaelliges Element aus der Menge $A$"? Sind die Wahlen jeweils unabhaengig? Und hat jedes Element die gleiche Wahrscheinlichkeit, gewaehlt zu werden? Ich nehme mal an, dass die Antwort beides Mal "ja" ist.
> Hier sieht man ja schnell, dass der Aufwand linear mit der
> Zeit zunimmt.
![[ok]](/images/smileys/ok.gif "[ok]")
> Da mich im Grunde genommen aber nur die Elemente aus B
> interessieren und B eine recht kleine Menge darstellt,
> dachte ich mir folgendes:
>
> * Ich berechne eine Art statistischen Mittelwert, welcher
> angibt, wie oft ein Element aus B im Schnitt abhängig von
> der Zeit getroffen wird.
Die Wahrscheinlichkeit, dass ein spezielles Element aus der Menge $A$ getroffen wird, ist [mm] $\frac{1}{|A|}$. [/mm] Wenn du das also $T$-mal machst, ist der Mittelwert [mm] $\frac{T}{|A|}$.
[/mm]
> * Nun iteriere ich lediglich alle Elemente aus B und
> führe Mittelwert-Mal die Operation für jedes Element aus
Das liefert dir einen anderen Algorithmus. Du gehst hier davon aus, das alle Elemente aus $B$ gleichoft getroffen werden: das ist zwar Idealerweise so, aber tritt in der Realitaet nur mit verschwindend geringer Wahrscheinlichkeit ein.
Wenn du etwas mehr ueber das ganze Problem verraetst (einmal ueber die Relation von $|A|$ zu $T$) koennen wir versuchen dir zu helfen das Problem besser zu loesen.
LG Felix
|
|
|
|
