ACM 116: Stochastic Processes

October 11th, 2006 ~ Posted in: Mathematics

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 N 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.

Mathematics ~

6 Responses to “ACM 116: Stochastic Processes”

  • 1. AnonEcon
    October 11th, 2006 at 7:48 pm

    Is it

    sum_{k=1}^{k=N}{1/(2k-1)}

  • 2. Alex
    October 11th, 2006 at 11:38 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?

  • 3. AnonEcon
    October 12th, 2006 at 1:57 am

    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?

  • 4. AnonEcon
    October 12th, 2006 at 4:17 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)

  • 5. Alex
    October 13th, 2006 at 9:23 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.

  • 6. AnonEcon
    October 13th, 2006 at 10:19 pm

    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.

This entry was posted on Wednesday, October 11th, 2006 at 12:31 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply