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.
 A: 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. 
A: 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.
