\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\left\{#1\right\}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }

\begin{document}

\begin{center}
{\Large Notes for Tutorial 7} \\
6.042 - March 21 and March 31, 2003 \\
\bigskip
\end{center}

These notes cover three problems that are complicated, difficult, and
use most of the tools presented in class so far.  There is probably
much more here than you can cover, so pick and choose.

\begin{itemize}
\item Every man a king.
\item The stop game.
\item Never two kings.
\end{itemize}

(Next time, we can examples with female characters.  For now, let's
stick with the ``king'' terminology to avoid confusion.)

\section{Every Man a King}

Recall the definition of a {\em tournament}:

\begin{itemize}

\item There are $n$ vertices, $p_1, \ldots, p_n$, that represent players.

\item For every pair of distinct players $p_i$ and $p_j$, either there
is an edge from $p_i$ to $p_j$ (denoted $p_i \rightarrow p_j$) or
there is an edge from $p_j$ to $p_i$ (denoted $p_j \rightarrow p_i$)
but not both.

\item There are no self-loops, edges $p_i \rightarrow p_i$.

\end{itemize}

\noindent We also defined the notion of a {\em king} in a tournament.

\begin{itemize}

\item We say that $p_i$ {\em virtually defeats} $p_j$ (denoted $p_i
\leadsto p_j$) if player $i$ beats player $j$:

\[
p_i \rightarrow p_j
\]

or if player $i$ beats someone else who in turn beats player $j$:

\[
\exists p_k \ p_i \rightarrow p_k \rightarrow p_j
\]

\item Player $p_i$ is a {\em king} if he virtually defeats every other
player: $\forall j \neq i\ p_i \leadsto p_j$.

\end{itemize}

In lecture, we saw that every tournament has at least one king.  Can
{\em everyone} in an $n$-player tournament be a king?

\subsection{Small Cases}

A standard approach is to begin by considering small cases.  Have
students try to construct an $n$-player tournament where every player
is a king for $n = 2$ through $n = 6$ or so.  I think $n = 2$ is
impossible, $n = 3$ is possible, $n = 4$ is impossible, and $n = 5$ is
possible.  It is tempting to conjecture that every player can be a
king if and only if $n$ is odd!

\subsection{The Probabilistic Method}

There is another standard approach to a question of the form:

\bigskip
\centerline{``Does there exist a THING with a certain PROPERTY?''}
\bigskip

\noindent In our case, the THING is an $n$-player tournament and the
PROPERTY is that every player is a king.  The basic idea of the {\em
probabilistic method} is:

\begin{enumerate}

\item Construct a {\em random} THING.

\item Show $\pr{\text{THING has PROPERTY}} > 0$.

\item Conclude that a THING with the PROPERTY must exist!

\end{enumerate}

The sample space for the experiment in the first step is a set of
THINGS.  Therefore, if the probability that a random THING has the
PROPERTY is greater than zero, then there must exist at least one
THING in the sample space that has the PROPERTY.

\subsection{Solving Every Man a King}

\noindent The probabilistic works well for the Every Man a King
problem.  Define a {\em random tournament} to be tournament with edges
oriented uniformly and independently at random.  Here, ``uniformly''
means that each edge is as likely to point one way as the other.

An outline of the argument is provided below.  You could ask students
to fles out the details and provide hints as necessary.

\subsubsection{Compute $\pr{\overline{p_i \leadsto p_j}}$.}

We want to compute the probability that player $p_i$ does not
virtually defeat player $p_j$.  This happens only if all of the
following occur:

\begin{itemize}

\item We do not have $p_i \rightarrow p_j$.  This happens with
probablity $1/2$.

\item We do not have $p_i \rightarrow p_k \rightarrow p_j$, where
$p_k$ is one of the $n-2$ players other than $p_i$ or $p_j$.  For each
player $p_k$, there is no such path with probability $\frac{3}{4}$.

\end{itemize}

\noindent These events are all independent, because they involve
disjoint sets of edges and edges are oriented mutually independently.
Therefore, the probability that all these events occur is:

\beqn
\pr{\overline{p_i \leadsto p_j}}
	& = &	\frac{1}{2} \left(\frac{3}{4}\right)^{n-2}
\eeqn

\subsubsection{Upper bound the probability that player $p_i$ is not a king.}

We use Boole's inequality, a.k.a. the union bound, which says that for
events $E_1, \ldots, E_m$:

\beqn
\pr{\bigcup_{k=1}^m E_k} & \leq & \sum_{k=1}^m \pr{E_k}
\eeqn

\noindent Player $p_i$ is not a king if he does not virtually defeat
some player.

\beqn
\pr{p_i \text{ is not a king}}
	& = &	\pr{\bigcup_{j \neq i}
			\overline{p_i \leadsto p_j}} \\
	& \leq & \sum_{j \neq i}
		\pr{\overline{p_i \leadsto p_j}} \\
	& = &	(n-1) \cdot \frac{1}{2} \left(\frac{3}{4}\right)^{n-2}
\eeqn

The first step uses the definition of a king.  The second uses the
union bound, and the third uses the previous result.

\subsubsection{Upper bound the probability someone is not a king.}

We use the union bound again.

\beqn
\pr{\text{some player not a king}}
	& = &	\pr{\bigcup_{i=1}^n \text{$p_i$ is not a king}} \\
	& \leq & \sum_{i=1}^n \pr{\text{$p_i$ is not a king}} \\
	& = &	n \cdot (n-1) \cdot \frac{1}{2} \left(\frac{3}{4}\right)^{n-2}
\eeqn

The first step is a rephrasing of the event.  The second uses the
union bound, and the third uses the previous result.

\subsubsection{Show that every man is a king with positive probability.}

Rewriting the previous bound, we have:

\beqn
\pr{\text{every player is a king}}
	& \geq &	1 - \frac{n(n-1)}{2 \left(\frac{4}{3}\right)^{n-2}}
\eeqn

In general, {\em an exponential grows much faster than a polynomial}.
Therefore, the denominator on the right gets much bigger than the
numerator when $n$ is large.  Therefore, as $n$ grows large, the
fraction becomes very small and so the overall probability is greater
than zero.  Therefore, for all sufficiently large $n$, there exists a
tournament in which every man is a king!

With a calculator, you can check that such a tournament exists for all
$n \geq 21$.  In fact, when $n$ is is 50, there's a 99.9\% chance that
every player in a random tournament is a king!

\section{The Stop Game}

Here is how to play a card game called {\em Stop}.

\begin{itemize}

\item I shuffle a deck of cards.  

\item I deal cards off the top of the deck, face up, one at a time.

\item At some time before the last card is dealt, you must say,
``Stop!''.

\item I deal one more card.  If it is black, you win; if it is red,
you lose.

\end{itemize}

\noindent What is the best strategy for this game?  Let the students
play.  Choose a player who did particularly well to explain his or her
``winning strategy''.

Intuitively, you should wait until there are more black cards than red
remaining.  If you then say stop, your odds of winning are greater
than $\frac{1}{2}$.  But when {\em exactly} should you say stop?
Smart mathematicians have spent hours on this problem--- no kidding!
Two solutions are presented here, one using induction and one using
bijection.

\subsection{Solution by Induction}

We can characterize a player's strategy by giving the probability that
she says stop in every possible situation.  Define:

\beqn
S_{n,b} & = & \pr{\text{player says stop with $n$ cards left,
		$b$ of them black}}
\eeqn

\noindent Thus, a player's strategy is just an assignment of values to
the stop variables $S_{n,b}$.  According to the rules, we must have
$S_{1,0} = S_{1,1} = 1$; that is, if there is only one card left, the
player has to say stop.

Now let's compute the probability that a player wins using a
particular strategy.  Define:

\beqn
W_{n,b} & = & \pr{\text{player wins if $n$ cards are left, $b$ of them black}}
\eeqn

\noindent We know the probability of winning for some special cases:

\beqn
W_{n,0} & = & 0 \\
W_{n,n} & = & 1
\eeqn

\noindent If there are no black cards left, the player can't win.  If
only black cards are left, she can't lose.  Ask the students to
express $W_{n,b}$ in terms of other stop and win variables.

\beqn
W_{n,b} & = &
	S_{n,b}	\cdot \frac{b}{n} +
	(1 - S_{n,b}) \left(\frac{b}{n} \cdot W_{n-1,b-1} +
		\frac{n - b}{n} \cdot W_{n-1,b} \right) \quad (0 < b < n)
\eeqn

\noindent This equation says that if you stop, your winning
probability is just the fraction of the remaining cards that are
black.  If you don't stop, then there are two cases.  If the next card
is black, then only $n-1$ cards remain, $b-1$ of them black, and so
you win with probability $W_{n-1,b-1}$.  If the next card is red, then
only $n-1$ cards remain, $b$ of them black, and so you win with
probability $W_{n-1,b}$.

\subsection{Small Cases}

Using this recurrence, we can compute the probability that a player
wins Stop with a given strategy; it is just $W_{52,26}$!  But how
large is $W_{52,26}$ if we use the very best strategy?

Ask students to compute $W_{2,1}$ and $W_{3,2}$ using the recurrence.
Tell them to leave their answers in terms of the stop probabilities
$S_{n,b}$.  In fact, these cancel out.

\beqn
W_{2,1} & = &	S_{2,1}	\cdot \frac{1}{2} +
		(1 - S_{2,1}) \left(\frac{1}{2} \cdot W_{1,0} +
		\frac{1}{2} \cdot W_{1,1} \right) \\
	& = &	S_{2,1}	\cdot \frac{1}{2} +
		(1 - S_{2,1}) \left(\frac{1}{2} \cdot 0 +
		\frac{1}{2} \cdot 1 \right) \\
	& = &	\frac{1}{2} \\
W_{3,2} & = &	S_{3,2}	\cdot \frac{2}{3} +
		(1 - S_{3,2}) \left(\frac{2}{3} \cdot W_{2,1} +
		\frac{1}{3} \cdot W_{2,2} \right) \\
	& = &	S_{3,2}	\cdot \frac{2}{3} +
		(1 - S_{3,2}) \left(\frac{2}{3} \cdot \frac{1}{2} +
		\frac{1}{3} \cdot 1 \right) \\
	& = &	\frac{2}{3}
\eeqn

Apparently, the player's probability of winning {\em does not depend
on her strategy!}  In fact, her probability of winning seems to be $b
/ n$, the fraction of black cards in the deck at the start.  Ask
students to prove this by induction.  Make sure that their induction
hypothesis is suitable!

