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!?
