Return to Revisions

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.