Mathematics for Computer Science

Chapter 17 Random Variables608

because Team 1 has a strategy that guarantees that it wins at least 3/7 of the time,
no matter how Team 2 plays. Describe such a strategy for Team 1 and explain why
it works.

Problem 17.6.
Suppose you have a biased coin that has probabilitypof flipping heads. LetJbe
the number of heads innindependent coin flips. SoJhas the general binomial
distribution:

PDFJ.k/D

n

k

!

pkqnk

whereqWWD 1 p.

(a)Show that

PDFJ.k1/ <PDFJ.k/ fork < npCp;

PDFJ.k1/ >PDFJ.k/ fork > npCp:

(b)Conclude that the maximum value of PDFJis asymptotically equal to

1

p

2npq

:

Hint:For the asymptotic estimate, it’s ok to assume thatnpis an integer, so by
part (a), the maximum value is PDFJ.np/. Use Stirling’s formula (14.30).

Homework Problems

Problem 17.7.
A drunken sailor wanders along main street, which conveniently consists of the
points along thexaxis with integral coordinates. In each step, the sailor moves
one unit left or right along thexaxis. A particularpathtaken by the sailor can be
described by a sequence of “left” and “right” steps. For example,hleft,left,righti
describes the walk that goes left twice then goes right.
We model this scenario with a random walk graph whose vertices are the integers
and with edges going in each direction between consecutive integers. All edges are
labelled1=2.
The sailor begins his random walk at the origin. This is described by an initial
distribution which labels the origin with probability 1 and all other vertices with
probability 0. After one step, the sailor is equally likely to be at location 1 or 1 ,
so the distribution after one step gives label 1/2 to the vertices 1 and 1 and labels
all other vertices with probability 0.