XXV - I - Problem 11

Let $ X_n $ and $ Y_n $ be independent random variables with the same distribution $ \left{ \left(\frac{k}{2^n}, \frac{1}{2^n}\right) : k = 0, 1, \ldots, 2^n-1\right} $. Denote by $ p_n $ the probability of the event that there exists a real number $ t $ satisfying the equation $ t^2 + X_n \cdot t + Y_n = 0 $. Calculate $ \lim_{n\to\infty} p_n $.
A favorable event consists in the discriminant of the quadratic polynomial $ t^2 + X_n t + Y_n $ being a non-negative number. Let $ \displaystyle X_n = \frac{r}{2^n} $, $ \displaystyle Y_n = \frac{s}{2^n} $, where $ r, s = 0, 1, \ldots, 2^n - 1 $. The inequality $ X_n^2 - 4 Y_n \geq 0 $ is equivalent to the inequality $ r^2 - 4 \cdot 2^n s \geq 0 $, that is,






We will find the number of such pairs $ (r, s) $ for which (1) holds. For any $ a $, the number of solutions to the inequality $ 0 \leq x \leq a $ in integers $ x $ is $ [a] + 1 $, where $ [a] $ is the greatest integer not exceeding $ a $. Therefore, the number of pairs $ (r, s) $ satisfying
(1) is equal to



Consider the sum



By the formula



we have



Since for any real number $ x $ the inequality



holds, we have



The number of all elementary events, i.e., the considered pairs $ (r, s) $, is $ 2^{2n} $. Therefore, $ \displaystyle p^n = \frac{A^n}{2^{2n}} $ and from (3) it follows that



From (2) we obtain that $ \displaystyle \lim_{n \to \infty} \frac{B_n}{2^{2n}} = \frac{1}{12} $ and therefore from (4) we conclude that $ \displaystyle \lim_{n \to \infty} p_n = \frac{1}{12} $