An "obvious" probability lemma about random words

Question

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.

Answer 1

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.

Answer 2

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.