Monte Carlo Method - Revision history

Bradley Monk at 04:31, 3 November 2013

2013-11-03T04:31:31Z

← Older revision		Revision as of 21:31, 2 November 2013
Line 1:		Line 1:
	== Introduction ==		== Introduction ==
	[[File:Monte Carlo Circle.gif~~\|thumb~~\|right\|Monte Carlo method applied to approximating the value of {{pi}}. After placing 30000 random points, the estimate for {{pi}} is within 0.07% of the actual value. This happens with an approximate probability of 20%.]]		[[File:Monte Carlo Circle.gif\|right\|Monte Carlo method applied to approximating the value of {{pi}}. After placing 30000 random points, the estimate for {{pi}} is within 0.07% of the actual value. This happens with an approximate probability of 20%.]]
	Monte Carlo methods vary, but tend to follow a particular pattern:		Monte Carlo methods vary, but tend to follow a particular pattern:
	# Define a domain of possible inputs.		# Define a domain of possible inputs.

Bradley Monk at 04:30, 3 November 2013

2013-11-03T04:30:28Z

← Older revision		Revision as of 21:30, 2 November 2013
Line 15:		Line 15:

	If the grains are not uniformly distributed, then our approximation will be poor. Secondly, there should be a large number of inputs. The approximation is generally poor if only a few grains are randomly dropped into the whole square. On average, the approximation improves as more grains are dropped.		If the grains are not uniformly distributed, then our approximation will be poor. Secondly, there should be a large number of inputs. The approximation is generally poor if only a few grains are randomly dropped into the whole square. On average, the approximation improves as more grains are dropped.




			[[Category:Diffusion]] [[Category:Statistics]]

Bradley Monk: Created page with "== Introduction == [[File:Monte Carlo Circle.gif|thumb|right|Monte Carlo method applied to approximating the value of {{pi}}. After placing 30000 random points, the estimate f..."

2013-11-03T04:29:05Z

Created page with "== Introduction == [[File:Monte Carlo Circle.gif|thumb|right|Monte Carlo method applied to approximating the value of {{pi}}. After placing 30000 random points, the estimate f..."

New page

== Introduction ==
[[File:Monte Carlo Circle.gif|thumb|right|Monte Carlo method applied to approximating the value of {{pi}}. After placing 30000 random points, the estimate for {{pi}} is within 0.07% of the actual value. This happens with an approximate probability of 20%.]]
Monte Carlo methods vary, but tend to follow a particular pattern:
# Define a domain of possible inputs.
# Generate inputs randomly from a [[probability distribution]] over the domain.
# Perform a [[Deterministic algorithm|deterministic]] computation on the inputs.
# Aggregate the results.

For example, consider a circle inscribed in a unit square. Given that the circle and the square have a ratio of areas that is {{pi}}/4, the value of [[pi|{{pi}}]] can be approximated using a Monte Carlo method:
# Draw a square on the ground, then [[inscribed figure|inscribe]] a circle within it.
# [[uniform distribution (continuous)|Uniformly]] scatter some objects of uniform size (grains of rice or sand) over the square.
# Count the number of objects inside the circle and the total number of objects.
# The ratio of the two counts is an estimate of the ratio of the two areas, which is {{pi}}/4. Multiply the result by 4 to estimate {{pi}}.
In this procedure the domain of inputs is the square that circumscribes our circle. We generate random inputs by scattering grains over the square then perform a computation on each input (test whether it falls within the circle). Finally, we aggregate the results to obtain our final result, the approximation of {{pi}}.

If the grains are not uniformly distributed, then our approximation will be poor. Secondly, there should be a large number of inputs. The approximation is generally poor if only a few grains are randomly dropped into the whole square. On average, the approximation improves as more grains are dropped.