Probability of elements in a subset of the original set

Question

Let me try and rephrase the question as an example. I'll use bits since its convenient in this case.

You have 3 bits A, B and C, that have probability 1/2 of being 1 and 1/2 of being 0.

We take $A^{-1}$ as the inverse of A, i.e. $1-A$.

We calculate the following values (all $2^3$ combinations):

$A*B*C\\ A*B*C^{-1}\\ A*B^{-1}*C\\ A*B^{-1}*C^{-1}\\ A^{-1}*B*C\\ A^{-1}*B*C^{-1}\\ A^{-1}*B^{-1}*C\\ A^{-1}*B^{-1}*C^{-1}$

Only one of these will have the end result of 1, with probability 1/8, yes?

So say the result is [0,0,0,1,0,0,0,0]. The 1 would be at index 4 and for all indexes i it holds that the probability it is 1 is 1/8, yes?

So now look only at the first 5 indexes, the results [0,0,0,1,0]. Does the value of 1 still have a uniformly distributed chance of being at any of the 5 possible indexes in the list?

If you uniformly generate a 1 within a group of size $2^n$, and you than use only a subgroup of this group, the elements remain uniformly distributed?

Answer 1

Here’s how I understand the question:

You have an $n$-bit string $b_1b_2\dots b_n$. For each bit you flip a fair coin to set that bit to $0$ or $1$, $0$ for heads and $1$ for tails, say. Each of the $2^n$ possible $n$-bit strings is then equally to be produced. Now for some $m\le n$ you look at the $m$-bit substring $b_1b_2\dots b_m$, and you want to know whether each of the $2^m$ possible outcomes is equally likely.

The answer is yes: each of the $2^m$ $m$-bit strings can be extended in $2^{n-m}$ ways to an $n$-bit string, so each of them occurs with probability

$$\frac{2^{n-m}}{2^n}=\frac1{2^m}\;.$$