Problem A. 846. (February 2023)

A. 846. Let \(\displaystyle n\) be a positive integer and let vectors \(\displaystyle v_1,v_2,\ldots,v_n\) be given in the plain. A flea originally sitting in the origin moves according to the following rule: in the \(\displaystyle i^{\text{th}}\) minute (for \(\displaystyle i=1,2,\ldots,n\)) it will stay where it is with probability \(\displaystyle 1/2\), moves with vector \(\displaystyle v_i\) with probability \(\displaystyle 1/4\), and moves with vector \(\displaystyle -v_i\) with probability \(\displaystyle 1/4\). Prove that after the \(\displaystyle n^{\text{th}}\) minute there exists no point which is occupied by the flea with greater probability than the origin.

Proposed by Péter Pál Pach, Budapest

(7 pont)

Deadline expired on March 10, 2023.

Assume that in the \(\displaystyle i\)th minute, the flea first decides with a probability of \(\displaystyle \frac{1}{2}\) whether to jump with the vector \(\displaystyle v_i\), and then independently decides with a probability of \(\displaystyle \frac{1}{2}\) whether to jump with the vector \(\displaystyle -v_i\). This results in a probability of \(\displaystyle \frac{1}{4}\) that it jumps with \(\displaystyle v_i\) in total, and a probability of \(\displaystyle \frac{1}{4}\) that it jumps with \(\displaystyle -v_i\) in total during the minute, and a probability of \(\displaystyle \frac{1}{2}\) that it stays in place.

The order of jumps is irrelevant to where the flea will be at the end of the \(\displaystyle n\)th minute, so we can assume that the flea first decides about all the vectors \(\displaystyle v_i\), which we call the first round. Then the flea decides about all the vectors \(\displaystyle -v_i\), which we call the second round.

Let \(\displaystyle W\) be the set of vectors that the flea could have moved with during the first round. Let \(\displaystyle p_w\) be the probability that the flea moved with \(\displaystyle w\in W\) during the first round.

In the second round, the flea can move with vectors \(\displaystyle -W=\{-w: w\in W\}\), and the probability of moving with \(\displaystyle -w\) is \(\displaystyle p_w\), since each path it could take to move \(\displaystyle w\) in the first round is matched by a path of the same number of hops it could take to move \(\displaystyle -w\) in the second round.

So, for any vector \(\displaystyle r\), the probability that the flea moves away from the origin by the vector \(\displaystyle r\) throughout its entire movement,

\(\displaystyle \sum_{w_1, w_2\in W, w_1-w_2=r} p_{w_1}p_{w_2}.\)

Since for every \(\displaystyle w_1\in W\) there is at most one vector \(\displaystyle w_2\in W\) for which \(\displaystyle w_1-w_2=r\), the above sum is at most

\(\displaystyle \sum_{w\in W} p_wp_{\pi(w)},\)

where \(\displaystyle \pi\) is a permutation of the elements of \(\displaystyle W\). By the rearrangement inequality this is at most \(\displaystyle \sum_{w\in W} p_w^2.\)

The flea ending up in the origin means that it will move in the second round with the opposite vector as in the first round, which has exactly a probability of \(\displaystyle \sum_{w\in W} p_w^2.\)

With this, we have proved the desired statement.

Statistics:

6 students sent a solution.
7 points:	Németh Márton, Seres-Szabó Márton, Varga Boldizsár.
0 point:	3 students.

Problems in Mathematics of KöMaL, February 2023