Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem A. 583. (February 2013)

A. 583. There are given n random events (n\ge3) such that each of them has probability \frac12, the joint probability of each two is \frac14 and the joint probability of each three is \frac18. (a) Prove that the probability that none of the events occurs is at most \frac{1}{2n}. (b) Show that there are infinitely many numbers n, for which the events can be specified in such a way that the probability that none of the events occurs is precisely \frac{1}{2n}.

Based on problem 3 of the Kürschák competition in 2012

(5 pont)

Deadline expired on March 11, 2013.


Solution. (a) Denote by N the number of the occuring events, and let p be the probability that N=0. Denote by E(f(N)|N>0) the conditional expected value of f(N), assuming N>0. Then we have

E(1|N>0)=1,

 E(N|_{N>0}) = \frac1p\sum P(A_i) = \frac{n}{2p},

 E(N^2|_{N>0}) = \frac1p \left(\sum P(A_i)+2\sum_{i<j} P(A_i\cap A_j)\right) =
  \frac1p \left(n\cdot\frac12 + 2\binom{n}2 \frac14 \right) =
  \frac{n^2+n}{4p},

 E(N^3|_{N>0}) = \frac1p \left(\sum P(A_i)+6\sum_{i<j} P(A_i\cap A_j)
    + 6\sum_{i<j<k} P(A_i\cap A_j\cap A_k) \right) =

  = \frac1p \left(\frac{n}2 + 6\binom{n}2 \frac14
    + 6\binom{n}3 \frac18 \right) =
  \frac{n^3+3n^2}{8p}.

By substituting x=N into -x^3+2nx^2-\frac54n^2x+\frac{n^3}4=(n-x)(x-n/2)^2\ge0 and taking conditional expected values we get


  E\left( -N^3+2nN^2-\frac54n^2N+\frac{n^3}4 \bigg|_{N>0}\right) \ge0


  -E(N^3|_{N>0})
  +2nE(N^2|_{N>0})
  -\frac54n^2E(N|_{N>0})
  +\frac{n^3}4E(1|_{N>0}) 
  \ge0


  -\frac{n^3+3n^2}{8p} +2n\frac{n^2+n}{4p}
  -\frac54n^2\frac1p +\frac{n^3}4 \ge0


  p \ge 1-\frac1{2n}.

(b) If n=2k the equiality can be achieved. Suppose that

-- with probability \frac1{4k} none of the events occurs.

-- with probability \frac1{4k} all of the events occurs.

-- with probability \frac{2k-1}{2k}, precisely half of the events occur, and the k-sets of events have the same probability. Then


  P(A_i) = \frac1{4k} + \frac{2k-1}{2k}\cdot
  \frac{\binom{2k-1}{k-1}}{\binom{2k}{k}} =
  \frac1{4k} + \frac{2k-1}{2k}\cdot \frac12 = \frac12


  P(A_{i_1}\cap A_{i_2}) = \frac1{4k} + \frac{2k-1}{2k}\cdot
  \frac{\binom{2k-2}{k-2}}{\binom{2k}{k}} =
  \frac1{4k} + \frac{2k-1}{2k}\cdot \frac{k-1}{2(2k-1)} = \frac14


  P(A_{i_1}\cap A_{i_2}\cap A_{i_3}) =
  \frac1{4k} + \frac{2k-1}{2k}\cdot
  \frac{\binom{2k-3}{k-3}}{\binom{2k}{k}} =
  \frac1{4k} + \frac{2k-1}{2k}\cdot \frac{(k-1)(k-2)}{2(2k-1)(2k-2)} =
  \frac18.


Statistics:

3 students sent a solution.
5 points:Janzer Olivér, Nagy Bence Kristóf, Szabó 928 Attila.

Problems in Mathematics of KöMaL, February 2013