A Probability Game Clause Samples

A Probability Game. ‌ We consider the following game that will be used to model the evolution of the component finalization process in the MBBA protocol, and thus the MBA protocol. In particular we want compute the probability distribution associated to the number of steps necessary to win this game. From that, we retrieve the probability distribution associated to the number of MBBA iterations necessary to end the MBA Protocol. The game is the following: we have n coins which flip heads with probability π, at each step we flip the coins and discard the ones which flipped heads, then we carry on with the others until there are no coins left. So, in the first step we flip all n coins, then we discard the h1 coins which flipped heads, in the second step we flip the remaining n − h1 coins and so on. We now compute the probability distribution associated to the number χn,π of steps required to end the game. The probability that a coin flipped heads at least once in w steps is 1 − (1 − π)w, hence, being the coin flips independent, the probability that all coins flipped heads at least once is (1 − (1 − π)w)n. This means that P(χn,π > w) = 1 − (1 − (1 − π)w )n, and from that we can compute P(χn,π = w) = P(χn,π > w − 1) − P(χn,π > w) = (1 − (1 − π)w)n − (1 − (1 − π)w−1)n. This defines the probability distribution associated to the number of steps to end this game played with n coins.