# An "obvious" probability lemma about random words

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.

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.

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.

• (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$. Mar 15, 2020 at 21:01
• @IosifPinelis Thanks for the comments, now I think it is correct. Mar 15, 2020 at 23:31
• Now I don't see any reasons for your main claims: (i) "the RHS is smaller than" and (ii) "which is clearly smaller". Mar 15, 2020 at 23:44
• 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. Mar 16, 2020 at 9:51
• (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. Mar 16, 2020 at 13:47