X

Expected Value and Variance

• The expected value of a random variable is a weighted average of the values of a random variable.

• Variance, which tells us how spread out the values of this random variable are

• The expected value, also called the expectation or mean, of the random variable X on the sample space S is equal to E(X) = ∑ s ∈ S p(s)X(s)

• The deviation of X at s ∈ S is X(s) − E(X), the difference between the value of X and the mean of X

• The expected number of successes when "n" mutually independent Bernoulli trials are performed, where "p" is the probability of success on each trial, is np.

Q. Let X be the number that comes up when a fair die is rolled. What is the expected value of X?

• The random variable X takes the values 1, 2, 3, 4, 5, or 6, each with probability 1/6. It follows that

• E(X) = 1/ 6 · 1 + 1/ 6 · 2 + 1/ 6 · 3 + 1/ 6 · 4 + 1/ 6 · 5 + 1/ 6 · 6 = 21/ 6 = 7/ 2 .

Q. A fair coin is ﬂipped three times. Let S be the sample space of the eight possible outcomes, and let X be the random variable that assigns to an outcome the number of heads in this outcome. What is the expected value of X?

• The values of X are the eight possible outcomes when a coin is ﬂipped three times

• Because the coin is fair and the ﬂips are independent, the probability of each outcome is 1/8

• E(X) = 1/ 8 [X(HHH) + X(HHT) + X(HTH) + X(THH) + X(TTH) +X(THT) + X(HTT) + X(TTT)]

• = 1 / 8 (3 + 2 + 2 + 2 + 1 + 1 + 1 + 0)

• = 12 / 8

• = 3 / 2

Q. What is the expected value of the sum of the numbers that appear when a pair of fair dice is rolled?

• Let X be the random variable equal to the sum of the numbers that appear when a pair of dice is rolled. The value of X for the 36 outcomes of this experiment.

