PROBABILITY AND COUNTING TECHNIQUES

 

“KEY CONCEPTS AND FORMULAS”

 

(A) SETS

 

1.       DEFINITION OF A SET: A set is a well-defined collection of distinct objects, called the elements or

members of the set. One way of describing a set is by listing its elements in a “Roster.”

 

For example: A = {a, e, i, o, u}; X = {0, 8, 2, 3, 7, 10}; etc.

 

NOTE: When the list is extensive and the pattern is obvious, an ellipsis may be used.

 

For example: B = {a, b, c, …, z}.

 

NOTE: The above form is also called the Tabular Form of the Set. The elements of a set are separated by commas and are enclosed in brackets {   }.

    

2.       SUBSET: A is a subset of B if every element in set A is also in set B. The notation is A Í B. NOTE:

Every set is a subset of itself, i.e., A Í A, where A is any set.

 

3.   NULL OR EMPTY SET: The null or empty set is the set with no elements. The notation is Æ  or {  }.

 

NOTE: The empty set is a subset of every set, i.e., Æ Í A, where A is any set.

 

4.    UNIVERSAL SET: The UNIVERSAL SET, U, is the set that contains all possible elements under consideration in a problem.

 

5.    NUMBER OF SUBSETS OF A SET: If a set contains “N” elements then the number of subsets is equal to 2N and the number of proper subsets is equal to 2N - 1.

 

6.    POWER SET: The set of all the distinct subsets of a set A is called the power set of A. The notation is P(A). Thus, if n(A) = N, then n(P(A)) = 2N, where A is any finite set.

 

7.     UNION OF SETS: The union of sets A and B is the set of all elements which are either in A or in B. The notation is A È B. Thus A È B = {x | x Î A or x Î B or x Î both A and B}.

 

8.     INTERSECTION OF SETS: The intersection of sets A and B is the set of all those elements, which are common to both A and B. The notation is A Ç B. Thus A Ç B = {x | x Î A and x Î B}.

 

9.    COMPLEMENT OF A SET: Let A be a set and U the universal set. Then the complement of set A with respect to the universal set U is the difference of sets U and A, i.e., U – A, and is denoted by

        _

A/  or A. Thus A/ = {x | x Î U and x Ï A}.

 

10.    DISJOINT SETS: Any two sets A and B are said to be disjoint if and only if A Ç B = Æ.

 

11.    VENN DIAGRAMS: We can visualize sets and operations on sets and guess the truth of a number of propositions on sets with the help of geometric diagrams, known as Venn diagrams. A convenient way to use Venn diagrams is to represent the universal set U by rectangular area in a plane and the elements which make up U by the points of this area. Simple plane areas bounded by circles or their parts drawn within the rectangular area can give a simple and instructive picture of sets and operations on sets. We can think of each set as consisting of all points within the corresponding circle.

 

(B) PROBABILITY

 

1. PROBABILITY EXPERIMENT: A probability experiment refers to any act or process or procedure that can be performed that yields a collection of outcomes (or results). The outcome of the probability experiment is not known in advance of the act. For example:

 

(i) The act of tossing a fair coin.

 

(ii) The act of rolling a fair die.

 

(iii) The act of drawing a single card from an ordinary deck of 52 playing cards.

    

2. SAMPLE SPACE: A sample space is defined as the set of all possible outcomes (or results) that can occur in a probability experiment such that exactly one outcome occurs at a time. The letter S will be used to denote a sample space. In a Venn diagram, a rectangle will be used to represent a sample space and the outcomes which make up S by the points drawn within this rectangle.

 

For example:

 

(i) If a fair coin is tossed, there are two possible, equally likely outcomes in the sample space that could occur in this experiment (Heads, H, or Tails, T). Thus S = {H, T}.

 

(ii) If a fair die is rolled, then S = {1, 2, 3, 4, 5, 6}.  

 

3. EVENT: An event is any collection of results or outcomes of a probability experiment. Thus, an event may be defined as any subset of the sample space. For example:

 

