Thursday, January 20, 2011

Homework 3

As you know, HW3 has been handed out and is available on the website. Its due next Thursday. It seems that some of you are still unsure of some basic concepts in probability. Problem 4 of this homework heavily relies on your understanding of random variables and expectations. Please, feel absolutely free to clarify your understanding during office hours with the TAs. If you prefer, you may also contact me (Raga) personally to set up a time to meet and clarify your doubts.

As usual, ask your questions on the homework as comments to this post... Good luck!


  1. I received the following questions through e-mail (sorry for the delay in creating a post for HW3):

    Q: "How can we use the central limit theorem's E[X] for Pareto with scale parameter 1? Isn't the expected value for this random variable indeterminate? I'm also not too entirely sure how to interpret the results for the CLT plots. The results for the Normal shows very small deviation (< 1) while the heavy tails are pretty large (around 2~6). My conclusion is that this means the CLT breaks down with a heavy tail distribution as we saw in class. But am not too sure how to justify it completely."

    A: Without giving too much away, the question asks you to make various plots and interpret them in light of the law of large numbers and the central limit theorem. Your interpretation should include your conclusion about the applicability of these limit theorems to each of the four scenarios. So, if you feel that one of these theorems fails for a particular scenario, then say so and explain why you think it fails.

    Q: "On the first problem part c, in the limit we're supposed to prove, are the log's on the left hand side log_n or anything specific? I think I know why you can just write them as log since converting to another base will just leave a constant term out front which then cancels with top and bottom."

    A: It doesn't matter what the base of the logarithms that appear in the fraction on the left hand side are (just assume that they are both to the same base), because it is a property of logarithms that no matter what the base is, as long as the two bases are the same, the ratio is the same.

    Q: "For part d of the first problem, I'm not too sure what to consider in contrasting the two results. Can you give a little nudge in the right direction?"

    A: Part b asks you for the distribution of the length of the next word that the monkey will type. This means specifying the probability that the length of the next word is a certain positive integer. Part c asks you for the probability that the monkey types a particular word of a particular rank, but the rank of a word and its length are related (by the definition of rank). So it kinda looks like parts (b) and (c) both involve probabilities of words of certain lengths being typed. Your task is to figure out in what aspect are these two distributions different, and why they differ in that aspect.

  2. To clarify my response to the first question above, by "fails", I mean "does not apply".

  3. Some general announcements/clarifications:

    For problem 2, assume n>1.

    For those of you who are turning in your homework electronically, you should ideally combine your
    solutions to the problems, your code, and your plots, all into one single pdf file. You can print your code to pdf, convert plots in any image format into pdfs, label them and join all these pdfs into one and email it to me. Once again, please just attach a single pdf file containing the solutions, code and plots (properly labelled). If, for some reason, you are not able to convert stuff into pdf and combine them, just print them out directly and turn it in the form of a hard copy stapled together as one bunch.

  4. For problem 3(b) you only need to make plots and comment on them for distributions (i)-(iii).

  5. I received a (very heavy!) homework submission today with no name on it! It is about 30 pages of typed material (not handwritten). Whoever you are, please identify yourself! I have sent acknowledgements to everyone else who submitted a homework, so if you have submitted it but haven't received an ack from me, please contact me!

  6. Also, if anybody has turned in their homework both by email and in person, let me know.

  7. For 4(c), if we start at node A_1, go to the middle node B, then go to node A_2 (which is closest to our destination), will we go back to B from A_2, then back to A_2, then continue along the ring? Or will the mechanism remember that we already got to A_2 from B from A_1, so once instead of going back to B, it'll just continue along the ring to the destination?


  8. Good question, Scott. Assume that the node A_2 remembers that it got the packet from B and so it will not send it back to B, but along the ring. (If it did not remember, it could send it to B and B will send it back, and then according to what the question describes, the second time, it will route it along the ring - this could sometimes be suboptimal).