-1
$\begingroup$

I want to know this to know why finding probability by finding complement is more easy in this case?

Question: A sequence of 9 bits is randomly generated. What is the probability that at least one of these bits is a $1$?

Solution:

E is the event that at least one of the 9 bits is 1. The sample space, S, is the set of all bit strings length 9.

$p(E) = 1 - p(\bar E) = 1 - \dfrac{|E|}{|S|} = 1 - \dfrac{1}{2^9} = 1 - \dfrac{1}{512}=\dfrac{511}{512}$

I also want to know in the formula which we used for finding total possible outcomes, i.e $2^9$ what is $2$ generally and what is $9$ generally? How are we using this formula? (What is the logic behind it?)

$\endgroup$

closed as unclear what you're asking by Did, Claude Leibovici, N. F. Taussig, man and laptop, drhab Jun 22 '15 at 11:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 1 - p(-E) = 1 - ( |E| / |S| ) ?? 2^10 what is 2 generally ?? 2^10 does not appear in the question. $\endgroup$ – Did Jun 22 '15 at 7:26
  • $\begingroup$ Sorry I edited it now $\endgroup$ – User Jun 22 '15 at 7:27
  • $\begingroup$ Again: p(-E) = |E| / |S| ?? $\endgroup$ – Did Jun 22 '15 at 7:32
  • $\begingroup$ Yes 1st we found p(-E) ,then p(E). And using same formula as for p(-E) because it is been treated as another p(E) $\endgroup$ – User Jun 22 '15 at 7:35
  • $\begingroup$ Again (last time): p(-E) is not |E| / |S|, never. $\endgroup$ – Did Jun 22 '15 at 9:15
1
$\begingroup$

Why the Possibilities Are $2^9$

Suppose we tossed a fair coin three times. Constructing a list of all possibilities, we have

$$HHH, HHT, HTH, HTT, THH, THT, TTH,TTT $$

which counts for eight possibilities.

If you toss a fair coin four times, there are 16 possibilities, five times there are 32 possibilities, and so on.

We then realize that

$$8 = 2^3$$ $$16 = 2^4$$ $$32 = 2^5$$

where each exponent may be interpreted as the quantity of tosses.

Therefore, if there are two possibilities that both have an equal chance of occurring for some operation, and we perform that operation k times, it follows that the total number of possibilities is

$$2*2*2*...*2 = 2^k$$

where $k\in\mathbb{Z^+}\cup$ {0}

This is called the fundamental counting principle, or the multiplication rule.

Therefore, since there are 2 possibilities, a 0 or a 1, and we are making a selection 9 times (with replacement, I might add), it follows that we multiply all the possibilities together--hence

$$2^9 = 512$$

Why, in This Case, the Complement of the Desired Event is Better to Compute than Directly Computing the Desired Event

If we let $x$ represent the number of 1 bits that occur in a bit string of length 9, we realize that we have quite a number of possibile bit strings that may be generated with atleast 1 bit in the string.

Well, suppose that we consider the set of bit strings of length 9 which has one 1 and eight 0's. Convince yourself that the 1 can appear anywhere in string with the 0's allocating the remaining positions. Here are all the possibilities

$$100000000$$ $$010000000$$ $$001000000$$ $$000100000$$ $$000010000$$ $$000001000$$ $$000000100$$ $$000000010$$ $$000000001$$

Counting up the possibilites, we see that there are 9 possibilities. In fact, these 9 possibilities come from a set of all bit strings of length 9 that has only one 1. Therefore, if we let $A$ represent the set that contains those bit strings enumerated above, it is clear that $A\subset S$. Hence $|A|=9$. We have a handy notation for calclating the number of elements in a subset, and in this case it is

$${9 \choose 1} = 9$$

If we wanted three 1s to appear in our string, then the probability of getting three 1s is $(1/2)(1/2)(1/2)$ = $(1/2)^3$ = 1/8, while the number of 0s allocated the number of remaining positions, which is $9-3=6$; therefore, the probability of 0s is $(1/2)^{9-3}$ = $(1/2)^6$ = $1/64$. Since the 1s can appear anywhere in the bit string, we account for all those possibilities by writing ${9\choose3}$

Notice the pattern: If, for instance, we want 5 os, the exponent for the probability of obtaining five 1s is $5$ while the exponent for the probability of 0s is $9-5 = 4$. Therefore, if we wanted the probability for $k$ 1s, the exponent for the corresponding probability would be $k$, and the exponent for the corresponding probability for the 0s is $9-k$. Accounting for all possible places the sequence of 1s could appear is ${9\choose k}$. We are now ready to construct a formula

The probability of obtaining at least one 1 in a bit string of length 9 is

$$\sum_{k=1}^9{9 \choose k}\left(\frac{1}{2}\right)^x\left(\frac{1}{2}\right)^{9-x} = \frac{511}{512}$$

Now, an easier way to compute this is to realize that the complement of the probability of obtaining at least one 1 is one minus the probability that no 1s occur.

Well, no 1s occuring means that all nine positions have 0s. Therefore, the probability of obtaining 0s in all nine positions is multiplying $\frac{1}{2}$ nine times, or $\frac{1}{2^9} = \frac{1}{512}$ Subtracting this result from 1 renders $1-\frac{511}{512} = \frac{1}{512}$, which confirms the above result.

Much easier!

$\endgroup$
0
$\begingroup$

The complement of an event or set $E$ is usually denoted as $E^c$.

In general, for a sequence of items of length $N$ and $k$ possible choices per item we have a total of $k^N$ possible outcomes. In your example you have $k = 2$ choices per bit ($0$ or $1$) and $N = 9$ items.

For your specific example: there is only one way in which we can get all bits equal to $0$ (the event $E^c$), so the probability of having all $9$ bits equal to $0$ is

\begin{equation} \mathbb{P}(\textrm{only $0$'s}) = \frac{\textrm{Number of outcomes that have only $0$'s}}{\textrm{Total number of possible outcomes}} = \frac{1}{2^9}. \end{equation}

It is easier to find the probability of the event $E^c$ since there is only one way in which it can happen. This makes the analysis much easier. If you want to compute the probability that there is at least $1$ zero, then you need to sum the probabilities of having $1$ zero, $2$ zeros, ..., $9$ zeros and those probabilities are more difficult to compute.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.