There are probabilistic programs that terminate with probability 1, but with an average of infinitely many steps.
-
-
Replying to @larsr_h
Is this equivalent to a random walk returning to its starting position?
1 reply 0 retweets 1 like -
Replying to @propensive
Yes. That was precisely the example the lecturer used.
2 replies 0 retweets 1 like -
Replying to @larsr_h
Ok, so maybe you could write a kind of parallel probabilistic program with infinite steps (average) which has a 34% chance of terminating...
2 replies 0 retweets 0 likes
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.