• The range of X is {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.

• p(X = 2) = p(X = 12) = 1/36,

• p(X = 3) = p(X = 11) = 2/36 = 1/18,

• p(X = 4) = p(X = 10) = 3/36 = 1/12,

• p(X = 5) = p(X = 9) = 4/36 = 1/9

• p(X = 6) = p(X = 8) = 5/36

• p(X = 7) = 6/36 = 1/6

• E(X) = 2 * 1/36 + 3 * 1/18 + 4 * 1/12 + 5 * 1/9 + 6 * 5/ 36 + 7 * 1/6 + 8 * 5/36 + 9 * 1/9 + 10 * 1/12 + 11 * 1/18 + 12 * 1/36

• = 7

Relations and Their Properties

• Let A and B be sets. A binary relation from A to B is a subset of A × B.

• A binary relation from "A" to "B" is a set "R" of ordered pairs where the ﬁrst element of each ordered pair comes from "A" and the second element comes from "B".

• The notation a R b is used to denote that (a, b) ∈ R. Moreover, when (a, b) belongs to R, "a" is said to be related to "b" by R

• Binary relations represent relationships between the elements of two sets.

Example of binary relations :

• Let "A" be the set of students in your school, and let "B" be the set of courses. Let "R" be the relation that consists of those pairs (a, b), where "a" is a student enrolled in course "b".

• So assume Sanjay dutt is also enrolled in CS510, then the pair (Sanjay dutt, CS510) is in R.

• However, if Sharukh Khan is not enrolled in CS510, then the pair (Sharukh Khan, CS510) is not in R.

• Note that if a student is not currently enrolled in any courses there will be no pairs in "R" that have this student as the ﬁrst element. Similarly, if a course is not currently being offered there will be no pairs in "R" that have this course as their second element.

Q. Let A ={0, 1, 2} and B ={a, b}. Then {(0, a), (0, b), (1, a), (2,b)} is a relation from A to B. This means, for instance, that 0 R a, but that 1 R b. Relations can be represented graphically, as shown in Figure below, using arrows to represent ordered pairs. Another way to represent this relation is to use a table, which is also done in Figure below.

Relations on a Set

• A relation on a set A is a relation from A to A.

Q. Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R ={(a, b) | a divides b}?

• Because (a, b) is in R if and only if a and b are positive integers not exceeding 4 such that a divides b, we see that

• R ={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

Q. Consider these relations on the set of integers: R 1 = {(a, b) | a ≤ b}, R 2 = {(a, b) | a > b}, R 3 = {(a, b) | a = b or a = −b}, R 4 = {(a, b) | a = b}, R 4 = {(a, b) | a = b + 1}, R 5 = {(a, b) | a + b ≤ 3}. Which of these relations contain each of the pairs (1, 1), (1, 2), (2, 1), (1, −1), and (2, 2)?

• The pair (1, 1) is in R 1, R 3, R 4 and R 6; (1, 2) is in R 1 and R 6; (2, 1) is in R 2, R 5 and R 6

• (1, −1) is in R2, R3 , and R6; and

• ﬁnally, (2, 2) is in R1, R3 and R4 .

Q. How many relations are there on a set with n elements?

• A relation on a set "A" is a subset of A × A.

• Because A × A has n2 elements when "A" has "n" elements, and a set with "m" elements has 2m subsets, there are 2n2 subsets of A × A.

• Thus, there are 2n2 relations on a set with "n" elements.

• For example, there are 232 = 29 = 512 relations on the set {a, b, c}.

Properties of Relations

• Reflexive relations : A relation R on a set A is called reﬂexive if (a, a) ∈ R for every element a ∈ A.

• Symmetric and Anti-Symmetric relations : A relation R on a set "A" is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all (a, b ∈ A). A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called anti-symmetric.

• Transitive relations : A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A.

Q. Consider the following relations on {1, 2, 3, 4}: R1 ={(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}, R 2 ={(1, 1), (1, 2), (2, 1)}, R 3 ={(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}, R 4 ={(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, R 5 ={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}, R 6 ={(3, 4)}. Which of these relations are reﬂexive?

• The relations R 3 and R 5 are reﬂexive because they both contain all pairs of the form (a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4).

• The other relations are not reﬂexive because they do not contain all of these ordered pairs. In particular, R 1 , R 2 , R 4 , and R 6 are not reﬂexive because (3, 3) is not in any of these relations.

Q. Is the “divides” relation on the set of positive integers reﬂexive?

• Because a | a whenever a is a positive integer, the “divides” relation is reﬂexive.

• (Note that if we replace the set of positive integers with the set of all integers the relation is not reﬂexive because by deﬁnition 0 does not divide 0.)

• In some relations an element is related to a second element if and only if the second element is also related to the ﬁrst element. The relation consisting of pairs (x, y), where x and y are students at your school with at least one common class has this property.

Q. How many reﬂexive relations are there on a set with n elements?

• A relation R on a set A is a subset of A × A.

• Consequently, a relation is determined by specifying whether each of the n 2 ordered pairs in A × A is in R

• However, if R is reﬂexive, each of the n ordered pairs (a, a) for a ∈ A must be in R.

• Each of the other n(n − 1) ordered pairs of the form (a, b), where a ≠ b, may or may not be in R.

• Hence, by the product rule for counting, there are 2n(n−1) reﬂexive relations

Q. R1 ={(a, b) | a ≤ b}, R2 ={(a, b) | a > b}, R3 ={(a, b) | a = b or a = −b}, R4 ={(a, b) | a = b}, R5 ={(a, b) | a = b + 1}, R6 ={(a, b) | a + b ≤ 3}. Which of these relations are symmetric and which are antisymmetric?

• R3 is symmetric as if a = b or a = -b then b = a or b = -a.

• R4 is symmetric as a = b implies that b = a

• R6 is symmetric because a + b ≤ 3 implies that b + a ≤ 3.

• R1 is anti-symmetric as the inequalities a ≤ b and b ≤ a imply that a = b

• R2 is anti-symmetric because it is possible that a > b and b > a

• R4 is antisymmetric, because two elements are related with respect to R4 if and only if they are equal.

• R5 is antisymmetric because it is impossible that a = b + 1 and b = a + 1.

Q. Consider the following relations on {1, 2, 3, 4}: R1 ={(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}, , R 4 ={(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}. Which of these relations are transitive?

• R4 is transitive, because (3, 2) and (2, 1), (4, 2) and (2, 1), (4, 3) and (3, 1), and (4, 3) and (3, 2) are the only such sets of pairs, and (3, 1), (4, 1), and (4, 2) belong to R4

• R1 is not transitive because (3, 4) and (4, 1) belong to R1 , but(3, 1) does not.

Q. Is the “divides” relation on the set of positive integers transitive?

• Suppose that a divides b and b divides c.

• Then there are positive integers k and l such that b = ak and c = bl. Hence, c = a(kl),soa divides c

• It follows that this relation is transitive.

Combining Relations

• Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relations R1 = {(1, 1), (2, 2), (3, 3)} and R2 ={(1, 1), (1, 2), (1, 3), (1, 4)} can be combined to obtain :-

• R1 ∪ R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)}

• R1 ∩ R2 = {(1, 1)}

• R1 - R2 = {(2, 2), (3, 3)}

• R2 - R1 = {(1, 2), (1, 3), (1, 4)}

Q. Let A and B be the set of all students and the set of all courses at a school, respectively. Suppose that R1 consists of all ordered pairs (a, b), where "a" is a student who has taken course "b", and R2 consists of all ordered pairs (a, b), where "a" is a student who requires course "b" to graduate. What are the relations R1 ∩ R2, R1 ∪ R2, R1 ⊕ R2, R1 - R2 and R2 - R1 ?

• R1 ∪ R2 consists of all ordered pairs (a, b), where a is a student who either has taken course b or needs course b to graduate.

• R1 ∩ R2 is the set of all ordered pairs (a, b), where a is a student who has taken course b and needs this course to graduate.

• R1 ⊕ R2 consists of all ordered pairs (a, b), where student a has taken course b but does not need it to graduate or needs course b to graduate but has not taken it.

• R1 - R2 is the set of ordered pairs (a, b), where a has taken course b but does not need it to graduate; that is, b is an elective course that a has taken.

• R2 - R1 is the set of all ordered pairs (a, b), where b is a course that a needs to graduate but has not taken.

 Previous Next