Probability of $\max_i \{X_i\} = X_0$ where $X_i$ are iid binomial

Question

We have $M$ Binomial random variables, where $X_0 \sim $ Bin$(n,p)$ and $X_i \sim $ Bin$(n,1/2)$.

Suppose $p > 1/2$. I'm interested in the probability that $\mathbb{P}(\max \{X_1,\dots,X_M\} \geq X_0)$. Is this tractable?

If not, is it tightly boundable/approximable? If this is a very difficult question, I'd accept a reference providing some insight on the problem as well.

Answer 1

$P( \max \{X_1,...,X_M \} \geq X_0)=P(X_i \geq X_0$ for some i) = $1-P( \text{each }X_i < X_0)$.
Now $P( \text{each }X_i < X_0)=\sum_{k=0}^n P(\text{each }X_i<X_0 \vert X_0=k) \cdot P(X_0 =k)$ =$\sum_{k=0}^n P( \text{each } X_i<k \text{ and } X_0=k)$ = $\sum_{k=1}^n \big[ P(X_1<k) \big]^M \cdot P(X_0=k)$. Note the k=0 term is 0.

Answer 2

The maximum of $\{X_i\}_{i\in\{1;M\}}$ will be at least as great as $X_0$ when it is not that all values are less than $X_0$.   (Employ the rule of complements.)   Assuming that $X_0$ is also independent of the iid variables then: $$\begin{align} \mathsf P\left(\max_{i=1}^M\{X_i\} \geqslant X_0\right) =&~ 1-\sum_{k=1}^n\mathsf P(X_0=k)\mathsf P\Big(\bigcap_{i=1}^M X_i<k\Big) \\ =&~ 1- 2^{-nM} \sum_{k=1}^n\binom{n}{k}p^k(1-p)^{n-k}\left(\sum_{h=0}^{k-1}\binom{n}{h}\right)^M \end{align}$$