5
$\begingroup$

I am teaching a "computation" course, where we get students to explore mathematics and statistics via a high-level programming language. So the course is less about mathematics proper, and more about computation, and the process of learning about mathematics.

I am looking for good examples of the form where the main ideas behind the techniques are easy to motivate, and yet the technique (aided with a computer) produces otherwise difficult-to-obtain results.

I've been hoping to find a good example from the MCMC family of ideas. Perhaps it's because I'm not terribly familiar with this branch of stats myself that I haven't developed good basic examples.

Perhaps this is a stretch, but in these family of ideas would there be a good, simple way of estimating the volume of an icosahedron?

I don't need examples quite that sophisticated. But I would like the examples to be intuitive-enough to stand on their own, but flexible enough so the student could have some idea of how to apply the technique to a wide variety of problems.

These students know linear algebra and multi-variable calculus, and a little bit about programming languages.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ MCMC stands for Markov Chain Monte Carlo. $\endgroup$
    – Ryan Budney
    Jan 3, 2017 at 22:50

2 Answers 2

Reset to default
6
$\begingroup$

Perhaps the "Metropolis Ball-Walk" algorithm for computing the volume of a polyhedron might be a good example?

BallWalk
I found two sets of lecture notes on the topic, neither of which may be ideal, but...

The snapshot above is from Sinclair's notes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Joseph. I'll see what I can do with this. . . $\endgroup$
    – Ryan Budney
    Jan 4, 2017 at 3:49
4
$\begingroup$

To sample a point uniformly inside a convex set (e.g. to evaluate an integral, for example if you want to know the average distance from the center in your icosahedron), to my knowledge the most efficient algorithm is the "hit-and-run": from a point in the convex, you take a uniform random direction (easily constructed from a radially symmetric Gaussian random vector), draw the maximal segment in the convex generated by the current location and the drawn direction, a jump to a uniform random point on that segment. Then you iterate.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Some literature references on hit-and-run can be found in a paper by Anderson & Diaconis: PDF download. $\endgroup$
    – Joseph O'Rourke
    Jan 5, 2017 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.