One of the exercises I assigned last week proved interesting:
Consider n points on a circle, labeled clockwise from 0 to n-1. Initially a wolf begins at 0 and there is a sheep at each of the remaining n-1 points. The wolf takes a random walk on the circle; at each step, it moves with probability 1/2 to one neighbor and with probability 1/2 to the other neighbor. (0 and n-1 are neighbors.) The first time the wolf visits any point it eats the sheep that is there. (The wolf can return to points with no sheep.) Which sheep is most likely to be the last eaten?
If you haven't seen it before, you might try it; don't put the answer in the comments, though, since I'll use the problem again.
While grading the assignment, I found a number of students had simulated the process, figured out the answer from the simulations, and then used that knowledge to prove the desired result. The problem didn't ask for them to do it, but they did it themselves.
That was great (and I told them so). That's how solving research problems often works for me. I have to understand what's going on, and in many cases, that understanding comes about by simulating a process to figure out how things behave. Then I go back and try to prove what I think I'm seeing in the simulations.
My worry, though, is that the students that did it this way were primarily the "non-theorists" in the class, who did it because they knew they didn't know the answer, and thought it was easier to code to figure it out. And that the "theorists" in the class correspondingly thought they knew the answer (rightly or wrongly) and went ahead with the calculations without doing a simulation. That's not necessarily a bad thing, certainly not for this problem (which is easy enough), but I'd also like for the theorists to also get into a mindset of doing simulations in this sort of setting, both as a tool to gain insight before trying to prove things and as a check on their proofs.
I think they're probably getting the lesson from other, harder exercises I give. Still, it was nice that a number of people in the class went that direction (and thought to write it down in their assignment).
Subscribe to:
Post Comments (Atom)
7 comments:
Hmm... does the answer change if the sheep are also taking random walks, and the wolf eats all sheep at his location?
Won't the answer depend on how long this process continues? Do you implicitly mean it continues forever?
Anon: you can condition on the event "there exists a finite time t such that at time t the wolf has eaten all sheep". This happens with probability 1.
What a timely piece.
I am thinking precisely now of changing part of our intro course for freshmen. It has a piece (that I just got done teaching) on runtime analysis, solving simple recurrences, proofs by induction, and the like.
I'm considering replacing that by coding the recurrences, looking at the resulting data on runtime, and inferring from those data points whether the runtime is linear, quadratic, n log n, etc. Formal analysis would be deferred to later semesters.
@mm, you've defined a symmetric ring with zero or one unique sheep-containing points (depending on whether n is odd or even). Are you sure you want to phrase the question as "which sheep is" in the singular? :-) Or maybe I misunderstood the formulation.
baaa. nice post, though. i'd be one of those simulators. :)
I love this problem :-)
I present it in the following form: "You and N of your friends are sitting at a round table. You have a very large bag of M&Ms and a coin. Eat an M&M, flip the coin. On heads, pass the bag and coin to the person on the left --- on tails, pass them to the person on the right. Continue this random walk until everyone has eaten at least 1 M&M.
Easier: For each of your N friends (from #1 on your left all the way round to #N on your right), what is the probability they are the *last* person to eat an M&M?
Harder: What if the coin isn't fair?"
My biased coin is likely to stump the simulation-only crowd, forcing them into [:shudder:] algebra.
Here is a related problem: "There are N balls in a bag. Initially all the balls have distinct colors. Define an 'iteration' as follows: reach into the bag and pick out a pair of balls --- color the ball in your right hand so it matches the ball in your left hand --- put them back. On average, how many iterations until all the balls are the same color?"
I like the way you look at things, and I encourage Claire to actually do what she proposes.
Post a Comment