\begin{theorem}
If Stop is played with a deck of $n \geq 1$ cards, of which $b$
areblack, then the player wins with probability $b /n$, regardless of
her strategy.
\end{theorem}

\begin{proof} The proof is by induction on $n$.  Let $P(n)$ be the
proposition that for all strategies and all $b$ such that $0 \leq b
\leq n$, the player wins with probability $b / n$.

First, we show that $P(1)$ is true.  In this case, only one card
remains, and so the player must say stop immediately.  Her probability
of winning is then $b/n$.  If $b = 0$, she always loses; if $b = 1$,
she always wins.

Next, we assume $P(n-1)$ in order to prove $P(n)$.  If there are no
black cards left, then the player wins with probability $b / n = 0 / n
= 0$.  If only black cards are left, then the player wins with
probability $b / n = n / n = 1$.  Otherwise, the player wins with
probability:

\beqn
W_{n,b} & = &	S_{n,b}	\cdot \frac{b}{n} +
		(1 - S_{n,b}) \left(\frac{b}{n} \cdot W_{n-1,b-1} +
		\frac{n - b}{n} \cdot W_{n-1,b} \right) \\
	& = &	S_{n,b}	\cdot \frac{b}{n} +
		(1 - S_{n,b}) \left(\frac{b}{n} \cdot \frac{b-1}{n-1} +
		\frac{n - b}{n} \cdot \frac{b}{n-1} \right) \\
	& = &	S_{n,b}	\cdot \frac{b}{n} +
		(1 - S_{n,b}) \cdot \frac{b}{n} \\
	& = &	\frac{b}{n}
