Monte Carlo method

Any computational technique that estimates a quantity — usually an expected valueexpected value, n.: The long-run average you would get if a chancy situation could be repeated many times — 3.5 for a fair die, even though no single roll shows 3.5., integral or probability — by averaging over random samples. By the law of large numberslaw of large numbers, n.: The mathematical rule that averages of chance events steady out over many repetitions: flip a fair coin a few times and the share of heads can be far from one-half, but over thousands of flips it gets very close. the estimate converges to the true value, and by the central limit theoremcentral limit theorem, n.: The mathematical reason bell curves are everywhere: add up many small independent random effects and the total is almost always bell-shaped, whatever the individual effects look like. its error shrinks in proportion to 1/√N for N samples regardless of dimension, which is why Monte Carlo beats grid-based integration in high dimensions. Variancevariance, n.: A number that grows the more widely something's possible values scatter away from its average, and is zero if it never varies. Its square root, the standard deviation, uses the same units as the values themselves.-reduction refinements include importance samplingimportance sampling, n.: A shortcut for estimating averages: draw samples from a convenient source, then reweight each one to correct for how much more or less likely it would be under the source you actually care about., control variates and stratification. Monte Carlo pervades AI: a mini-batch gradient in stochastic gradient descentstochastic gradient descent, n.: A faster version of gradient descent that estimates which way is downhill from a small random sample of the training data at each step, instead of checking the whole dataset. is a Monte Carlo estimate of the full gradient; reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. estimates returns from sampled episodes and plans with Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.; variational inferencevariational inference, n.: A way of approximating a hard-to-compute probability distribution by picking the closest match from a simpler family of distributions, turning a hard problem of adding up every possibility into an optimization problem. and diffusiondiffusion model, n.: An AI that learns to create images, sound or video by practicing noise removal: shown pictures buried under static, it learns to clean them up, then builds new ones starting from pure static. training estimate expectations with sampled noise; and keeping dropout on at test time ('Monte Carlo dropout') approximates uncertainty. Markov chain Monte CarloMarkov chain Monte Carlo, n.: A family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability. extends the idea to distributions that cannot be sampled directly.

We estimated each problem's pass rate with a Monte Carlo average over 200 samples.