Problem 495581 · hard · Level 04 Non-Linear Data Structures

Expected Yield on a Budget

Monte Carlo integration · standard error · variance reduction · stratified sampling

An agronomist has a crop model f: it takes a list x of dim numbers between 0 and 1 (scaled weather and soil conditions for the season) and returns a yield. The conditions are uncertain and every combination is equally likely, so the quantity of interest is the expected yield, the average of f(x) over all x in the unit cube [0, 1]^dim. The model is slow, so you may call it at most budget times.

Write expected_yield(f, dim, budget, rng) that returns your estimate of the expected yield. rng is a random.Random object; use it (and nothing else) for any randomness you need. Call f with a list of dim floats, each between 0 and 1 inclusive, and never more than budget times.

Each test calls yield_trial(expected_yield, dim, budget, case) from the setup. It builds a hidden model (smooth parts, kinks and jumps, in 3 to 6 dimensions) whose exact expected yield it knows, runs your function 16 times with 16 different rng seeds, and reports your typical error: the root mean square of the 16 errors. You can call yield_trial yourself with Run to see how your ideas do.

Examples

Input:  yield_trial(expected_yield, 3, 1250, 4)
Output: for example {"rmse": 0.0177, "plain": 0.0598, "calls": 1250}
Explanation: averaging f at 1250 independent uniform points has a typical error of 0.0598
for this model; an estimator that places the points more cleverly reached 0.0177.

How this problem is scored

  • Baseline: plain Monte Carlo, the average of f at budget independent uniform points. Its typical error is sd(f) / sqrt(budget), computed exactly by the judge (the value "plain"). You pass a test when your typical error is at most 1.6 times that (so an honest plain Monte Carlo estimate always passes, and a lucky guess does not).
  • Best known: the smallest typical error that much stronger offline methods reached on the same model with the same budget and the same 16 runs.
  • Score: 100 · log(plain / yours) / log(plain / best), between 0 and 100 (100 at or below the best known, 0 at or above plain Monte Carlo's error).

Constraints

  • 3 <= dim <= 6, 1000 <= budget <= 1500
  • more than budget calls of f raise BudgetExceeded, and coordinates outside [0, 1] raise ValueError; either fails the test
  • the result must not depend on the clock; each call of your function must finish well within a tenth of a second

Goals

  • Estimate an expected value by averaging a model over random inputs
  • Measure an estimator by its typical error over repeated runs
  • Reduce the error for a fixed number of model runs by spreading the sample points more evenly
Starting Python…