5.4-3 For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.
From appendix: A collection A1,A,.....An of events is said to be pairwise independent if $$Pr{Ai \cap Aj} = Pr{Ai} .Pr{Aj}$$ for all 1 i < j n.
We say that the events of the collection are (mutually) independent if every k-subset Ai1,Ai2, ... ,Aik of the collection, where 2\leq k \leq n and $1 \leq i1 < i2 < < ik \leq n$, satisfies $$Pr{Ai1 \cap Ai2 \cap.... \cap Aikg } = Pr{Ai1}. Pr{Ai2}...Pr{Aik}.$$ we need pairwise independence if we see the analysis of birthday pardox we compare two people birthdays. $$Pr\{b_i = r and b_j =r\} = Pr\{b_i=r\} Pr\{b_j=r\}$$
No comments:
Post a Comment