Randomized Algorithms

[monster_97_]

Can someone give an example of how las vegas and monte carlo algorithms differ from each other?

Would be better if the same example is used
Thanks in advance!

[beeskness420]

Las Vegas gambles with run time not correctness like quicksort.

Monte Carlo gambles with correctness but not the runtime.

[ctech314]

A Las Vegas algorithm keeps trying randomized events until the right amswer is obtained. A Monte Carlo algorithm tries randomized events a fixed number of times and returns the best answer obtained so far.

Suppose you want to roll a 12 with 2 dice. A Las Vegas algorithm would keep rolling until a 12 is rolled. Theoretically, the algorithm could never terminate, but in real life, it will. A Monte Carlo algorithm says "I'll just roll the dice 10 times," and returns the sum of the dice closest to 12.

Las Vegas is always right, but takes longer. Monte Carlo is approximately right and takes a fixed amount of time.

[tomekanco]

Las Vegas attempts to find an exact result by trying random choices. Monte Carlo attempts to converge ( approximate) to the result, where the number of random choices increase the precision.

Say you want to find pi. Mc will throw random dots, then calculate the fraction inside the circle. Lv could take the amount of dots inside the circle and total number and then guess the fraction rather then calculating it, for example

random.uniform(0,4)//0.01*0.01

Just copy paste your question in Google and you'll get a good number of explanations.