Relationship between two measures of inequality Let $A = \{a_1,\dots,a_n\}$ be a multi-set and let $B$ be the set of distinct elements in $A$. Now define $H(A) = -\frac1n \sum_{x \in B} f(x) \log_2(f(x)/n)$ where $f(x)$ is the number of times $x$ occurs in $A$.  Now consider two indices $i,j\in\{1,\dots,n\}$ chosen uniformly at random and let $p = \Pr(a_i = a_j)$. 

What is the relationship between $2^{H(A)}$ and $1/p$?

Clearly, $2^{H(A)}= 2^n$ iff $1/p = 2^n$. Similarly $H(A)=0$ iff $2^{H(A)}=1/p$,  but they don't always have to be equal.   
 A: We have $n$ elements in $A$ that can be grouped in  $K$ groups, each group having $q_k$ ($k=1\cdots K$) equal elements ( $\sum_{k=1}^K q_k = n$).
Then the probability that two randomly chosen elements (with replacement) belong to the same group is
$$p= \sum_{k=1}^K \left(\frac{q_k}{n}\right)^2 = \sum_{k=1}^K r_k^2 $$
where $r_k=q_k/n$
Hence  $\log p =  \log \sum_{k=1}^K r_k^2  $, and using Jensen inequality, $E \log (\cdot) \le \log E  (\cdot)$ we get
$$\log p \ge  \sum_{k=1}^K r_k \log r_k = -H $$
Or
$$ 2^H \ge \frac{1}{p}$$
Equality occurs when $r_k$ is constant over its support, i.e. when $q_k$ is either zero or a constant. That is, iff the multiset if formed by equally sized groups.
Update: regarding some upper bound on the difference, it looks more difficult. A glance to this seems to lead to:
$$0\le \Delta=\log \frac{1}{p}-H  \le \max_{0\le t \le 1}_{K=1 \cdots n} \psi(n,K,t)$$
with
$$\psi(n,K,t) = \log \left(\frac{t}{n} + (1-t) \frac{n-K+1}{n}\right) - (1-t) \log \frac{n-K+1}{n} -t \log  \frac{1}{n} $$
but this doesn't look very nice.
