Algorithms For Dummies

  Using Randomized Algorithms 

     329

Don’t  confuse  the  Monte  Carlo  method  with  the  Monte  Carlo  algorithm.  The 

Monte Carlo method is a way to understand how a probability distribution affects 

a problem, whereas, as discussed previously, the Monte Carlo algorithm is a 

 randomized algorithm that isn’t guaranteed to reach a solution.

In a Monte Carlo simulation, you repeatedly sample the algorithm results. You 

store a certain number of results and then calculate statistics, such as the mean, 

and visualize them as a distribution. For instance, if you want to understand bet-

ter how reducing the size of the deck you’re drawing from can help you achieve 

better results (as in the previous Python script), you iterate the algorithm a few 

times and record the success rate:

import numpy as np

samples = list()

for trial in range(1000):

    my_cards = deck.copy()

    guessed = 0

    for card in deck:

        if card == choice(my_cards):

            guessed 

+= 1

        else:

            my_cards.pop(my_cards.index(card))

    samples.append(guessed)

Running  a  Monte  Carlo  simulation  may  take  a  few  seconds.  The  time  required 

depends on the speed of the algorithm, the size of the problem, and the number of 

trials. However, when sampling from distributions, the more trials you make, the 

more stable the result. This example performs 1,000 trials. You can both estimate 

and visualize the expected result (see Figure 17-3) using the following code:

plt.hist(samples, bins=8)

plt.xlabel("Guesses")

plt.ylabel("Frequency")

plt.show()

print ('On average you can expect %0.2f guesses each run'

       % np.mean(samples))

On average you can expect 3.15 guesses each run

Observing the resulting histogram, you can determine that you get a result of 

three in about 300 runs out of the 1,000 trials, which gives three the highest prob-

ability of happening. Interestingly you never got a result of zero, but it is also rare 

to score seven or more hits. Later examples in the chapter use Monte Carlo simu-

lations to understand how more sophisticated randomized algorithms work.

---

330