\eeqn

\noindent The first equation is our recurrence.  The second step uses
the induction hypothesis, $P(n-1)$.  The remaining two steps are
simplifications.

Thus, the claim holds by the principle of induction.
\end{proof}

\subsection{A Bijection Approach}

There is an another way to see that the player's strategy is
irrelevant.

Suppose that we change the last rule slightly: now I deal the last
card from the bottom of the deck.  Say that the original rules define
``game 1'' and the new rules define ``game 2''.  Are these games
different?  Could you, as a player, determine whether you were playing
game 1 or game 2 if you didn't see the origin of the last card?  How
can we rigorously prove that these games are equivalent?  We can use a
bijection!

\begin{lemma}
For every card $t$ and sequence of cards $t_1, \ldots, t_k$, the
probability that the next card dealt is $t$, given that cards $t_1,
\ldots, t_k$ have already been dealt, is the same in games 1 and 2.
\end{lemma}

\begin{proof}
For concreteness, suppose that $t$ is the queen of hearts.  Our
argument applies equally well to every other card.

Until the player says stop, the rules of the two games are identical.
Therefore, the probability of dealing the queen of hearts, given that
$t_1, \ldots, t_k$ have already been dealt, is the same in both games.

When the player says stop, the games diverge.  In game 1, the next
card comes from the top of the deck.  In game 2, the next card comes
from the bottom.  If the queen of hearts has already been dealt, then
it is the next card with probability zero in both games.  Otherwise,
if there is only one card left, then it is the queen of hearts with
probability 1 in both games.

So suppose there is a set $S$ of at least two cards remaining, one of
which is the queen of hearts.  Assuming the deck is thoroughly
shuffled, so that every permutation of the remaining cards is equally
likely.  Then the permutations of $S$ form a uniform sample space.

