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.



An "obvious" probability lemma about random words
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](https://arxiv.org/abs/1803.09663v1): 



> 
> $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. 


