Upper bound of the sum of probabilities

Question

Let $X$ be a discrete random variable, such that $X\in \{1,\ldots, k\}$. Let $P(X=i)=p_i$, for $i=1,\ldots, k$ and $p_1+\ldots p_k=1$. I want to find an upper bound for the following expression $$ \sum_{j=1}^{k}\sum_{m\neq j}p_{j}(1-p_j)p_{m} + \sum_{j=1}^{k}\sum_{m\neq j}p_{j}(1-p_m)p_{m} + \sum_{j=1}^{k}\sum_{m\neq j}p_{j}p_{m}(1-p_j-p_m) = \sum_{j=1}^{k}\sum_{m\neq j}p_{j}p_{m}(3-2p_j-2p_m). $$ I want to show that it can be bounded above by approximately $\frac{3k}{4}$. Several numerical simulations show that this bound is likely to hold, but I can't show it analytically. I tried to bound $p_m$ between $0$ and $1$, but it turns out that the bound is too loose. Can anyone provide some insights to whether this bound is achievable or not? Thanks!

Answer 1

Let $p_1,...,p_k$ be nonnegative real numbers such that $p_1+\cdots +p_k$=1. \begin{align*} \text{Then}\;\;& \sum_{j=1}^k\sum_{m\ne j}p_jp_m(3-2p_j-2p_m) \\[4pt] \le\;& \sum_{j=1}^k\sum_{m\ne j}3p_jp_m \\[4pt] =\;& 3\sum_{j=1}^kp_j\sum_{m\ne j}p_m \\[4pt] =\;& 3\sum_{j=1}^kp_j(1-p_j) \\[4pt] \le\;& 3\sum_{j=1}^k\frac{1}{4} \\[4pt] =\;& \frac{3k}{4} \\[4pt] \end{align*}