INTRODUCTION TO PROBABILITY by Dimitri P. Bertsekas and John N.
Tsitsiklis
CHAPTER 1: TEXTBOOK PROBLEMS
1) Romeo and Juliet have a date at a given time, and each will arrive at the meeting place with a delay
between 0 and 1 hour, with all pairs of delays being equally likely. The first to arrive will wait for 15
minutes and will leave if the other has not yet arrived. What is the probability that they will meet?
2) A fair 4-sided die is rolled twice and we assume that all sixteen possible outcomes are equally likely. Let
X and Y be the result of the 1st and the 2nd roll respectively. We wish to determine the conditional
probability 𝑃(𝐴|𝐵) , where 𝐴 = {max(𝑋, 𝑌) = 𝑚}, 𝐵 = {min(𝑋, 𝑌) = 2} and m takes each of the
values 1. 2. 3, 4.
3) A conservative design team, call it C. and an innovative design team, call it N, are asked to separately
design a new product within a month. From past experience we know that:
(a) The probability that team C is successful is 2/3.
(b) The probability that team N is successful is 1/2.
(c) The probability that at least one team is successful is 3/4.
Assuming that exactly one successful design is produced, what is the probability that it was designed by
team N?
4) If an aircraft is present in a certain area, a radar detects it and generates an alarm signal with
probability 0.99. If an aircraft is not present. the radar generates a (false) alarm, with probability 0.10.
We assume that an aircraft is present with probability 0.05. What is the probability of no aircraft
presence and a false alarm? What is the probability of aircraft presence and no detection? Given that
the radar generates an alarm what is the probability that an aircraft is present?
5) You enter a chess tournament where your probability of winning a game is 0.3 against half the players
(call them type 1). 0.4 against a quarter of the players (call them type 2), and 0.5 against the remaining
quarter of the players (call them type 3). You play a game against a randomly chosen opponent. What
is the probability of winning?
6) You roll a fair four-sided die. If the result is 1 or 2, you roll once more but otherwise, you stop. What is
the probability that the sum total of your rolls is at least 4?
7) Alice is taking a probability class and at the end of each week she can be either up-to-date or she may
have fallen behind. If she is up-to-date in a given week, the probability that she will be up-to-date (or
behind) in the next week is 0.8 (or 0.2, respectively). If she is behind in a given week, the probability
that she will be up-to-date (or behind) in the next week is 0.4 (or 0.6, respectively). Alice is (by default)
up-to-date when she starts the class. What is the probability that she is up-to-date after three weeks?
8) A test for a certain rare disease is assumed to be correct 95% of the time: if a person has the disease,
the test results are positive with probability 0.95, and if the person does not have the disease, the test
results are negative with probability 0.95. A random person drawn from a certain population has
probability 0.001 of having the disease. Given that the person just tested positive, what is the
probability of having the disease?
9) A computer network connects two nodes A and B through intermediate nodes C, D, E, F, as shown in
Fig. 1. For every pair of directly connected nodes. say 𝑖 and 𝑗, there is a given probability 𝑃𝑖𝑗 that the
link from 𝑖 to 𝑗 is up. We assume that link failures are independent of each other. What is the
probability that there is a path connecting A and B in which all links are up?
Fig. 1
10) An internet service provider has installed 𝑐 modems to serve the needs of a population of 𝑛 dialup
customers. It is estimated that at a given time, each customer will need a connection with probability
𝑝, independent of the others. What is the probability that there are more customers needing a
connection than there are modems?
11) Out of the students in a class, 60% are geniuses, 70% love chocolate, and 40% fall into both categories.
Determine the probability that a randomly selected student is neither a genius nor a chocolate lover.
12) A six-sided die is loaded in a way that each even face is twice as likely as each odd face. All even faces
are equally likely, as are all odd faces. Construct a probabilistic model for a single roll of this die and
find the probability that the outcome is less than 4.
13) A four-sided die is rolled repeatedly, until the first time (if ever) that an even number is obtained. What
is the sample space for this experiment?
14) You enter a special kind of chess tournament, in which you play one game with each of three
opponents, but you get to choose the order in which you play your opponents, knowing the probability
of a win against each. You win the tournament if you win two games in a row, and you want to
maximize the probability of winning. Show that it is optimal to play the weakest opponent second, and
that the order of playing the other two opponents does not matter.
15) We roll two fair 6-sided dice. Each one of the 36 possible outcomes is assumed to be equally likely.
(a) Find the probability that doubles are rolled.
(b) Given that the roll results in a sum of 4 or less, find the conditional probability that doubles are
rolled.
(c) Find the probability that at least one die roll is a 6.
(d) Given that the two dice land on different numbers, find the conditional probability that at
least one die roll is a 6.
16) A coin is tossed twice. Alice claims that the event of two heads is at least as likely if we know that the
first toss is a head than if we know that at least one of the tosses is a head. Is she right? Does it make a
difference if the coin is fair or unfair? How can we generalize Alice's reasoning?
17) We are given three coins: one has heads in both faces, the second has tails in both faces, and the third
has a head in one face and a tail in the other. We choose a coin at random, toss it, and the result is
heads. What is the probability that the opposite face is tails?
18) A batch of one hundred items is inspected by testing four randomly selected items. If one of the four is
defective, the batch is rejected. What is the probability that the batch is accepted if it contains five
defectives?
19) Alice searches for her term paper in her filing cabinet. which has several drawers. She knows that she
left her term paper in drawer 𝑗 with probability 𝑝𝑗 > 0. The drawers are so messy that even if she
correctly guesses that the term paper is in drawer 𝑖, the probability that she finds it is only 𝑑𝑖 Alice
searches in a particular drawer say drawer 𝑖 but the search is unsuccessful. Conditioned on this event,
𝑝 𝑝𝑖 (1−𝑑𝑖 )
show that the probability that her paper is in drawer 𝑗, is given by 1−𝑝𝑗 𝑑 𝑖𝑓 𝑗 ≠ 𝑖 & 𝑖𝑓 𝑗 = 𝑖
𝑖 𝑖 1−𝑝𝑖 𝑑𝑖
20) How an inferior player with a superior strategy can gain an advantage. Boris is about to play a two-
game chess match with an opponent, and wants to find the strategy that maximizes his winning
chances. Each game ends with either a win by one of the players, or a draw. If the score is tied at the
end of the two games, the match goes into sudden-death mode, and the players continue to play until
the first time one of them wins a game (and the match). Boris has two playing styles, timid and bold,
and he can choose one of the two at will in each game. no matter what style he chose in previous
games. With timid play. he draws with probability 𝑝𝑑 > 0, and he loses with probability 1 − 𝑝𝑑 . With
bold play. he wins with probability 𝑝𝑤 , and he loses with probability 1 − 𝑝𝑤 . Boris will always play bold
during sudden death, but may switch style between games 1 and 2.
(a) Find the probability that Boris wins the match for each of the following strategies:
(i) Play bold in both games 1 and 2.
(ii) Play timid in both games 1 and 2.
(iii) Play timid whenever he is ahead in the score. and play bold otherwise.
(b) Assume that 𝑝𝑤 < 1/2, so Boris is the worse player, regardless of the playing style he adopts. Show
that with the strategy in (iii) above, and depending on the values of 𝑝𝑤 and 𝑝𝑑 , Boris may have a
better than a 50-50 chance to win the match. How do you explain this advantage?
21) Two players take turns removing a ball from a jar that initially contains 𝑚 white and 𝑛 black balls. The
first player to remove a white ball wins. Develop a recursive formula that allows the convenient
computation of the probability that the starting player wins.
22) Each of 𝑘 jars contains 𝑚 white and 𝑛 black balls. A ball is randomly chosen from jar 1 and transferred
to jar 2, then a ball is randomly chosen from jar 2 and transferred to jar 3, etc. Finally, a ball is randomly
chosen from jar 𝑘. Show that the probability that the last ball is white is the same as the probability
𝑚
that the first ball is white, i.e., it is 𝑚+𝑛.
23) We have two jars, each initially containing an equal number of balls. We perform four successive ball
exchanges. In each exchange, we pick simultaneously and at random a ball from each jar and move it to
the other jar. What is the probability that at the end of the four exchanges all the balls will be in the jar
where they started?
24) The prisoner's dilemma. The release of two out of three prisoners has been announced. but their
identity is kept secret. One of the prisoners considers asking a friendly guard to tell him who is the
prisoner other than himself that will be released, but hesitates based on the following rationale: at the
prisoner's present state of knowledge, the probability of being released is 2/3, but after he knows the
answer, the probability of being released will become 1/2, since there will be two prisoners (including
himself) whose fate is unknown and exactly one of the two will be released. What is wrong with this
line of reasoning?
25) A two-envelopes puzzle. You are handed two envelopes. and you know that each contains a positive
integer dollar amount and that the two amounts are different. The values of these two amounts are
modeled as constants that are unknown. Without knowing what the amounts are, you select at
random one of the two envelopes, and after looking at the amount inside, you may switch envelopes if
you wish. A friend claims that the following strategy will increase above 1/2 your probability of ending
up with the envelope with the larger amount: toss a coin repeatedly. let X be equal to 1/2 plus the
number of tosses required to obtain heads for the first time, and switch if the amount in the envelope
you selected is less than the value of X. Is your friend correct?
26) The paradox of induction. Consider a statement whose truth is unknown. If we see many examples
that are compatible with it, we are tempted to view the statement as more probable. Such reasoning is
often referred to as inductive inference (in a philosophical, rather than mathematical sense). Consider
now the statement that "all cows are white." An equivalent statement is that "everything that is not
white is not a cow." We then observe several black crows. Our observations are clearly compatible with
the statement. but do they make the hypothesis "all cows are white" more likely?
To analyse such a situation, we consider a probabilistic model. Let us assume that there are two
possible states of the world, which we model as complementary events:
𝐴: all cows are white,
𝐴𝑐 : 50% of all cows are white.
Let 𝑝 be the prior probability 𝑃(𝐴) that all cows are white. We make an observation of a cow or a crow,
with probability 𝑞 and 1 − 𝑞, respectively, independent of whether event A occurs or not. Assume that
0 < 𝑝 < 1, 0 < 𝑞 < 1 and that all crows are black.
(a) Given the event B = {a black crow was observed}, what is 𝑃(𝐴|𝐵)?
(b) Given the event C = {a white cow was observed}, what is 𝑃(𝐴|𝐶)?
27) Alice and Bob have 2𝑛 + 1 coins, each coin with probability of heads equal to 1/2. Bob tosses 𝑛 + 1
coins, while Alice tosses the remaining 𝑛 coins. Assuming independent coin tosses, show that the
probability that after all coins have been tossed, Bob will have gotten more heads than Alice is 1/2.
28) A hunter has two hunting dogs. One day, on the trail of some animal, the hunter comes to a place
where the road diverges into two paths. He knows that each dog. independent of the other. will choose
the correct path with probability p. The hunter decides to let each dog choose a path, and if they agree,
take that one, and if they disagree, to randomly pick a path. Is his strategy better than just letting one
of the two dogs decide on a path?
29) Communication through a noisy channel. A source transmits a message (a string of symbols) through a
noisy communication channel. Each symbol is 0 or 1 with probability 𝑝 and 1 − 𝑝, respectively, and is
received incorrectly with probability 𝜀0 and 𝜀1 , respectively (see Fig. 2). Errors in different symbol
transmissions are independent.
Fig. 2
(a) What is the probability that the kth symbol is received correctly?
(b) What is the probability that the string of symbols 1011 is received correctly?
(c) In an effort to improve reliability, each symbol is transmitted three times and the received string is
decoded by majority rule. In other words, a 0 (or 1) is transmitted as 000 (or 111, respectively), and
it is decoded at the receiver as a 0 (or 1) if and only if the received three-symbol string contains at
least two 0s (or 1s, respectively). What is the probability that a 0 is correctly decoded?
(d) For what values of 𝜀0 is there an improvement in the probability of correct decoding of a 0 when
the scheme of part (c) is used?
(e) Suppose that the scheme of part (c) is used. What is the probability that a symbol was 0 given that
the received string is 101?
30) The king's sibling. The king has only one sibling. What is the probability that the sibling is male?
Assume that every birth results in a boy with probability 1/2, independent of other births. Be careful to
state any additional assumptions you have to make in order to arrive at an answer.
31) Using a biased coin to make an unbiased decision. Alice and Bob want to choose between the opera
and the movies by tossing a fair coin. Unfortunately. the only available coin is biased (though the bias is
not known exactly). How can they use the biased coin to make a decision so that either option (opera
or the movies) is equally likely to be chosen?
32) An electrical system consists of identical components, each of which is operational with probability 𝑝,
independent of other components. The components are connected in three subsystems, as shown in
Fig. 3. The system is operational if there is a path that starts at point A. ends at point B. and consists of
operational components. What is the probability of this happening?
Fig. 3.
A system of identical components that consists of the three subsystems
1. 2, and 3. The system is operational if there is a path that starts at
point A, ends at point B, and consists of operational components.
33) Reliability of a k-out-of-n system. A system consists of 𝑛 identical components, each of which is
operational with probability p. independent of other components. The system is operational if at least
𝑘 out of the 𝑛 components are operational. What is the probability that the system is operational?
34) A power utility can supply electricity to a city from 𝑛 different power plants. Power plant 𝑖 fails with
probability 𝑝𝑖 , independent of the others.
(a) Suppose that anyone plant can produce enough electricity to supply the entire city. What is the
probability that the city will experience a black-out?
(b) Suppose that two power plants are necessary to keep the city from a black-out. Find the probability
that the city will experience a black-out.
35) A cellular phone system services a population of 𝑛1 "voice users" (those who occasionally need a voice
connection) and 𝑛2 "data users" (those who occasionally need a data connection). We estimate that at
a given time, each user will need to be connected to the system with probability 𝑝1 (for voice users) or
𝑝2 (for data users), independent of other users. The data rate for a voice user is 𝑟1 bits/sec and for a
data user is 𝑟2 bits/sec. The cellular system has a total capacity of 𝑐 bits/sec. What is the probability
that more users want to use the system than the system can accommodate?
36) The problem of points. Telis and Wendy play a round of golf (18 holes) for a $10 stake, and their
probabilities of winning on anyone hole are 𝑝 and 1 − 𝑝, respectively, independent of their results in
other holes. At the end of 10 holes, with the score 4 to 6 in favour of Wendy, Telis receives an urgent
call and has to report back to work. They decide to split the stake in proportion to their probabilities of
winning had they completed the round, as follows. If 𝑝𝑇 and 𝑝𝑊 are the conditional probabilities that
Telis and Wendy, respectively, are ahead in the score after 18 holes given the 4-6 score after 10 holes,
𝑝𝑇 𝑝𝑊
then Telis should get a fraction 𝑝 +𝑝 of the stake, and Wendy should get the remaining 𝑝 +𝑝 . How
𝑇 𝑊 𝑇 𝑊
much money should Telis get?
Note: This is an example of the, so-called, problem of points, which played an important
historical role in the development of probability theory. The problem was posed by Chevalier de Mere
in the 17th century to Pascal, who introduced the idea that the stake of an interrupted game should be
divided in proportion to the players' conditional probabilities of winning given the state of the game at
the time of interruption. Pascal worked out some special cases and through a correspondence with
Fermat, stimulated much thinking and several probability-related investigations.
37) A particular class has had a history of low attendance. The annoyed professor decides that she will not
lecture unless at least 𝑘 of the 𝑛 students enrolled in the class are present. Each student will
independently show up with probability 𝑝𝑔 if the weather is good, and with probability 𝑝𝑏 if the
weather is bad. Given the probability of bad weather on a given day, obtain an expression for the
probability that the professor will teach her class on that day.
38) Consider a coin that comes up heads with probability 𝑝 and tails with probability 1 − 𝑝. Let 𝑞𝑛 be the
probability that after 𝑛 independent tosses, there have been an even number of heads. Derive a
(1+(1−2𝑝)𝑛 )
recursion that relates 𝑞𝑛 to 𝑞𝑛−1, and solve this recursion to establish the formula 𝑞𝑛 = 2
39) Consider a game show with an infinite pool of contestants, where at each round 𝑖, contestant 𝑖 obtains
a number by spinning a continuously calibrated wheel. The contestant with the smallest number thus
far survives. Successive wheel spins are independent and we assume that there are no ties. Let 𝑁 be
the round at which contestant 1 is eliminated. For any positive integer 𝑛, find 𝑃(𝑁 = 𝑛)
40) Gambler's ruin. A gambler makes a sequence of independent bets. In each bet, he wins $1 with
probability 𝑝, and loses $1 with probability1 − 𝑝. Initially, the gambler has $𝑘, and plays until he either
accumulates $𝑛 or has no money left. What is the probability that the gambler will end up with $𝑛?
41) Laplace's rule of succession. Consider 𝑚 + 1 boxes with the 𝑘th box containing 𝑘 red balls and 𝑚 − 𝑘
white balls, where 𝑘 ranges from 0 to 𝑚. We choose a box at random (all boxes are equally likely) and
then choose a ball at random from that box, 𝑛 successive times (the ball drawn is replaced each time,
and a new ball is selected independently). Suppose a red ball was drawn each of the 𝑛 times. What is
the probability that if we draw a ball one more time it will be red? Estimate this probability for large 𝑚.
