Problem A. 583. (February 2013)

A. 583. There are given n random events (n $\ge$ 3) 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

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

Already signed up?
New to KöMaL?