2
$\begingroup$

Fix some positive integers $p,n,k$. Let $w$ be chosen uniformly at random from $[k]^n$ (the set of $n$ length words/sequences where each entry is in $\{1,\ldots,k\}$). Let $A_i$ be the event that $w_r=i$ for at least $p$ values of $r$. Can one prove that, for all $s$, $$\Pr\left(\bigwedge_{i=1}^{s-1} A_i\ \large|\ A_s^c\right)\ge \Pr\left(\bigwedge_{i=1}^{s-1} A_i\right).$$ In other words, if we know some letter appears few times, is it more likely that other letters appear many times? Intuitively it seems like this result must be true, but I don't have a good argument to prove it.

$\endgroup$

2 Answers 2

4
$\begingroup$

The property in question is a special case (with the probabilities of all the $k$ outcomes equal to one another) of the known $NA$ (negative association) property of the multinomial distribution; see e.g. this sentence in the bottom paragraph on page 5:

$NA$ property of multinomial distributions can be seen from Condition $N$, since it is the conditional distribution of independent Poisson random variables given their sum.


Indeed, for each $i\in[k]:=\{1,\dots,k\}$, let $N_i$ denote the number of times the letter $i$ appears in the random word of length $n$. Then $(N_1,\dots,N_k)$ has the $k$-nomial distribution with parameters $n,1/k,\dots,1/k$, and the inequality in question can be written as $$P(N_1\ge p,\dots,N_s\ge p)\le P(N_1\ge p,\dots,N_{s-1}\ge p)P(N_s\ge p)$$ or, equivalently, as $$Cov\,\big(f(N_1,\dots,N_{s-1}),g(N_s,\dots,N_k)\big)\le0,$$ where $f$ and $g$ are the functions (nondecreasing in each argument) given by formulas $$f(n_1,\dots,n_{s-1}):=1_{n_1\ge p,\dots,n_{s-1}\ge p}$$ and $$g(n_s,\dots,n_k):=1_{n_s\ge p}\,;$$ cf. Definition 2.1 of $NA$ in the linked paper.

$\endgroup$
2
$\begingroup$

I think it is easier if you rewrite your inequality as \begin{align} & P( \bigcap_{i=1}^{s-1}A_i ) - P ( \bigcap_{i=1}^{s-1}A_i \cap A_s) \geq P(\bigcap_{i=1}^{s-1}A_i)(1-P(A_s)) \\ & \iff P(A_s) \geq P(A_s | \bigcap_{i=1}^{s-1}A_i). \end{align} Now let $\{X_i\}_{i=1}^n$ be the random variables which indicate if the $i-th$ letter is $s$ or not. (Bernouli independent random variables with success probability $1/k$) Let also $N_{s-1}$ is the random variable which counts how many times the letters $\{1,\dots,s-1\}$ appear in a given random word. Then the LHS is exactly $$P(\sum_{i=1}^nX_i \geq p )$$ while the RHS is smaller than $$ P(\sum_{i=1}^{n-N_{s-1}}X_i\geq p| N_{s-1}\geq (s-1)p),$$ which is clearly smaller.

$\endgroup$
7
  • 1
    $\begingroup$ (i) Your latter probability is undefined, because you have not defined the joint distribution of $N_{s-1}$ and the $X_i$'s. (ii) How come the definition of $N_{s-1}$ does not involve $p$? (iii) The success probability should be $1/k$, not $1/n$. $\endgroup$ Mar 15, 2020 at 21:01
  • $\begingroup$ @IosifPinelis Thanks for the comments, now I think it is correct. $\endgroup$ Mar 15, 2020 at 23:31
  • $\begingroup$ Now I don't see any reasons for your main claims: (i) "the RHS is smaller than" and (ii) "which is clearly smaller". $\endgroup$ Mar 15, 2020 at 23:44
  • $\begingroup$ the first smaller than is because since you assume that each of the s-1 first letters appears at least p times, this is less likely than the fact that all the first s-1 all together appear (s-1)p times. The second less than is because you sum less things. $\endgroup$ Mar 16, 2020 at 9:51
  • $\begingroup$ (i) concerning ""the RHS is smaller than": it seems your logic here is that, if $P(B)\le P(C)$, then $P(A|B)\le P(A|C)$. However, this is false in general, even if you assume that $B\subset C$. (ii) concerning "which is clearly smaller": you seem to assume there that the joint distribution of the $X_i$'s is not affected by the condition $N_{s-1}\ge(s-1)p$, which does not seem to be the case. $\endgroup$ Mar 16, 2020 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.