Discusión de la Tarea


  • Vladimir Támara Patiño   5 de julio de 2011 a las 11:54

    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

  • Saravanan   6 de julio de 2011 a las 09:25
    En Respuesta A:   Vladimir Támara Patiño   5 de julio de 2011 a las 11:54

    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 ? 

  • Vladimir Támara Patiño   6 de julio de 2011 a las 11:20
    En Respuesta A:   Saravanan   6 de julio de 2011 a las 09:25

    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.

  • Tom_Chan   7 de julio de 2011 a las 16:19
    En Respuesta A:   Vladimir Támara Patiño   5 de julio de 2011 a las 11:54

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

  • Jessy Kate Schingler   31 de mayo de 2011 a las 15:17

    (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 :)

     

  • Jessy Kate Schingler   21 de mayo de 2011 a las 14:13

    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 :)

  • Saravanan   22 de mayo de 2011 a las 00:28
    En Respuesta A:   Jessy Kate Schingler   21 de mayo de 2011 a las 14:13

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

  • Saravanan   22 de mayo de 2011 a las 00:52
    En Respuesta A:   Jessy Kate Schingler   21 de mayo de 2011 a las 14:13

     

    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.

  • Jessy Kate Schingler   24 de mayo de 2011 a las 12:05
    En Respuesta A:   Saravanan   22 de mayo de 2011 a las 00:52

    thanks saravanan, that helps! :)

  • Vladimir Támara Patiño   2 de julio de 2011 a las 07:09
    En Respuesta A:   Saravanan   22 de mayo de 2011 a las 00:28

    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)

    1. E1 = (E1 - (E1 \cap E2)) \cup (E1 \cap E2) .   The following sets are pairwise mutually disjoint  (E1 - (E1 \cap E2)),  (E1 \cap E2)
    2. E2 = (E2 - (E1 \cap E2)) \cup (E1 \cap E2).  The following sets are pairwise mutually disjoint (E2 - (E1 \cap E2)), (E1 \cap E2)
    3. E1 \cup E2 =(E1 - (E1 \cap E2)) \cup (E2 - (E1 \cap E2)) \cup (E1 \cap E2).   The following sets are pairwise mutually disjoint (E1 - (E1 \cap E2)), (E2 - (E1 \cap E2)) \cup (E1 \cap E2)

    Apply condition 3 of definition 2 to each one and you have the three equalities.

  • Vladimir Támara Patiño   2 de julio de 2011 a las 07:22
    En Respuesta A:   Saravanan   22 de mayo de 2011 a las 00:52

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