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}^{s1} A_i\ \large\ A_s^c\right)\ge \Pr\left(\bigwedge_{i=1}^{s1} 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.
2 Answers
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_{s1}\ge p)P(N_s\ge p)$$ or, equivalently, as $$Cov\,\big(f(N_1,\dots,N_{s1}),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_{s1}):=1_{n_1\ge p,\dots,n_{s1}\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}^{s1}A_i )  P ( \bigcap_{i=1}^{s1}A_i \cap A_s) \geq P(\bigcap_{i=1}^{s1}A_i)(1P(A_s)) \\ & \iff P(A_s) \geq P(A_s  \bigcap_{i=1}^{s1}A_i). \end{align} Now let $\{X_i\}_{i=1}^n$ be the random variables which indicate if the $ith$ letter is $s$ or not. (Bernouli independent random variables with success probability $1/k$) Let also $N_{s1}$ is the random variable which counts how many times the letters $\{1,\dots,s1\}$ 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}^{nN_{s1}}X_i\geq p N_{s1}\geq (s1)p),$$ which is clearly smaller.

1$\begingroup$ (i) Your latter probability is undefined, because you have not defined the joint distribution of $N_{s1}$ and the $X_i$'s. (ii) How come the definition of $N_{s1}$ 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 s1 first letters appears at least p times, this is less likely than the fact that all the first s1 all together appear (s1)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(AB)\le P(AC)$. 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_{s1}\ge(s1)p$, which does not seem to be the case. $\endgroup$ Mar 16, 2020 at 13:47