Posted: November 26th, 2015

Discrete maths

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