Probability of a randomly sampled subset being Byzantine I have been working on writing a white paper to describe a consensus algorithm I have been creating. Please note I am a computer scientist, not a mathematician, though I am happy to do lots of reading on any topics people link in. I like to understand the why of a solution, not just the solution.
The problem at hand is, I have n validators, where ε percent of them are controlled by an adversary. These n validators are shuffled using a random fisher Yates shuffle. They are then split into k uniform “shards” or committees. Each committee has an equal number of validators in it.
A committee can be considered Byzantine/corrupt if more than 3/4c (where c is the number of validators per committee, aka n/k) members are controlled by the adversary.
Given this information (ε, n, k, c) and assuming a random shuffling of the “list” of the validators can we calculate the probability of a random sample producing a set of committees where one or more committees are “corrupt”?
I know that there can be n choose k possible combinations, but am stuck on how to take this combined with the percentage of validators who are adversary (ε) and produce a probability.
A more generic expression of the above problem is to imagine there are n coloured pieces of card, a card can be either red or green. ε percent of the cards are red. The cards are shuffled with a truly random & unpredictable shuffling algorithm. Then the top n/k cards are taken from the top of the pile and placed into their own pile, this is done k times. The colour of the card is unknown until all cards have been split into cards (ie the cards are face down)
EYou now have k piles of cards of length c (where c = n/k). Each pile's cards colour is then revealed (ie flipped over) and then tested using the following rule: "if 3/4 or more of the cards in a pile is red, then that pile is RED, otherwise that pile is GREEN)."
What is the probability that at least one of the sampled piles is RED, and the probability of i piles being red (while k - i piles are green).  (given ε, n, k)
Thank you very much, and any help is greatly appreciated. Please let me know if my notation or terminology is incorrect or if I can improve the way I have asked my question.
 A: Given
$$
\begin{align}
n & \text{ : the number of validators}, \newline
k & \text{ : the number of committees}, \newline
\varepsilon & \text{ : the percentage of adversarial validators}, \newline
c & \text{ : the number of validators per committee} = \bigg\lfloor \frac n k \bigg\rfloor
\end{align}
$$
Let
$$
C_i : \text{ the set of validators in committe $i$}.
$$
There are $\lfloor \varepsilon n \rfloor$ corrupt validators in total. If $v = \frac {3\lfloor n/k \rfloor} 4$ or more corrupt validators are assigned to a single committee then we have a vulnerable assignment.
For a committee to be vulnerable, the probability is given by
$$
\pi = \overbrace{{\frac {\lfloor \varepsilon n \rfloor} {n}} \times {\frac {\lfloor \varepsilon n \rfloor - 1} {n-1}} \cdots \times {\frac {\lfloor \varepsilon n \rfloor - (v-1)} {n-(v-1)}}}^{v \text{ adversarial validators}} \times \overbrace {1 \times 1 \times \cdots \times 1}^{\lfloor n/k \rfloor -v \text{ times}}
$$

Note: The above calculation is similar to picking $v$ red balls from an urn containing red and white balls while picking $\lfloor n/k \rfloor$ total balls without replacement.

For a committee to be invulnerable, the probability is
$$
p = 1 - \pi
$$
For $k$ committees to be invulnerable, we should use conditional probabilities (because the $j$-th committee being invulnerable depends on the previous $j-1$ committees' vulnerability statuses):
The probability that $C_1$ is invulnerable is
$$p_1 = p = 1 - \pi.$$
The probability that $C_2$ is invulnerable is
$$
\begin{align}
p_2 & = P(C_2 \text{ is invulnerable}|C_1 \text{ is invulnerable}) \\
    & = \frac {P(C_2 \text{ is invulnerable} \land C_1 \text{ is invulnerable})} {P(C_2 \text{ is invulnerable})} \\
    & = \frac {p \times p} {p} \\
    & = p  
\end{align}
$$
The probability that $C_3$ is invulnerable is
$$
\begin{align}
p_2 & = P(C_3 \text{ is invulnerable}| C_2 \text{ is invulnerable}\land C_1 \text{ is invulnerable}) \\
& = \frac {P(C_3 \text{ is invulnerable} \land C_2 \text{ is invulnerable}\land C_1 \text{ is invulnerable}} {P(C_3 \text{ is invulnerable})} \\
& = \frac {p \times p \times p} p \\
& = p^2
\end{align}
$$
Similarly, the probability that $C_j$ is invulnerable is
$$p_j = p^{j-1}$$
The probability that all $C_i$ are invulnerable is
$$
\begin{align}
\prod_{i=1}^k p_i & = p \times p \times (p^2) \times (p^3) \times \cdots \ (p^{k-1}) \\
 & = p \cdot p^(1 + 2 + \cdots + k-1) \\
 & = p \cdot p^{(k-1)k/2} \\
 & = p^{(k-1)k/2 + 1}
\end{align}
$$
The probability that at least one committee is vulnerable is given by
$$
1 - p^{(k-1)k/2 + 1}
$$
