Posted: November 26th, 2015

Discrete maths

Question 1: On the first page of your assignment, write your name and student number.

Question 2: You flip a fair coin three times. Define the four events (recall that zero is even)

A = “the coin comes up heads an odd number of times”,

B = “the coin comes up heads an even number of times”,

C = “the coin comes up tails an odd number of times”,

D = “the coin comes up tails an even number of times”.

• Determine Pr(A), Pr(B), Pr(C), Pr(D), Pr(A | C), and Pr(A | D). Show your work.

• Are there any two events in the sequence A, B, C, and D that are independent? Justify

your answer.

Question 3: In Section 5.4.1, we have seen the different cards that are part of a standard

deck of cards.

• You get a uniformly random hand of two cards from a standard deck of 52 cards.

Determine the probability that this hand contains an ace and a king. Show your work.

• You get a uniformly random hand of two cards from the 13 spades. Determine the

probability that this hand contains an ace and a king. Show your work.

Question 4: You roll a fair die twice. Define the events

A = “the sum of the results is even”

1

and

B = “the sum of the results is at least 10”.

Determine Pr(A | B). Show your work.

Question 5: In this question, we will use the product notation. In case you are not familiar

with this notation:

• For k = m,

Qm

i=k

xi denotes the product

xk · xk+1 · xk+2 · · · xm.

• If k > m, then Qm

i=k

xi

is an “empty” product, which we define to be equal to 1.

Let n = 1 be an integer, and for each i = 1, 2, . . . , n, let pi be a real number such that

0 < pi < 1. In this question, you will prove that

Xn

i=1

pi

Yn

j=i+1

(1 – pj ) = 1 –

Yn

i=1

(1 – pi). (1)

For example,

• for n = 1, (1) becomes

p1 = 1 – (1 – p1),

• for n = 2, (1) becomes

p1(1 – p2) + p2 = 1 – (1 – p1)(1 – p2),

• for n = 3, (1) becomes

p1(1 – p2)(1 – p3) + p2(1 – p3) + p3 = 1 – (1 – p1)(1 – p2)(1 – p3).

Assume we do an experiment consisting of n tasks T1, T2, . . . , Tn. Each task is either a

success or a failure, independently of the other tasks. For each i = 1, 2, . . . , n, let pi be the

probability that Ti

is a success. Define the event

A = “at least one task is a success”.

• Prove (1) by determining Pr(A) in two different ways.

Question 6: Let n = 2 be an integer and consider a uniformly random permutation

(a1, a2, . . . , an) of the set {1, 2, . . . , n}. Let k and ` be two integers with 1 = k < ` = n

and define the events

Ak = “ak is the largest element among a1, a2, . . . , ak”

2

and

A` = “a`

is the largest element among a1, a2, . . . , a`”.

Are these two events independent? Justify your answer.

Hint: Use the Product Rule to determine the number of permutations that define Ak, A`

,

and Ak n A`

.

Question 7: You know by now that Jennifer loves to drink India Pale Ale. Maybe you are

not aware that Connor Hillen (President of the Carleton Computer Science Society, 2015–

2016) prefers Black IPA. Jennifer and Connor decide to go to their favorite pub Chez Lindsay

et Simon. The beer menu shows that this pub has ten beers on tap:

• Phillips Cabin Fever Imperial Black IPA,

• Big Rig Black IPA,

• Leo’s Early Breakfast IPA,

• Goose Island IPA,

• Caboose IPA,

• and five other beers, neither of which is an IPA.

Each of the first five beers is an IPA, whereas each of the first two beers is a Black IPA.

Jennifer and Connor play a game, in which they alternate ordering beer: Connor starts,

after which it is Jennifer’s turn, after which it is Connor’s turn, after which it is Jennifer’s

turn, etc.

• When it is Connor’s turn, he orders two beers; each of these is chosen uniformly at

random from the ten beers (thus, these two beers may be equal).

• When it is Jennifer’s turn, she orders one of the ten beers, uniformly at random.

The game ends as soon as (i) Connor has ordered at least one Black IPA, in which case he

pays the bill, or (ii) Jennifer has ordered at least one IPA, in which case she pays the bill.

• Determine the probability that Connor pays the bill, assuming that all random choices

made are mutually independent. Justify your answer.

Question 8: Let n = 2 be an integer. We generate a random bitstring S = s1s2 · · · sn, by

setting, for each i = 1, 2, . . . , n, si = 1 with probability 1/i and, thus, si = 0 with probability

1 – 1/i. All random choices made when setting these bits are mutually independent.

For each i with 1 = i = n, define the events

Bi = “si = 1”

and

Ri = “the rightmost 1 in the bit string S is at position i”.

3

• Determine Pr (Ri).

The following algorithm Try To Find Right most One(S, n, m) takes as input the binary

string S = s1s2 · · · sn of length n and an integer m with 1 = m = n. As the name suggests,

this algorithm tries to find the position of the rightmost 1 in the string S.

Algorithm Try To Find Right most One(S, n, m):

for i = 1 to m

do if si = 1

then k = i

endif

endfor;

// k is the position of the rightmost 1 in the substring s1s2 · · · sm

// the next while-loop finds the position of the leftmost 1 in the substring

// sm+1sm+2 · · · sn, if this position exists

` = m + 1;

while ` = n and s` = 0

do ` = ` + 1

endwhile;

// if ` = n, then ` is the position of the leftmost 1 in the substring

// sm+1sm+2 · · · sn

if ` = n

then return `

else return k

endif

Define the event

Em = “there is exactly one 1 in the substring sm+1sm+2 · · · sn”.

• Prove that

Pr (Em) = m

n

1

m

+

1

m + 1

+ · · · +

1

n – 1

.

Define the event

A = “Try To Find Right most One(S, n, m) returns the position of the

rightmost 1 in the string S”.

• Prove that

Pr (A) = m

n

1 +

1

m

+

1

m + 1

+ · · · +

1

n – 1

.

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT

Place an order in 3 easy steps. Takes less than 5 mins.