# Rank of random binary string with Bernoulli distribution

For $$1\ge p_1 \ge \dots \ge p_n \ge 0$$, and for $$i\in[n]$$ draw $$k$$ iid binary strings with $$m$$ length: $$X_{i,1},\dots,X_{i,k}\stackrel{iid}{\sim} \text{Bernoulli}(p_i)^m.$$ Viewing these binary strings as integers, define their ranks as $$\text{rank}(i,s):=\#\{j\in[n]:X_{j,s}\ge X_{i,s}\}, \qquad \text{MinRank}(i):=\min_{s\in[k]} \text{rank}(i,s).$$

If we assume that $$p_1> c p_j$$ for some $$c>1$$ and all $$j\ge 2$$, what can be said about $$\text{MinRank}(1)$$? Namely, what is the best (small) $$\delta$$ such that $$\Pr\big(\text{MinRank}(1)> r\big) \le \delta(c,n,k,r)$$ Alternatively, can it be bounded in expectation? $$\mathbb{E} [\text{MinRank}(1)] \lesssim \rho(c,n,k)$$

Update: Upon excellent suggestion by @D.W., let us assume $$p_j=p_1/c$$ for all $$j\ge 2$$. We have \begin{align} \Pr(rank(i,s)=r) = \binom{n}{r} \Pr(X_2>X_1)^r\Pr(X_2\le X_1)^{n-r}\\ = \binom{n}{r} (p_2(1-p_1))^r(p_1(1-p_2))^{n-r}\\ = (p_1(1-p_2))^n \underbrace{\binom{n}{r}}_{\le (ne/r)^r}\left(\underbrace{\frac{p_2(1-p_1)}{p_1(1-p_2)}}_{\le p_2/p_1 = c}\right)^r\\ \implies \Pr(rank(i,s)\ge r)\le (p_1(1-p_2))^n\sum_{s=r}^n (\frac{ne}{c s })^s \\ \Pr(MinRank(i)> r)=\Pr(rank(i,1)\ge r)^k \end{align} Not exactly sure how to bound the $$\sum_{s=r}^n (\frac{ne}{c s })^s$$ term

• What are the best results you've been able to attain so far?
– D.W.
Jul 20, 2022 at 16:09
• What progress have you made? The worst case is presumably $p_j=p_1/c$ for all $j\ge 2$. For those $p$'s, can you calculate $\Pr[X_{j,s} \ge X_{1,s}]$? Can you calculate the probability distribution of $\text{rank(1,s)}$?
– D.W.
Jul 20, 2022 at 20:02