Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    PR 2 Sol Exam 2023 BB

    Uploaded by

    shir altman

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    PR 2 Sol Exam 2023 BB

    Uploaded by

    shir altman
    6 views3 pages

    Original Title

    Pr2SolExam2023bb

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    6 views3 pages

    PR 2 Sol Exam 2023 BB

    Uploaded by

    shir altman

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Probability Theory 2

    Proposed solution of moed bet exam 2023b

    1. (a) Since f is a probability density function, it follows that


    Z ∞ Z ∞
    1= f (x)dx = ce−x dx = −ce−x |∞ 0 = 0 − (−c) = c,
    −∞ 0

    implying that c = 1. Note that for this value of c, the function f is non-negative.
    (b) Let k be an arbitrary positive integer. Then
    Z ∞ Z ∞ Z ∞
    k −x k −x ∞
    k
    E(X ) = k
    x f (x)dx = x e dx = −x e |0 + kxk−1 e−x dx
    −∞ 0 0
    = kE(X k−1 ), (1)

    where the third equality follows via integration by parts with u = xk (implying that
    u0 = kxk−1 ) and v 0 = e−x (implying that v = −e−x ). Next, we prove the following
    claim.
    Claim 1. Let k be a positive integer. Then, E(X k ) = k!.

    Proof. The proof is by induction on k. For k = 1, note that


    Z ∞
    0
    E(X) = 1 · E(X ) = x0 f (x)dx = 1,
    −∞

    where the first equality holds by (1) and the last equality holds since f is a probability
    density function. Assume now that E(X k ) = k! holds for some positive integer k. Then,
    E(X k+1 ) = (k + 1)E(X k ) = (k + 1)k! = (k + 1)!,
    where the first equality holds by (1) and the second equality holds by the induction
    hypothesis.

    2. (a) Consider a random red/blue colouring c of the edges of Kn , generated as follows. For
    every edge of Kn toss a fair coin, all coin tosses being independent. for every e ∈ E(Kn ),
    if the outcome of the
     corresponding coin toss is HEADS, colour e red, otherwise colour
    n
    it blue. Let t = 4 and let F1 , . . . , Ft be an arbitrary enumeration of the copies of K4
    in Kn . For every 1 ≤ i ≤ t, let Xi be the indicator random variable for the event “Fi
    is monochromatic under c”. Then
    4
    E(Xi ) = P(Xi = 1) = 2 · (1/2)(2) = 2−5
    holds for every 1 ≤ i ≤ t. Let X = ti=1 Xi and note that X denotes the number of
    P
    copies of K4 in Kn which are monochromatic under c. It follows by the linearity of
    expectation that
    t t
    !  
    −5 n
    X X
    E(X) = E Xi = E(Xi ) = 2 .
    4
    i=1 i=1

    1
    It follows that there exists a colouring c0 : E(Kn ) → {red, blue} such that the number
    of copies of K4 in Kn which are monochromatic under c0 is at most E(X) = 2−5 n4 .
    

    (b) We say that a red/blue colouring c : E(Kn ) → {red, blue} is good if at most 2−4 n4
    

    copies of K4 in Kn are monochromatic under c. Consider the following algorithm.


    (1) Initialize i = 1.
    (2) Generate a random colouring ci : E(Kn ) → {red, blue} as in Part (a) of this
    question.
    (3) By going over all n4 copies of K4 in Kn , check whether ci is good or not.
    

    (4) If ci is good or i = 100, output ci . Otherwise, increase i by 1 and return to Step


    (2).
    Complexity: Step (1) takes time O(1), Step (2) (executed at most 100 times) takes
    time O(n2 ), Step (3) (executed at most 100 times) takes time O(n4 ), and Step (4)
    (executed at most 100 times) takes time O(1). We conclude that the running time of
    this algorithm is O(n4 ) which is polynomial in n.
    Error probability estimation: For every 1 ≤ i ≤ 100, let Yi be the random variable
    denoting the number of copies of K4 in Kn which are monochromatic under ci (assuming
    it is generated).
     It follows by the calculation made in Part (a) of this question that
    E(Yi ) = 2−5 n4 . Since Yi is non-negative, it then follows by Markov’s inequality that
      
    −4 n
    P Yi ≥ 2 = P(Yi ≥ 2E(Yi )) ≤ 1/2.
    4
    The algorithm fails to produce a good colouring if and only if it generates 100 colourings
    in Step (2) and none of them are good. Since the colourings generated in Step (2) are
    independent of each other, the probability of the latter is
    100   
    −4 n
    Y
    P Yi ≥ 2 ≤ 2−100 .
    4
    i=1

    3. Let G ∼ G(n, 1/3). For every pair of distinct vertices u, v ∈ V (G), let Xuv be the random
    variable which denotes the number of common neighbours of u and v in G. For every
    z ∈ V (G) \ {u, v}, let Yz be the indicator random variable for the event “z is a common
    neighbour of u and v”. Note that
    E(Yz ) = P(Yz = 1) = P(uz ∈ E(G), vz ∈ E(G)) = (1/3)2 = 1/9
    P
    holds for every z ∈ V (G) \ {u, v}. Note, moreover, that Xuv = z∈V (G)\{u,v} Yz and thus
     
    X X
    E(Xuv ) = E  Yz  = E(Yz ) = (n − 2)/9
    z∈V (G)\{u,v} z∈V (G)\{u,v}

    holds by the linearity of expectation. Since the random variables Yz : z ∈ V (G) \ {u, v}
    are independent (as they rely on pairwise disjoint pairs of edges) indicators, we may use
    Chernoff’s inequality to deduce that
    √ √
     
    8n ln n
    P(|Xuv − n/9| ≥ 3 n ln n) ≤ P(|Xuv − (n − 2)/9| ≥ 2 n ln n) ≤ 2 exp − ≤ n−7 ,
    n−2

    2
    where the first inequality holds for sufficiently large n. A union bound over all pairs of
    distinct vertices
    √ shows that the probability
    √ that there exists a pair of vertices
     with more
    n −7
    than n/9 + 3 n ln n or less than n/9 − 3 n ln n common vertices is at most 2 n = o(1).

    You might also like