This course will become read-only in the near future. Tell us at community.p2pu.org if that is a problem.
University of Maryland open study group on mathematical proofs, theoretical arguments, probability theory and randomized algorithms. Focus on solving problems. Content has been chosen to complement graduate-level work in computer science.
For those on campus at UMD, there will be weekly in-person meetings to review practice problems and questions about the material. All are welcome to participate and keep pace with the material and discussions. If there is interest we will determine a way to support remote meeting participation.
MATHEMATICAL FUTURE
Read Chapter 1 of Probability and Computing ("the Alice book") and do a selection of exercises at the end of the chapter. Post comments or questions here.
Thanks to God, I have completed some exercises, they are at: http://tasks-frics.wikia.com/wiki/Chapter_1_Alice_-_vtamara
By the way feel free to use that wiki for this study group as needed: http://tasks-frics.wikia.com/wiki/Tasks-formal-reasoning-in-computer-science_Wiki
Hello Vladimir,
Awesome ! I took a superficial look at your solutions and they look great ! Is there a different LaTeX syntax (eg markups) for Wikia like Wikipedia ?
Thank you. It is the same LaTeX syntax you just have to put it inside <math> .... </math>. Try the Edit button in the page with solutions.
The solution are written in a great detail. I have added some alternative solution to it that may be simpler to work out (and fixed some miscalculation).
(Testing image embeds) Saravanan posted lots of solutions for chapter 1 problems... so we can compare for those we all did and, in my case, find at least one typo :)
I defiitely found chapter 1 of the alice book more challenging than the MathCS book. I mostly found my way through the proofs, but had two things I couldn't quite figure out.
1. Lemma 1.1
The proof of Lemma 1.1, says that the first two expressions, for Pr(E1) and Pr(E2) follow from the definition (I assume "the definition" is referring to definition 2). But I don't see how they follow-- if I apply definition 2 for two events E1 and E2 I get a simpler equation-- ie, that the probability of the union of E1 and E2 is the sum of the probabilities.
The lemma makes sense intuitively, I'm just not sure where they'e getting the expressions from.
2. on page 22 of the pdf version, there is an inequality in the middle of the page (the last equation on the page) where they say that \prod_{j=1}^k (d- (j-1))/(100d-(j-1)) <= ((1/100)^k.
i don't imagine they're wrong but it's not immediately obvious that that inequality necessarily holds. we know that d and j are integers, but i guess i just don't quite see the inequality.
Anyone get it? :)
Going to start doing some problems soon... woo :)
@Jessy,
Condition 3 for Definition 2 works only for pairwise mutual disjoint events. May be using definition 1 might be more apt. The equation makes more sense if we view it from the perspective of a Venn diagram . In definition 1, the authors say that the probability space consists of different sets (E1 and E2 in this case) .
The probability space has E1 and E2 and E1 \cup E2 = \Omega . Then E1 = E1 - (E1 \cap E2) + (E1 \cap E2). Applying the probability on both sides we get the first line.
Orig equation : \prod_{j=1}^k (d- (j-1))/(100d-(j-1)) <= ((1/100)^k
@Jessy,
May one way to see it is to define a new variable (say) i=j-1 and change the equation as \prod_{i=0}^{k-1} (d- i)/(100d-i) .
Then , take factorize d out of the equation : \prod_{i=0}^{k-1} d( 1 - (i/d)) / d(100-i/d) . Cancelling out d, we have \prod_{i=0}^{k-1} ( 1 - (i/d)) / (100-i/d) .
The largest value each term of the expression can take is 1/100 and hence the rhs follows.
Of course, all this are under the assumption d >> k . Else, we can use the brute force to compute the canonical form.
thanks saravanan, that helps! :)
IMHO it is not necessary that E1 \cup E2 = \Omega. (By the way in TeX \cup is the union symbol whie \cap is the intersection symbol, see http://www.artofproblemsolving.com/Wiki/index.php/LaTeX:Symbols ).
Just use the following equalities that are easy to prove (in set theory with the definition of =, \cup, \cap and - and using that some sets are pairwise mutually disjoint if the intersection of any pair is empty)
Apply condition 3 of definition 2 to each one and you have the three equalities.
Thank you. It is not necessary that d >> k. Assuming that 0 <= i < k <= d you can prove that (1-(i/d)) / (100-i/d) <= 1/100 (and the book states that k<=d. and the values of i are between 0 and k-1).
