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

  • $\begingroup$ What are the best results you've been able to attain so far? $\endgroup$
    – D.W.
    Jul 20, 2022 at 16:09
  • 2
    $\begingroup$ 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)}$? $\endgroup$
    – D.W.
    Jul 20, 2022 at 20:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.