(i) If a fair coin is tossed, each of the two individual outcomes (Heads, H, or Tails, T) may be referred to as events since the sets {H} and {T} are subsets of S = {H, T}.

 

(ii) If a fair die is rolled, then each of the individual outcomes in this probability experiment is an event because {1}, {2}, {3}, {4}, {5}, and {6} are subsets of S = {1, 2, 3, 4, 5, 6}.

 

Similarly, {1, 3, 5} and {2, 4, 6} represent the events of rolling an odd number and an even number on the die respectively. Note that no two outcomes can occur at the same time.  

 

The event of rolling a 7 on a die is Æ  or {  } because Æ is a subset of S, i.e. Æ Í S.  

 

Notations: The capital letters such as A, B, C, D, E, etc. will be used to denote an event. In a Venn diagram, a circle drawn within the rectangle will be used to represent an event and the outcomes which make up the event by the points of this circle.

 

4. SIMPLE EVENT: A simple event is an outcome or an event that cannot be further broken down. For example:

 

(i) If a fair coin is tossed, each of the two individual outcomes (Heads, H, or Tails, T) may be referred to as simple events.

 

(ii) If a fair die is rolled, then each of the individual outcomes {1}, {2}, {3}, {4}, {5}, and {6} is a simple event.

  

5. COMPOUND EVENT: A compound event is any event combining two or more simple events. For example:

 

(i) If a fair die is rolled, then {1, 3, 5} and {2, 4, 6} may be referred to as compound events.

 

6. COMPLEMENT OF AN EVENT: Let E be any event and S the sample space of a probability experiment. Then the complement

                                                                                                   _

of the event E with respect to the sample space S, denoted by E/  or E, consists of those outcomes which are not in E, i.e.

 

E/ = {x | x Î S and x Ï E}. For example:

 

(i) If a fair die is rolled, then {1, 3, 5} and {2, 4, 6} may be referred to as complementary events of each other.

 

7. FORMULAS:

 

Let and  be any two events from the sample space of a probability experiment. Let  the number of outcomes in  and  the number of outcomes in. Let denote the probability of event  occurring, and  denote the probability of event  occurring.

 

(i) PROBABILITY OF AN EVENT:  (Classical Probability)

 

(ii) PROBABILITY OF AN IMPOSSIBLE EVENT: If the event  cannot occur, then.

 

(iii) PROBABILITY OF A CERTAIN EVENT: If the event  is certain to occur, then.

 

(iv) The probability of any event  is a number between  and , inclusive, i.e.


(v) ADDITION RULES:

 

(a) FOR MUTUALLY EXLUSIVE EVENTS: The events  and  are called mutually exclusive (or disjoint) if , i.e. they cannot both occur together, i.e. simultaneously. For mutually exclusive events, we have , and the addition rule is defined as follows:   

 

.   

 

(b) FOR NON-MUTUALLY EXLUSIVE EVENTS: The events  and  are not mutually exclusive if , i.e. they both occur simultaneously. In this case, the addition rule is defined as follows:   

 

.   

 

(vi) MULTIPLICATION RULES:

 

(a) FOR INDEPENDENT EVENTS: The events  and  are called independent if the occurrence of one event, say,  does not affect the probability of the occurrence of the other event. The multiplication rule is defined as follows:   

 

.   

 

(b) FOR DEPENDENT EVENTS: The events  and  are called dependent if the occurrence of one event, say,  affects the probability of the occurrence of the other event. In this case, the multiplication rule is defined as follows:   

 

,

 

where  is read as “” and represents the probability of event  occurring after it is assumed that event  has already occurred.  

 

8. FORMULAS (CONTINUED):

 

Let and  be any two events from the sample space of a probability experiment. Let  the number of outcomes in  and  the number of outcomes in. Let denote the probability of event  occurring, and  denote the probability of event  occurring.

 

(i) CONDITIONAL PROBABILITY RULE:

 

(a) DEFINITION: A conditional probability of an event  represents the probability of event  occurring after it is assumed that some other event  has already occurred. It is denoted by .  

 