Let $T$ be the event that the queen of hearts is on top, and let $B$
be the event that the queen is on the bottom.  These events are
disjoint, because the queen can't be in both places at once:

\bigskip
\centerline{\resizebox{!}{3in}{\includegraphics{tut7-queen.eps}}}
\bigskip

We must show that the probability of $T$ is equal to the probability
of $B$.  That is, the probability of dealing the queen in game 1 is
equal to the probability of dealing the queen in game 2.  We can do
this by establishing a {\em bijection} between events $T$ and $B$.
This will prove that $T$ and $B$ contain an equal number of outcomes.
Since all outcomes (permutations of the remaining cards) are equally
likely, this proves that $\pr{T} = \pr{B}$.  (Ask students to suggest
a bijection; they might give the one below or suggest reversing the
order of the remaining cards.)

Let $f$ be a function that swaps the top and bottom cards.  If $s_1,
\ldots, s_n$ is the sequence of remaining cards, then $f$ is defined as
follows:

\beqn
f(s_1 s_2 \ldots s_{n-1} s_n) & = & s_n s_2 \ldots s_{n-2} s_1
\eeqn

\noindent If the queen was on top in the permutation on the left, then
the queen is on the bottom in the permutation on the right.  So this
is a function from $T$ to $B$.  Futhermore, this is a bijection,
because the function is invertible; in fact, $f$ is it's own inverse.
\end{proof}

We've shown that games 1 and 2 are indistinguishable to the player;
given the cards already dealt, each card is as likely to be dealt next
in game 1 as in game 2.  Therefore, in particular, every strategy the
player uses in the first game works equally well in the second game.

But the second game is easy to analyze!  The player wins if an only if
the bottom card was red after the initial shuffle!  Therefore, the
player wins the second game with probability $1/2$ regardless of her
strategy.  By our lemma, the same is true of the first game.

\section{Never Two Kings}

Challenge students to prove the following claim:

\begin{claim}
A tournament can not contain {\em exactly} two kings.
\end{claim}

First, get them to suggest general approaches.  (Here we show that if
there are two kings, then there must be a third; perhaps some other
approach is possible.)  As a hint, suggest that they divide all other
players into four groups: those that lost to both $k_1$ and $k_2$,
those that beat $k_1$ and lost to $k_2$, etc.  As another hint, remind
them that they can use the King Chicken Theorem from lecture, which
says that every tournament has a king.

\begin{proof}
Suppose that a tournament contains two kings.  Let $k_1$ be the winner
of the match between them, and let $k_2$ be the loser.  We show that
the tournament must contain a third king, $k_3$, as well.  Therefore,
no tournament contains exactly two kings.

Divide the players (excluding $k_1$ and $k_2$) into four groups:

\beqn
D_{1,2} & = & \text{players that defeated both $k_1$ and $k_2$} \\
D_{1} & = & \text{players that defeated only $k_1$} \\
D_{2} & = & \text{players that defeated only $k_2$} \\
D_{-} & = & \text{players that defeated neither king}
\eeqn

\noindent These definitions are illustrated below.  An arrow between
two groups in the diagram below indicates that {\em all} edges
connecting those groups are oriented in the direction of the arrow.

\bigskip
\centerline{\resizebox{!}{2.5in}{\includegraphics{tut7-2kings.eps}}}
\bigskip

First, suppose that $D_{1,2}$ is nonempty.  Then let $k_3$ be the king
of the tournament among the players in $D_{1,2}$.  This means that
$k_3$ virtually defeats all the players in $D_{1,2}$.  Since $k_3$
defeats $k_1$, he also virtually defeats all players in $D_2$ and
$D_{-}$.  Since $k_3$ defeats $k_2$, he also virtually defeats all
players in $D_1$.  Therefore, $k_3$ is a king.

Otherwise, suppose that $D_{1,2}$ is empty.  Since $k_2$ virtually
defeats $k_1$, there must be a player $x$ such that $k_2 \rightarrow x
\rightarrow k_1$.  This player $x$ must be in $D_1$, and so the set
$D_1$ is nonempty.  Let $k_3$ be the king of the tournament among the
players in $D_1$.  Then $k_3$ virtually defeats all players in $D_1$.
Player $k_3$ also virtually defeats both kings, since $k_3 \rightarrow
k_1 \rightarrow k_2$.  Since $k_3$ defeats $k_1$, he virtually defeats
all players in $D_2$ and $D_{-}$.  Since the set $D_{1,2}$ is empty,
$k_3$ is a king.

Therefore, in either case, the tournament contains a third king.
\end{proof}
\end{document}
