week 2

• Monte Carlo Simulation


  Numerical solution method involving random numbers, to estimate quantities which cannot be calculated by a mathematical equation or formula
• Write ten numbers down


  1. Between 1 and 100

  2. Any order
• Uniform Random numbers


  • Used to create variability
  • Truly random sequence (can't predict next number, no pattern or mathematical formula for it)
  • Computers use algorithmic random number generators to create a "stream" of random numbers: but there are other types!
• Random number generators


  • Formula is called a random number generator
  • Gives stream of numbers between 0 and 1
  • Number streams pass statistical tests for randomness
  • Numbers are called pseudo random
• Sampling from distributions


  1. Suppose you want to model the time it takes a chilled-food truck to make its daily journey from the distribution centre to a supermarket

  2. The journey time depends on many factors (traffic, road conditions etc)

  3. Need to choose a probability distribution function (PDF) to describe the journey time

  4. Each day's journey time is then obtained by sampling (picking a value) from the domain of this distribution
• The domain of a PDF


  The domain of a PDF is the set of values which it can take, i.e. the set of possible outcomes or random space
• Uniform PDF


  • Journey time can take anything between 30 and 40 minutes, all values equally likely
• Triangular PDF


  • Min = 30, most likely = 33, max = 40
• Sampling (intuitive definition)


  • In both cases we want to pick a value on the line between 30 and 40
  • The chance of picking a given value is proportional to the probability (the height of the shaded area above that point)
  • We are therefore more likely to pick values with high probability
• Triangular PDF


  • Most likely to pick this value
  • Unlikely to pick this value
• Uniform PDF


  • Equally likely to pick any value
• The party


  • There are three drinks available at a party: beer, wine, and lemonade
  • Each time you fill your glass, the probability that you choose beer is 50%, wine is 40%, lemonade is 10%
  • Sampling from this distribution is the same as deciding what to drink each time, assuming this is independent of what you have already drunk
• The PDF


  • Beer 50%, Wine 40%, Lemonade 10%
• The CDF


  • Beer 50%, Wine 90%, Lemonade 100%
• Sampling


  1. Generate a uniform random number u, and see where the line through u parallel to the "x"-axis hits the CDF

  2. If 1 <= u <= 50, choose beer

  3. If 51 <= u <= 90, choose wine

  4. If 91 <= u <= 100, choose lemonade
• Exercise: Based on the random number you wrote down at the start of this session, what drink did you simulate?
• Discrete & continuous domains


  • Discrete: a finite (set) number of distinct outcomes
  • Continuous: an infinite number of possible outcomes
• Continuous PDFs: Inverting the CDF


  • The same method works, as long as we can invert the CDF
  • Whereas for a discrete distribution we allocate a range of random numbers to a each event, for continuous distributions, we allocate a random number to each value
• Exponential distribution


  • Used to model time between events
  • Where μ is the mean (and standard deviation)
• Sampling from an exponential PDF

  1. This is called 'inverting the CDF'

  2. Normally use u instead of 1 - u, since both are random numbers in [0,1]; variable 1 - u is a mirror image of u

  3. So x = -ln(u)
• Other distributions
• Monte Carlo simulation


  • Named after the famous gambling resort
  • Numerical solution method involving random numbers, to estimate quantities which cannot be calculated by a mathematical equation or formula
  • Need not involve computers, although it usually does
• Example


  • Estimating the area of an irregular shape for which there is no mathematical formula such as
  • Direct method: enclose area inside a square, and cover square with 10 by 10 grid
  • Count number of orange squares (need to decide what to do with partial squares)
  • Area = Number of orange squares / 100
• Monte Carlo simulation approach


  1. Shoot darts at square at random

  2. Dart lands inside orange area: a hit

  3. Dart lands outside orange area: a miss

  4. Repeat lots of times

  5. Area = Number of hits / Number of shots
• The underlying maths


  • A pair of random numbers between 0 and 1 represent the (x, y) coordinates of the point X
  • This represents a binomial distribution, where each dart is a "trial" and p, the probability of success, equals the proportion of the square which is orange
  • Trade-off between speed and accuracy: the more shots, the more accurate the estimate
• Inventory Control


  • An electrical wholesaler has recorded the weekly demand for vacuum cleaners over the last 50 weeks
  • Weekly Demand: 100 (10 weeks), 150 (15 weeks), 200 (15 weeks), 250 (8 weeks), 300 (2 weeks)
  • The wholesaler wishes to explore the possibilities of changing his ordering policy
  • Currently he orders 400 cleaners at the end of the week provided he has 200 or fewer cleaners in stock
  • It costs the retailer £250 to place an order, and storage costs are £0.40 per week per cleaner
  • Using the following random numbers, u, where 0 ≤ u < 100, simulate 7 weeks demand and calculate the average order cost, the average stock holding cost and the average total cost. You may assume that he starts the simulation with 300 cleaners in stock.
• Distribution of Demand


  • Weekly Demand: 100 (20%), 150 (30%), 200 (30%), 250 (16%), 300 (4%)
• Application areas for Monte Carlo simulation
• Critical path method


  1. List all the activities, their durations and prerequisites

  2. Draw a project network representing the logical connections between the activities

  3. Identify the critical path

  4. The project manager can then specify start and end dates for all the activities, and ensure all the required resources are available at the right time
• Project network


  • Activities = arcs (arrows): network shows logical connections between activities
  • Node 1 = start node; node 4 = end node
• Paths


  • There are two paths through the network: A-C-D (length 2 + 4 + 1 = 7) and B-D (length 1+1 =2)
  • The critical path is the longest path through the network: in this case, A-C-D
• The critical path


  • The critical path tells us how long the whole project will take (in this case 7 days)
  • Activities on the critical path must start on time, or else the whole project will be delayed
  • To complete the project, we must complete every activity
  • We have some slack for activities off the critical path: e.g. we have 6 days to do activity B, although it only takes one day
• Drawbacks of the critical path method
• The solution – simulation!


  1. Monte Carlo simulation: the network is static, even though the project evolves over time

  2. Replace fixed activity durations with appropriate probability distributions

  3. Can capture all the variability and uncertainty of the real world

  4. Can model alternative chains of activities
• Chair project example


  • A and D still have known, fixed durations
  • B has a triangular distribution with min 1, most likely = 4 and max = 10
  • C has a uniform distribution between 2 and 6
• Use of MCS


  • Gives information tailored to the risk appetite of the decision-maker, and the context of the decision
  • Seeing the whole distribution and not just the expected value allows the decision-maker to consider all possible outcomes and make a judgement based on fuller information
  • A major benefit of simulation!
• Which project would you select?

  • Project 1 vs Project 2 with different profit distributions