Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 7] PROBABILITY 145

(ii) Two points, (1, 2), (2, 1), have sum 3; hencef( 3 )=^29.

(iii) Three points, (1, 3), (2, 2), (1, 3), have sum 4; hencef( 4 )=^39.

(iv) Two points, (2, 3), (3, 2), have sum 5; hencef( 5 )=^29.

(v) One point (3, 3) has sum 6; hencef( 6 )=^19.

Thus the distributionfofXis:

x 23456

f(x) 1 / 92 / 93 / 92 / 91 / 9

The expected valueE(X)ofXis obtained by multiplying each value ofxby its probabilityf(x)and taking the sum.

Hence

E(X)= 2

(

1

9

)

+ 3

(

2

9

)

+ 4

(

3

9

)

+ 5

(

2

9

)

+ 6

(

1

9

)

= 4

(b) The random variableYonly assumes the values 1, 2, 3. We compute the distribution g ofY:

(i) Five points, (1, 1), (1, 2), (1, 3), (2, 1), (3, 1), have minimum 1; henceg( 1 )=^59.

(ii) Three points, (2, 2), (2, 3), (3, 2), have minimum 2; henceg( 2 )=^39.

(iii) One point (3, 3) has minimum 3; henceg( 3 )=^19.

Thus the following is the distribution g ofY:

y 123

g(y) 5 / 93 / 91 / 9

The expected valueE(Y)ofYis:

E(Y)= 1

(

5

9

)

+ 2

(

3

9

)

+ 3

(

1

9

)

=

12

9

≈ 1. 33

7.31.A linear array EMPLOYEE hasnelements. Suppose NAME appears randomly in the array, and there is

a linear search to find the locationKof NAME, that is, to findKsuch that EMPLOYEE[K]=NAME.

Letf (n)denote the number of comparisons in the linear search.

(a) Find the expected value off (n).

(b) Find the maximum value (worst case) off (n).

(a) LetXdenote the number of comparisons. Since NAME can appear in any position in the array with the same

probability of 1/n, we haveX= 1 , 2 , 3 ,...,n, each with probability 1/n. Hence

f (n)=E(X) = 1 ·^1 n+ 2 ·^1 n+ 3 ·^1 n+···+n·^1 n

= ( 1 + 2 +···+n)·^1 n=n(n+ 21 )·^1 n=n+ 21

(b) If NAME appears at the end of the array, thenf (n)=n.

MEAN,VARIANCE, STANDARD DEVIATION

7.32. Find the meanμ=E(X), varianceσ^2 =Var(X), and standard deviationσ=σxof each distribution:

(a) xi 2311(b) xi 1345

pi 1 / 31 / 21 / 6 pi 0.4 0.1 0.2 0.3

Use the formulas:

μ=E(X)=x 1 p 1 +x 2 p 2 +···+xmpm=xipi,σ^2 =Var (X)=E(X^2 )−μ^2

E(X^2 )=x^21 p 1 +x 22 p 2 +···+xm^2 pm=x^2 ipi,σ=σx=

√

Var (X)