长度为N的随机比特数组中1块的期望数量及M块概率求解

Great question! Let's start with the expected number of 1-blocks, since linearity of expectation makes this straightforward even without calculating the full probability distribution.

First, define indicator variables for each position in the bit array:

• Let ( X_1 = 1 ) if the first bit is 1 (meaning we start a 1-block here), otherwise 0.
• For ( 2 \leq i \leq N ), let ( X_i = 1 ) if the ( (i-1) )-th bit is 0 and the ( i )-th bit is 1 (meaning we start a new 1-block at position ( i )), otherwise 0.

The total number of 1-blocks ( X ) is the sum ( X = X_1 + X_2 + \dots + X_N ). By linearity of expectation, we can compute ( E[X] ) as the sum of the expectations of each ( X_i ):

• ( E[X_1] = P(\text{first bit is 1}) = \frac{1}{2} )
• For ( i > 1 ), ( E[X_i] = P(\text{bit } i-1 \text{ is 0 AND bit } i \text{ is 1}) = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4} )

Adding these up:
[
E[X] = \frac{1}{2} + (N-1) \times \frac{1}{4} = \frac{N + 1}{4}
]

Let's test this with a small example: for ( N=2 ), the expected value is ( (2+1)/4 = 3/4 ), which matches the average of 0 (from 00), 1 (from 01,10,11) — total average ( (0+1+1+1)/4 = 3/4 ). Perfect!

Now for the probability of having exactly ( M ) 1-blocks. We'll break this down using combinatorial counting:

Key Observations: #

A bit array with exactly ( M ) 1-blocks has a structure where the 1-blocks are separated by at least one 0 (except possibly at the start/end of the array). Using combinatorial arguments (specifically stars and bars and combining binomial coefficients), we can show that the number of such arrays is given by the binomial coefficient ( \binom{N+1}{2M} ), with edge cases handled naturally:

• If ( M = 0 ): The only array is all 0s. ( \binom{N+1}{0} = 1 ), which matches.
• If ( 2M > N+1 ): It's impossible to have ( M ) 1-blocks (the maximum number of 1-blocks is ( \lceil N/2 \rceil ), e.g., alternating 1s and 0s like 1010...). Here ( \binom{N+1}{2M} = 0 ), which correctly gives a probability of 0.

Final Probability Formula: #

Since there are ( 2^N ) total possible bit arrays (each bit independent), the probability of exactly ( M ) 1-blocks is:
[
P(M) = \frac{\binom{N+1}{2M}}{2^N}
]

Let's verify with ( N=3 ), ( M=1 ): ( \binom{4}{2} = 6 ), so probability ( 6/8 = 3/4 ). The valid arrays are 001, 011, 111, 110, 100, 010 — that's 6 arrays, which checks out.

Another example: ( N=4 ), ( M=2 ): ( \binom{5}{4} =5 ), probability (5/16). The valid arrays are 0101, 1001, 1010, 1011, 1101 — exactly 5, correct.

内容的提问来源于stack exchange，提问作者Vinícius Godim