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.

What if the games end in a draw or stalemate?

so A has to win only once to retain his championship?

that's not fair

Cool explanation. By the way – you are adorable saying: "I'm just testing you guys" š

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?

would have been nice if you explained the rules of the game. How am i supposed to know what round 2 is…???

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

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!

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

Very strange playoff rules