ACM 116: Stochastic Processes
Stochastic Processes is definitely my favorite class– even though it’s also my hardest, and the one where I make an utter fool of myself every class– although, maybe that’s why I like it so much. Before this summer, I was confused by and completely disliked ‘formal probability’, hated ‘informal’ probability, and only grudgingly admitted to an interest in ‘engineering’ probability (aka stochastic processes). But after all the skimming and talking to people about probability, and studying markov chain monte carlo techniques that I did this summer, I have fallen in love with the subject. I don’t have the feel of it yet, but I really like it.
Here’s a neat problem, one of the warm-up questions the prof asked at the start of last class:
You have a box full of
ropes. You put your hands in the box, pick two free ends and tie them together. You repeat this process until no free ends are left in the box. What is the expectation of the number of loops at the end of the process?
Finally, should I blow off tonight’s karate practice, and instead go to see a preview of an upcoming episode of Numb3rs and participate in a live cast interview afterwards, or not? Not a hard decision to make– karate is sooo much more interesting than Numb3rs– but it’s nice to need to think about it for a split second or so.
Possibly relevant posts:
- Stochastic Processes are fun! (9/13/2005)
- Stochastic Control note sets complete (5/29/2007)
- A mathematical kind of day (2/18/2005)
Is it
sum_{k=1}^{k=N}{1/(2k-1)}
Comment by AnonEcon — 10/11/2006 @ 7:48 pm
I didn’t write down the soln in class, so I could attempt recalculating it myself. I just did it, and got the same as you… so we’re both right or both wrong
what method did you use?
Comment by Alex — 10/11/2006 @ 11:38 pm
Let r(k) be the expected number of loops if you begin with k ropes. If you pick two ends at random from k ropes the probability of getting both ends from the same rope is p_k=1/(2k-1). If you do form the loop you have 1 loop and k-1 ropes from which we can expect r(k-1) more loops and otherwise we have k-1 ropes from which we can expect r(k-1) loops. So, we have the recursion:
r(k) = p_k[1 r(k-1)] (1-p_k)[r(k-1)]
or r(k) = p_k r(k-1)
or r(k)-r(k-1) = p_k =1/(2k-1)
We also know that r(1)=1. From this we get the answer by summing.
What method did you use? I was wondering if the result can be further simplified?
Comment by AnonEcon — 10/12/2006 @ 1:57 am
Hey, Wordpress has eaten up all my plus signs. It should have been
r(k) = p_k[1 \plus r(k-1)] \plus (1-p_k)[r(k-1)]
or r(k) = p_k \plus r(k-1)
or r(k)-r(k-1) = p_k =1/(2k-1)
Comment by AnonEcon — 10/12/2006 @ 4:17 am
That’s isomorphic to the method I used. As for simplification, for some reason, the prof said that the answer is proportional to ln N as N gets large, but I don’t see that from the result.
Comment by Alex — 10/13/2006 @ 9:23 am
After your hint I shamelessly formula-mined Knuth’s Fundamental Algorithms to find
sum_{k=1}^{N}{1/k} \approx ln(N) \plus \gamma
where \gamma is Euler’s constant: 0.5772156649…
Playing around with that a bit I got
sum_{k=1}^{N}{1/(2k-1)} \approx
(1/2) ln(N) \plus ln(2) \plus \gamma/2
Even for N as low as 10 the error in this approximation is less than one part in a thousand.
Comment by AnonEcon — 10/13/2006 @ 10:19 pm