Problem A. 883. (May 2024)

A. 883. Let \(\displaystyle J \subsetneq I \subseteq \mathbb{R}\) be non-empty open intervals, and let \(\displaystyle f_1\), \(\displaystyle f_2\), \(\displaystyle \ldots\) be real polynomials satisfying the following conditions:

•  \(\displaystyle f_i(x) \geq 0\) for all \(\displaystyle i \geq 1\) and \(\displaystyle x \in I\),
•  \(\displaystyle \sum_{i=1}^\infty f_i(x)\) is finite for all \(\displaystyle x \in I\),
•  \(\displaystyle \sum_{i=1}^\infty f_i(x)=1\) for all \(\displaystyle x \in J\).

Do these conditions imply that \(\displaystyle \sum_{i=1}^\infty f_i(x)=1\) also for all \(\displaystyle x \in I\)?

(Proposed by András Imolay, Budapest)

(7 pont)

Deadline expired on June 10, 2024.

Solution 1. We will prove that the statement is not true, i.e. there exist intervals and polynomials satisfying the conditions. Let the indexing start at \(\displaystyle n=0\) and let \(\displaystyle f_n=C_nx^{n+1}(1-x)^n\), where \(\displaystyle C_n\) denotes the \(\displaystyle n^{\text{th}}\) Catalan number, i.e. the number of ways to start and arrive at 0 on the number line by doing \(\displaystyle 2n\) steps of unit length without visiting a negative number. Let \(\displaystyle I=(0,1)\) and \(\displaystyle J=(1/2,1)\).

We will prove the following famous statement:

Claim: Let's consider an infinite random walk on the number line starting from 0 where the probability of moving to the left is \(\displaystyle p\) and the probability of moving to the right is \(\displaystyle 1-p\). For \(\displaystyle p\ge 1/2\) we will visit -1 with probability 1 and for \(\displaystyle p<1/2\) we will visit -1 with probability less than 1.

Proof: Let \(\displaystyle a\) denote the probability of visiting -1; this means that \(\displaystyle 1-a\) is the probability of only visiting non-negative numbers. If we only visit non-negative numbers, we have to move to the right first, and then we get back to 0 with probability a, and then the process starts over, or we don't, and then we can only visit positive values during the walk, thus we get the following equality: \(\displaystyle 1-a=(1-p)(a(1-a)+(1-a))\). Solving the equation yields \(\displaystyle a=1\) and \(\displaystyle a=p/(1-p)\). The latter is greater than 1 for \(\displaystyle p>1/2\), thus it cannot be the solution, which proves the first half of the claim.

To prove the second half, it's enough to show that for \(\displaystyle p>1/2\) the probability of visiting 1 is less than 1. If we consider a sequence that lands on -1, let's reflect it across 0 to pair it up with a sequence that lands on 1. If we made \(\displaystyle k\) moves to the right in the first sequence, the probabilities of the two sequences are \(\displaystyle p^{k+1}(1-p)^k\) and \(\displaystyle p^k(1-p)^{k+1}\). Now note that the ratio of these is \(\displaystyle p/(1-p)\) regardless of \(\displaystyle k\), therefore the probability of reaching 1 is \(\displaystyle (1-p)/p\) times the probability of reaching -1, and thus we are done.

Let \(\displaystyle f(p)\) denote the probability of visiting \(\displaystyle -1\) (this was probability \(\displaystyle ä\) in the previous part). Then

\(\displaystyle f(p)=\sum_{i=0}^\infty f_i(p), \)

since \(\displaystyle f_i(p)\) is the probability of visiting \(\displaystyle -1\) after \(\displaystyle 2i+1\) moves for the first time. Thus the claim shows that this gives an example for the claim, if we prove that the sum converges for \(\displaystyle 0\le p\le 1\). Since we sum non-negative values, and after factoring out \(\displaystyle p\) we can see that all terms of the sum take their maximum for \(\displaystyle p=1/2\), it's enough to prove convergence for \(\displaystyle p=1/2\). Using the formula for the Catalan numbers we have to prove that

\(\displaystyle \sum\limits_{k=1}^{\infty} \frac{1}{k+1}\binom{2k}{k}\frac{1}{4^k} \)

is convergent. Thus we have to estimate binomial coefficient \(\displaystyle \binom{2k}{k}\) from the above: a well-known estimation is \(\displaystyle 4^k/\sqrt{2k}\). Therefore the convergence is the consequence of the following well known fact: \(\displaystyle \sum_{k=1}^{\infty}\frac{1}{k\sqrt{k}}<\infty\).

Remark 1: the convergence can also be proved this way: if we only add up finitely many terms of the sum, we get the probability of an event defined on a finite event space, since the number of steps performed is bounded from the above. Therefore, the finite partial sums cannot exceed 1. Since we sum non-negative terms, partial sums being bounded from the above is equivalent to the sum being convergent.

Remark 2: there is a very elegant way of proving that for \(\displaystyle p\neq 1/2\) it is not possible that both 1 and -1 are reached witj probability 1. Otherwise the probability of returning to 0 would also be 1. Now the elegant idea is to investigate the expected value of the number of returns to 0. If we return with probability 1, the expected value is infinite (since it would satisfy equation \(\displaystyle E=E+1\) for a finite value, and also because actually the probability of returning infinitely many times is also 1). On the other hand, the expected value can be expressed as \(\displaystyle \sum_{i=1}^{\infty} \binom{2i}{i}p^i(1-p)^i\), and here the summands can be estimated with \(\displaystyle 4^ip^i(1-p)^i\) from above. Now these form a geometric sequence with a quotient less than 1 for \(\displaystyle p\neq 1/2\), thus this sum is finite, and we are done.

Solution 2: Let \(\displaystyle f_i(x) = x^2 (1 - x^2)^{i - 1} \), and let \(\displaystyle I = (-1, 1) \) and \(\displaystyle J = (0, 1) \). It is clear that \(\displaystyle f_i(x) \geq 0 \) for all \(\displaystyle i \in \mathbb{N} \) and \(\displaystyle x \in I \). We claim that

\(\displaystyle \sum_{i=1}^\infty f_i(x) = \begin{cases} 0 & \text{if } x = 0, \\ 1 & \text{if } x \in I \setminus \{0\}. \end{cases} \)

It is clear that this would imply the statement of the problem. If \(\displaystyle x = 0 \), then \(\displaystyle f_i(x) = 0 \) for all \(\displaystyle i \in \mathbb{N} \). If \(\displaystyle x \neq 0 \) and \(\displaystyle |x| < 1 \), then \(\displaystyle 0 < 1 - x^2 < 1 \), and the terms \(\displaystyle f_1(x), f_2(x), \ldots \) form a geometric series, thus

\(\displaystyle \sum_{i=1}^\infty f_i(x) = \frac{x^2}{1 - (1 - x^2)} = 1, \)

as claimed.

Statistics:

4 students sent a solution.
7 points:	Szakács Ábel, Varga Boldizsár.
0 point:	2 students.

Problems in Mathematics of KöMaL, May 2024