(b) FORMULA: The conditional probability of event  occurring, given that event  has already occurred, is denoted by , and is given by

 

 , provided , or .  

(ii) PROBABILITY OF THE COMPLEMENT OF AN EVENT: Let  denote the complement of the event  with respect to the sample space . Then

 

The probability that the event  will not occur ;

 

; and .

 

(iii PROBABILITY OF “AT LEAST ONE”:

 

(a) “At least one” is equivalent to “one or more.”

 

(b) “None” and “at least one” are complement of each other.

 

(c) P(at least one) = 1 – P(none) and P(none) = 1 – P(at least one) 

 

 

 

 

 

 

 

 

 

(iv) TESTING FOR INDEPENDENCE:

 

Two events  and  are “independent” if

Two events  and  are “dependent” if

 

 

OR

 

 

 

 

OR

 

 

 

(v) BAYES’ FORMULA:

 

 

9. FORMULAS FOR ODDS:

 

Let  be any event from the sample space of a probability experiment. Let  the number (#) for (in favor of) the event , and  the number (#) against the event . Let  = total number (#) of outcomes in . Then, we have the following definitions:

 

(a) Odds in favor (for) of the event  , or , i.e.

 

Odds in favor (for) of the event  ;

 

(b) Odds against the event  , or , i.e.

 

Odds against the event  ;

 

(c)  , which is the probability in favor of the event ;

 

(d)  , which represents the probability against the event .

 

 

 

 

(C) COUNTING TECHNIQUES

 

(i) FUNDAMENTAL PRINCIPLE OF COUNTING:

 

For a sequence of two events (or choices or tasks), say,  and, in which the first event  can occur  ways and the second event  can occur  ways, the events  and together can occur a total of   ways. Here, none of the two events (or choices or tasks) depends on another.

 

NOTE: The fundamental counting principle easily extends to situations involving more than two events.

 

(ii) FACTORIAL NOTATION:

 

If  denotes an integer, then the factorial symbol  is defined as follows:

 

;

 

;

 

 

 

(iii) FACTORIAL RULE:

 

A collection of  different items (or objects) can be arranged in order  different ways.

 

(iv) PERMUTATION RULE (WHEN ITEMS ARE ALL DIFFERENT):

 

(a) DEFINITION: A permutation is a sequential arrangement of   different (or distinct) items (or objects) taken  at a time, without replacement or repetition, denoted by , where , in which the order makes a difference.

 

(b) FORMULA:  , where .

 

(c) SHORT-CUT FORMULA:  , where .

 

(d) NOTE:  

 

(v) COBINATION RULE:

 

(a) DEFINITION: A combination is a group (or set or collection or selection) of   different (or distinct) items (or objects) taken  at a time, denoted by  or , where , in which the order is not important.

 

(b) FORMULA:  , where .

 

(c) NOTE:  

(vi) PERMUTATION RULE (WHEN SOME ITEMS ARE IDENTICAL OR SIMILAR OR ALIKE TO OTHERS):

 

If there are  items (or objects) with  alike,  alike, … ,  alike, the number of permutations of all  items (or objects) is given by

 

 , where      

 

(vii) APPLICATIONS OF PERMUTATION AND COMBINATION RULES TO PROBABILITY:

 

(a) The probability of a permutation (arrangement) is given by

 

 

(b) The probability of a selection (combination) is given by

 

 

(viii) AN USEFUL FORMULA ON SIMPLE RANDOM SAMPLING:

 

(a) DEFINITION OF A SIMPLE RANDOM SAMPLE:

 

A sample of size  from a population of size  is obtained through simple random sampling if every possible sample of size  has an equally likely chance of occurring. The sample is then called a simple random sample.

 

NOTE: In the above definition, the sample is always a subset of the population with

 

 (b) FORMULA: The number of different simple random samples of size  from a population of size  is defined as a combination of  objects by selecting  at a time without replacement, and is given by the following formula:    

 

 , where .