KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 11 March 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley