Is there some general lower bound for sum of squared probabilities?

1.6k Views Asked by At

In foundations of cryptography the author is trying to demonstrate the success an adversarial algorithm A1 will have using just random guessing. A1 will, given the output of some function f will try and produce its pre-image by guessing, and the author shows this probability to be greater than 2^-n. Is there any reason for this? It also says that this sum is minimized when all the values to be squared are equal why is this obvious?

enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, use the Cauchy-Schwarz inequality $(x \cdot y)^2\leq (x \cdot x)(y \cdot y)$ with equality if and only if $x$ and $y$ are parallel.

In particular, take $x = (x_1, \dots, x_n)$ and $y = (1, \dots, 1)$, so $$x \cdot y = \sum_{i=1}^n x_i = 1$$ $$x \cdot x = \sum_{i=1}^n x_i^2$$ $$y \cdot y = n$$ hence $$\sum_{i=1}^n x_i^2 \geq \frac{1}{n}.$$