A Chess Tournament Problem

A Chess Tournament Problem


Hi. Welcome back. Today, we’re going to do a fun
problem called the chess tournament problem. Now, it’s a very long problem,
so I just want to jump straight in. Essentially, the problem
statement describes a very special chess tournament, which
involves players named Al, Bo, and Chi. Now Al is the current reigning
championship, and Bo and Chi are this year’s contenders, and,
of course, they’re vying with each other to beat out Al
and become the new champion. And so essentially,
the tournament is divided into two rounds– a first round, during which Bo
and Chi play against each other, and then a second
round, during which the surviving contender from the
first round plays against Al. And the problem statement also
gives you a bunch of information like what’s the
probability that Bo beats Chi in a particular game,
et cetera. So without further ado, let’s
get started on part a. In part a, the first thing we’re
asked to compute is the probability that a second
round is required. Now, to save myself some
writing, I used the notation R2 to denote that event. So we are interested in
probability of R2. Now, I claim that this problem
is very sequential in nature so I would like to draw a tree
to describe what’s happening. So in the first part of the
tournament, when Bo and Chi play their first game, exactly
one of two things can happen– either Bo can win
or Chi can win. And we’re told by the problem
statement that Bo wins with the probability of 0.6 and,
therefore, Chi must win with the probability of 0.4, right? Because these two possibilities
must sum to 1, because either this must
happen or this happen. Now, let’s imagine that the
first game has been played and that Bo won. Well, during the second game,
there’s still two options for the outcome– Bo could win the second
game or Chi could win the second game. And because the problem
statement says that in every scenario Bo always wins
against Chi with the probability of 0.6, we can go
ahead and put a 0.6 along this branch as well. Similarly, 0.4 here. And similar logic, you’ve got
a tree that looks like this. And for those of you who haven’t
seen trees before, it’s just a structure that looks
something like this. And it helps us do better
accounting. It helps us keep straight in our
head what are the various outcomes, so that we
don’t get confused. And so very quickly here, you
can see that there’s four possible outcomes. So each node in this tree
corresponds to an outcome. And the leaves are those nodes
at the furthest stage. And it’s convention to draw
the probability of a particular– so for instance, the probability
that Bo wins the first game– it’s just
convention to draw that probability over the
corresponding branch. And the reason why such diagrams
are so useful is because to compute the
probability of a particular outcome, if you’ve designed your
tree correctly, all you have to do is multiply the
probabilities along the branches that get into
that outcome. So let’s see that in action. When is a second
round required? Well, a second round is
required here, right? Because in this case, Bo would
be the surviving challenger and he’d play the next
round against Al. It’s also required here. But of course, it’s not required
here or here, because no second round is played. And so these two outcomes
comprise the event R2. And now, to get the probability
of this outcome, you multiply along
the branches. So 0.6 times 0.6
give you 0.36. And 0.4 times 0.4
gives you 0.16. And we’re almost done. We know that these two events
are disjoint, because if Bo won the first two games, then,
certainly, Chi could’ve won the first two games. And so you can just sum the
probabilities to get the probability of the reunion. So the probability of R2 is
equal to the probability that Bo won the first two games or
Chi won the first two games. And that’s equal to 0.36
plus 0.16, which is equal to a 0.52. OK, now the second part
of part a asks for the probability that Bo wins
the first round. And this is first round. This is a very straightforward
one. So Bo wins the first round, that
correspondence only to this particular outcome. And we already know the
probability associated with that outcome is equal
to the 0.36. So we’re done with that one. And now the last part is sort
of an interesting one. It asks for the probability
that Al retains his championship this year. So I’m going to just call
that A for short. A is the event that Al retains
his championship this year. And for that we’re going to need
a larger tree, because Al has a lot of activity in the
second round, and so far our tree only describes what happens
in the first round. Now, to save time, I’ve actually
drawn the rest of the tree over there up
in the corner. So let’s get rid of
this one and let’s look at the full tree. So let’s see when does Al
retain his championship? Well, Al certainly retains his
championship here, right? Because no second round
is required. Similarly, here. Al retains his championship
here, because the second round was required, but Al beat Bo. And similarly, here Bo didn’t
win both games in the second round against Al, so Al wins. Here, Bo is the new
championship. So we don’t want to
include about one. And sort of by symmetry,
we also get this one and this one. So by my argument before, we
know that the outcomes that comprise our event of interest
are this one, this one, this one, this one, this
one, and this one. So we could multiply the
probabilities along each branch and sum them, because
they’re disjoint, to get the total probability. But we’re not going
to do that because that’s a lot of algebra. Instead, we’re going
to look at the complement of the event. So we’re going to notice,
there’s only two branches on which Al does not retain his
current championship. So P of A is, of course, equal
to 1 minus P of A. And we’re going to get P of
A by inspection. I’m sorry, so P of
A compliment. I’m just testing you, guys. So P of A compliment corresponds
to here and to here, because those are the
outcomes where Al didn’t win. And so again, you multiply along
the branches to get the probabilities. So you get 0.6 squared times 0.5
squared plus 0.4 squared times 0.3 squared. And if you do all the algebra,
you should get around 0.8956. So we’re cruising through
this problem. Let’s go to part b. Part b is a little bit less
straightforward than part a, because it starts asking you for
conditional probabilities, as opposed to a priori
probabilities. So in the first part– and again, I’m going to continue
my notation with R2– we want the probability that
Bo is the surviving challenger– so I’m just going to use
B to denote that– given R2. Now, by definition, you should
remember from lecture that this is equal to probability
of B and R2 divided by the probability of R2. And of course, we’ve already
computed this value right up here with part a. We know it’s 2.5. So we don’t have to do
any more work there. We only have to look
at the numerator. So we need to go and figure out
what nodes in that tree correspond to the event
B intersect R2. So let’s use a new color. Let’s see, Bo is the surviving
challenger here only, right? And R2 is automatically
satisfied, right? Because a second round is
required there and there, not on those two. But here Chi is the surviving
challenger, not Bo, so we’re really only interested
in that node. And you multiply along the
branches to get the probabilities. So we have 0.36 over
0.52, which is approximately equal to 0.6923. OK, now, the next part wants
the conditional probability that AL retains his
championship, conditioned, again, on R2. So we already have A being
the event Al retains his championship. So we want the probability
of A, given R2. And let’s just apply the
direct definition of conditional probability again. You get P of A and R2 divided
by a probability of R2. Of course, we have the
probability of R2 already, so we just need to find the node
in the tree that corresponds to A and R2. So where is R2? R2 is going to correspond to
every node to the right that is not one of these two. So a second round is required
here, here, here, here, here, and here. Now, where does Al retain
his championship? So Al retains his championship
here. He retains his championship
here. He retains his championship here
and here, but no second round is required, so these
guys don’t belong in the intersection. But this does, and this does. So we can again multiply the
probabilities along the branches and then some them. So let’s see, we get– this marker’s not working very
well, so I’m going to switch back to the pink– so you get 0.6 squared
times 0.5. That gets rid of this one. And then we want 0.6 squared
times 0.5 squared. That gets rid of that one. And then plus– let’s see– 0.4 squared times 0.7, which
takes care of this one. And then lastly, 0.4 squared
times 0.3 times 0.7. And that is a long expression. But it happens to
be about 0.7992. OK, so we are done with
part b and we can move along to part c. And I am, since we’re running
out of room, I’m actually just going to erase this. And hopefully you guys
have had a chance to copy it down by now. If not, you can always pause
the video and go back. So let’s see, part c asks us
given that the second round is required and that it comprised
of one game only. So let’s denote I. So let’s I
be the event that the second round was one game only. So essentially, in math
conditioned on R2 and I, what is the probability that it was
Bo who won the first round? So let’s let B be the event that
Bo won the first round. OK, so again translating the
English to math, we just want the probability of B given R2
and I. Now, I am once again going to use the definition of
conditional probability. You might be concerned that we
haven’t defined explicitly yet the definition of conditional
probability, when what lies behind the conditioning bar is
not a single event, but it’s rather an intersection
of an event. And so my claim to you is that
it doesn’t matter and that the same exact definition applies. But we’ll go through
it slowly. So R2 is an event, I is an
event, and we know that the intersection of two events
is itself an event. So I’m going to make up a new
letter, and I’m going to call this event W. So just using
the new notation, this is equal to probability
of B, given W. Now, this is the normal
definition that we know. We know that this is probability
of B intersect W over probability of W. And then
we just resubstitute what the definition of W was. And so if you do that over here,
you get probability of B and R2 and I divided by
probability of R2 and I. So hopefully, jumping from here
ahead to here, you see that the definitions act
exactly the same way. But these are two very short
intermediate steps that should help you convince yourself
that the same definition still works. So let’s start with the
denominator, because the denominator looks a
little bit easier. Where is R2 and I in our tree? Well, let’s see. Here, a second round was
required, but it comprised two games. Same with this one. Here, a second round was
required and it was comprised only of one game. So this is good. This is one of the outcomes
that we’re looking for. Here, no second round
was required. So this doesn’t qualify. Same with this one. Here, a second round was
required, and there was only one game, so that’s good. And then these don’t qualify
for the same reasons as we set up there. So we just have to multiply the probabilities along those branches. And we see that it’s 0.4 squared
times 0.7 plus 0.6 squared times 0.5. OK, we’re almost done. We just need to look at the
intersection of R2 and I. So R2 and I are the ones we’ve
already circled. But now, we want to add one more
constraint, which is that Bo had to have won
the first round. And so we see here that Chi won
the first round, if we’re looking at this outcome. And so he’s no good. Let’s use a different color. Let’s see, maybe this one. But here Bo did win
the first round. So we’re going to get 0.6
squared times 0.5. And I got that, of course,
just by multiplying the probabilities along the
right branches. And this, if you’re curious,
comes out to be about 0.6164. OK, so I know that was a lengthy
problem, but you should feel really comfortable
now doing sort of basic probability manipulations. One thing that this problem
emphasized a lot was your ability to compute conditional
probabilities. So you saw me apply the
definition of conditional probability twice in part b. And then you saw me apply the
definition again in part c in a sort of slightly
modified way. So that’s one thing that
you should have gotten out of this problem. And then another thing is that
hopefully, you noticed that by using a tree diagram, we made
the problem much easier. We almost didn’t even have
to think about computing probabilities anymore. We reduced the problem to just
saying, OK, what are the outcomes that comprise our
event of interest? And then once you select
those, to compute their probability you multiply the probabilities along the branches. You have the right to just add
those together, because if you draw your tree correctly, all
of these guys should be disjoint from one another. So you have to be careful, of
course, to set up your tree appropriately. But once you do set up your tree
appropriately, your life is much simpler. So that’s it for today. And we’ll see you next time.

9 thoughts on “A Chess Tournament Problem

  1. Part C is unintuitive to me. If we know that Al beat someone in the first game he played, then intuitively it seems more likely that it would be Ci as opposed to Bo, but the result from C claims precisely the opposite. Can someone explain where my reasoning has broken down?

  2. If you check at 12:29 P(A|R_2) + P(B|R_2) > 1
    I think correct answer is
    P(B|R_2) = 0.1731; P(C|R_2) = 0.0277; P(A|R_2) = 0.7992 ; P(A|R_2)+P(B|R_2)+P(C|R_2) =1

  3. There is a subtle mistake, each node of the tree does not correspond to an outcome, we reserve the word outcome for the overall outcome at the end of the overall experiment. As said By Professor John Tsitsiklis in Lecture 1. So each node is a result not an outcome please Clarify!

  4. what i don't get :
    1st point : if B beats C once then C beats B, then why does A retain his champion title ? Shouldn't B and C just match one last time before getting to the next round ? Computed probabilities would be different for sure
    2nd point : If A wins only one game, does the assignment say he keeps his title ? for B or C needs to beat him twice doesn't seem to be very fair in terms of rules

Leave a Reply

Your email address will not be published. Required fields are marked *