 Terminierung probabilistischer Algorithmus |
Backwardsman
Grünschnabel
Dabei seit: 18.12.2006
Beiträge: 1
 |
|
| Terminierung probabilistischer Algorithmus |
     |
wie kann ich denn bei einem probabilistichen/randomisierten algrorithmus (wo ist da denn genau der unterschied) sagen/argumentieren/beweisen, dass er terminiert
mein algo. im pseudocode:
| code: |
1:
2:
3:
4:
5:
6:
|
n = 1
while(true){
if (getRandom() <= p) return n;
else n++;
} |
|
dabei beträgt die wahrscheinlichkeit p, dass das aktuelle n akteptiert wird:
0 < p < 0.5 (fest für alle n)
naja, irgendwie ist es schon offensichtich, p ist größer null also wird schon irgendwann mal ein n akzeptiert werden, aber wie kann ich das denn formal begründen!?
danke!
|
|
18.12.2006 15:16 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Nach meiner Ansicht terminiert dieser Algorithmus nicht zwangsläufig, da es eine Folge von Eingaben von Zufallszahlen (0,0,0,0,0.....) gibt, bei der die Abbruchbedingung nicht erfüllt wird.
Das ist aber bald schon eine philosophische Frage, weil man argumentieren könnte daß die Wahrscheinlichkeit von n=x mit x gegen Unendlich gegen 0 geht.
Effektiv ist die Größe von n eh durch den Variablentyp beschränkt, also kannst du mit einer zusätzlichen Abbruchbedingung nicht viel verkehrt machen.
Wenn es dir um eine geometrische verteilte Zufallsvariable geht, dann gibt es auch bessere Algorithmen dafür, die das ganze in konstanter Zeit berechnen, was bei grossen p sicherlich einen Zeitgewinn bedeutet.
Gruß,
ED209
while (true) halte ich übrigens sogar in c für schlechten Stil 
|
|
|
18.12.2006 17:05 |
|
|
abraxas 
Grünschnabel
Dabei seit: 14.09.2006
Beiträge: 9
Herkunft: D
|
|
Es gibt Stellen, an denen man eine nicht terminierende while-Schlaufe braucht, aber das ist hier sicherlich nicht der Fall (und while (true) ist sicher hässlich 
)
Warum addierst Du nicht einfach eine Zufallszahl zu n und gibst es dann zurück?
Diese Art von Inkrementierung einer Variable mit einer zufällig ausgerechneten boolschen Variable (darauf läuft das hier hinaus, weil Du den Zahlenwert nicht direkt benützt) bringt nur in solchen Kontexten was:
Denk an eine Linked List (ich weiß leider nicht, wie das auf deutsch heisst. Peinlich für den deutschboardler... ich weiß) in der Du eine bestimmte Menge an irgendwas gleichmässig verteilen willst... sagen wir eine Liste von Reisschalen, die alle zufällig viel Reis beinhalten, aber Du hast nur eine bestimme Gesamtmenge an Reis zur Verfügung.
Und auch da ist while (true) hässlich...
Hat das einen bestimmten Hintergrund, dass Du das so schreibst?
Grüße, abraxas
PS: die formale Begründung, dass das, was Du da hast, terminiert, gibt es mEn nicht. Denn solange der Zufall eine Rolle spielt, ist nichts zu beweisen. Es kann immernoch der böse Zufallsgott kommen, und Dir unendlich viele Nullen an den Kopf werfen.
__________________
Never trust an operating system you don't have sources for.
-- Unknown source
|
|
|
18.12.2006 18:32 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
| Zitat: |
Original von abraxas
Warum addierst Du nicht einfach eine Zufallszahl zu n und gibst es dann zurück?
|
Weil da eine andere Verteilung bei rauskommt. getRandom() soll vermutlich bei jedem Aufruf eine gleichverteilte Zufallszahl zwischen 0 und 1 ausspucken. getRandom() <= p ist ein Bernoulli-Experiment und die Schleife berechnet damit eine geometrisch verteilte Zufallsvariable.
Aber es gibt bessere Methoden das zu machen, bei Bedarf such ich mal genau raus wie.
Gruß,
ED
PS: Linked List nennt man auch verkettete List in Deutschland. Aber ich bin selbst kein großer Ventilator von deutschen Übersetzungen englischer Begriffe
|
|
|
18.12.2006 23:09 |
|
|
|
