Bounds on $\max_i p_i$ in terms of $\sum_i p_i^2$ Suppose $(p_1,p_2,\ldots,p_d)$ is a discrete probability distribution over $d$ outcomes with $p_i\ge p_{i+1}$
Given the value of $\rho=\sum_{i=1}^d p_i^2$ (aka purity), what are the possible values of $p_1$?
I'm particularly interested in "large-d" regime.
Below is the graph of purity vs $p_1$ for distributions of the form $p_i\propto i^{-c}$. Does the set of feasible points $(\rho,p_1)$  concentrate around this curve when $d\to \infty$?

notebook
Animating the bounds provided in answer below:


 A: You have:
$$
\sum_{i=1}^d p_i^2 \leq \max_i p_i \cdot \sum_{i=1}^d p_i = \max_i p_i
$$
while, by monotonicity of $\ell_p$ norms, $\|p\|_\infty = \max_i p_i \leq \|p\|_2$. So overall
$$
 \|p\|_\infty \leq \|p\|_2 \leq \sqrt{\|p\|_\infty} \tag{$\dagger$}
$$
which cannot be improved in general: the lower bound is tight for point masses ($p_1=1, p_i=0$ for $i\geq 2$), the upper bound is tight for the uniform distribution ($p_i = 1/d$ for all $i$).
With that in hand: back to your question, you can check that, given $\rho$, there exists some $\alpha = \rho^2 + O(1/d)$ such that, setting $p_1=\alpha^2$ and $p_i = \frac{1-\alpha}{d-1}$ for $i\geq 2$, we get $\|p\|_2^2=\rho$ and $\|p\|_\infty^2 = \alpha$.
On the other side, for $d$ large enough, setting $p_1=\dots=p_D=\rho^2$ for $D=\lfloor 1/\rho^2\rfloor$ and $p_i=\frac{1-D\rho^2}{d-D}$ for $i\geq D+1$, you get $\|p\|_2^2=\rho+o(1/d)$ and $\|p\|^2_\infty=\rho^4$.
So again, even under the impurity ("collision probability") constraint $\|p\|_2^2=\rho$, the inequality $(\dagger)$ cannot be improved.
A: The range of $p_1$ is given by $[\alpha, \beta]$ where
$$\beta = \frac{1}{d} + \sqrt{\rho - \frac{\rho}{d} - \frac{1}{d} + \frac{1}{d^2}}$$
and
$$\alpha = \frac{1}{m} + \frac{1}{m}\sqrt{\frac{m\rho - 1}{m-1}}$$
where $m = \lfloor 1/\rho\rfloor + 1$.
Moreover, $p_1 = \beta$ if $p_2 = p_3 = \cdots = p_d = \frac{1}{d} - \frac{1}{d}\sqrt{\frac{d\rho - 1}{d-1}}$;
$p_1 = \alpha$ if
$p_1 = p_2 = \cdots = p_{m-1} = \alpha$
and $p_m = \frac{1}{m} - \sqrt{\rho - \frac{\rho}{m} - \frac{1}{m} + \frac{1}{m^2}}$ and $p_{m+1} = \cdots = p_d = 0$.
Proof:
(1) Prove that $p_1 \le \beta$
We have
$$1 - p_1 = p_2 + p_3 + \cdots + p_d
\le \sqrt{(d-1)(p_2^2 + p_3^2 + \cdots + p_d^2)} = \sqrt{(d-1)(\rho - p_1^2)}$$
or
$$-dp_1^2 + 2p_1 + d\rho - \rho - 1 \ge 0$$
which results in
$$p_1 \le \beta.$$
(2) Prove that $p_1 \ge \alpha$
Let $y_1 = y_2 = \cdots = y_{m-1} = \alpha$ and $y_m = \frac{1}{m} - \sqrt{\rho - \frac{\rho}{m} - \frac{1}{m} + \frac{1}{m^2}}$ and $y_{m+1} = \cdots = y_d = 0$.
If $p_1 < \alpha$, then
$(p_1, p_2, \cdots, p_d)$ is majorized by
$(y_1, y_2, \cdots, y_d)$.
By Karamata's inequality,
we have
$$p_1^2 + p_2^2 + \cdots + p_d^2
< y_1^2 + y_2^2 + \cdots + y_d^2 = \rho.$$
This is impossible.
We are done.
A: Think of it as an optimization problem, and in particular try using Langrange multipliers. Maximize $p_1$ subject to $\sum p_i = 1$ and $\sum p_i^2 = \rho$.
You should get the Langrangian:
$$
\mathcal{L}(p, \lambda, \mu) = p_1 + \lambda\bigl(\sum p_i - 1\bigr) + \mu \bigl(\sum p_i^2 - \rho\bigr).
$$
From there, you get the system of equations
$$
\begin{align}
p_1 + \lambda + 2\mu p_1 &= 0\\
\lambda + 2\mu p_i &= 0, \text{ for } i\ge2\\
\sum p_i &= 1\\
\sum p_i^2 &= \rho.
\end{align}
$$
Note that the constraint $p_i \ge p_{i+1}$ doesn't matter, because we can just rearrange them.
Solving the system will give you an expression for $p_1$ in terms of $\rho$.
