Skip to content

7. Sampling Methods I

7.1 Why Sampling Is Needed

Intuition

When the future has many possible outcomes, listing all of them is hard. Sampling means generating a manageable set of possible futures.

Instead of asking:

What are all possible future demands?

we ask:

What happens in 100 simulated futures?

Formal definition

Monte Carlo estimate:

\[ E[F(x,\omega)] \approx \frac{1}{N}\sum_{n=1}^{N}F(x,\omega^n) \]

where:

  • \(N\) is the number of samples,
  • \(\omega^n\) is sampled future \(n\),
  • \(F(x,\omega^n)\) is the performance of decision \(x\) in that future.

Properties

  • More samples usually reduce random error.
  • Sampling can approximate expectations without exact enumeration.
  • Bad samples lead to bad estimates.
  • Sampling costs computation time.
flowchart LR
    A["Information model"] --> B["Generate samples omega^1,...,omega^N"]
    B --> C["Evaluate decision x in each sample"]
    C --> D["Average performance"]
    D --> E["Choose or compare decisions"]

7.2 Scenario Enumeration vs Monte Carlo Sampling

Intuition

Scenario enumeration lists all possible futures. Monte Carlo sampling uses a subset.

Formal comparison

Exact expectation:

\[ E[F]=\sum_i p_iF_i \]

Sample estimate:

\[ \bar F=\frac{1}{N}\sum_n F_n \]

Properties

Method Best when Weakness
Enumeration few outcomes impossible when outcomes explode
Monte Carlo many outcomes estimate has sampling error
Stratified sampling important categories known more design effort
Scenario reduction large scenario set exists may remove rare important futures

Worked example: delivery cost

Decision A is tested in 5 sampled futures:

costs = 20, 25, 30, 35, 40

Sample average:

\[ \begin{aligned} \text{average} &= \frac{20+25+30+35+40}{5} \\ &= \frac{150}{5} \\ &= 30 \end{aligned} \]

Interpretation:

Estimated expected cost is 30.

7.3 Sampling For Information Models

Intuition

Sampling requires an information model. You need a way to generate possible future demand, travel times, service times, or arrivals.

Formal process

\[ \omega^n \sim \text{information model} \]

Translation:

Sample future information from the assumed distribution or simulator.

Properties

  • If the information model is biased, the sampled futures will be biased.
  • Historical data can estimate sample distributions.
  • Expert judgment can be used when data is limited.
  • Samples should reflect business patterns, such as morning/evening demand.

Worked example: ride-hailing spatial demand

Morning samples:

more origins in suburbs
more destinations downtown

Evening samples:

more origins downtown
more destinations in suburbs or nightlife areas

Decision use:

simulate request locations to evaluate vehicle repositioning policies.

7.4 Sample Size and Error

Intuition

Sampling is like polling voters. A small sample gives a rough estimate. A larger sample is more stable but costs more.

Simple property

For many averages:

typical sampling error shrinks roughly like 1 / sqrt(N)

Translation:

Using four times as many samples roughly halves random error.

Worked example

If 25 samples give a rough error of about 10 units, then 100 samples may give about:

\[ \frac{10}{\sqrt{100/25}}=\frac{10}{2}=5\text{ units} \]

Exam phrase

Increasing the number of samples can improve estimate quality but increases computation time.

7.5 Sampling as a Managerial Experiment

Intuition

Sampling is a controlled way to ask "what if?" many times. Instead of arguing about one forecast, the analyst generates many plausible futures and measures how a policy performs across them.

flowchart LR
    A["Policy pi"]:::policy --> B["Sample path 1"]:::sample
    A --> C["Sample path 2"]:::sample
    A --> D["Sample path 3"]:::sample
    A --> E["..."]:::sample
    B --> F["Cost/reward 1"]:::metric
    C --> G["Cost/reward 2"]:::metric
    D --> H["Cost/reward 3"]:::metric
    E --> I["Cost/reward N"]:::metric
    F --> J["Average + variability"]:::summary
    G --> J
    H --> J
    I --> J
    classDef policy fill:#ede9fe,stroke:#7c3aed,stroke-width:2px,color:#0f172a;
    classDef sample fill:#e0f2fe,stroke:#0284c7,stroke-width:2px,color:#0f172a;
    classDef metric fill:#dcfce7,stroke:#16a34a,stroke-width:2px,color:#0f172a;
    classDef summary fill:#fef9c3,stroke:#ca8a04,stroke-width:2px,color:#0f172a;

Worked example: policy evaluation by sample paths

Three policies are simulated for five days each.

Policy Day costs Average cost
closest driver 120, 130, 110, 125, 115 120
RHO 100, 140, 105, 110, 125 116
RHO + CFA 105, 112, 108, 115, 110 110

Business interpretation:

RHO + CFA has the best average and looks more stable in this small sample.

Approach comparison

Sampling design Merit Disadvantage
random Monte Carlo simple and general may miss rare events
common random numbers fair policy comparison requires paired scenarios
stress scenarios tests resilience not an average-case estimate
stratified scenarios covers key demand types needs careful scenario design

7.7 Slide Enrichment: Monte Carlo As A Replacement For Impossible Expectations

Mental model

In stochastic decision making, the ideal objective often contains an expectation. But expectations can be hard to calculate exactly. Monte Carlo sampling replaces the impossible average over all futures with a practical average over sampled futures.

Formal definition

For a fixed decision \(x\):

\[ \mathbb{E}[F(x,\omega)] \approx \frac{1}{N}\sum_{n=1}^{N}F(x,\omega^n). \]

\(N\) is the number of sampled scenarios. \(\omega^n\) is scenario \(n\).

Worked example: choosing a delivery route

Scenario Travel cost route A Travel cost route B
1 20 28
2 35 30
3 50 32
4 25 31

Sample average:

\[ \hat F(A)=\frac{20+35+50+25}{4}=32.5. \]
\[ \hat F(B)=\frac{28+30+32+31}{4}=30.25. \]

Choose B by sampled expected cost.

Properties

  • More samples usually reduce sampling error.
  • Samples must represent the uncertainty that matters for the decision.
  • Monte Carlo is easy to explain but can be computationally expensive.
  • A bad scenario generator produces misleading decisions.

In the slides, sampling is not just a statistics trick. It supports information models used inside decision models. For example:

Business system Sampled information \(\omega\) Decision supported
Ride-hailing future requests by zone/time reposition idle vehicles
Repair service service duration schedule buffers
Routing travel-time realization route choice
Inventory demand quantity stock or replenish

Exam trap

Do not say sampling automatically solves the decision problem. Sampling estimates future outcomes; the decision model still needs an objective, feasible decisions, and a policy for using the samples.

Chapter source note

Course basis: DDM sampling/look-ahead and tutorial scenario examples. Textbook enrichment: Kochenderfer et al. on sampling rollouts and policy validation; Powell on sampled models and stochastic search. Use sampling to approximate expectations, not to claim exactness.