Playing the Game

Loading...

Del curso dictado por University of California San Diego

Combinatorics and Probability

227 calificaciones

University of California San Diego

Combinatorics and Probability

227 calificaciones

Curso 2 de 5 en SpecializationIntroduction to Discrete Mathematics for Computer Science

Counting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following. If we need to count something, can we do anything better than just counting all objects one by one? Do we need to create a list of all phone numbers to ensure that there are enough phone numbers for everyone? Is there a way to tell that our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics. In this course we discuss most standard combinatorial settings that can help to answer questions of this type. We will especially concentrate on developing the ability to distinguish these settings in real life and algorithmic problems. This will help the learner to actually implement new knowledge. Apart from that we will discuss recursive technique for counting that is important for algorithmic implementations. One of the main `consumers’ of Combinatorics is Probability Theory. This area is connected with numerous sides of life, on one hand being an important concept in everyday life and on the other hand being an indispensable tool in such modern and important fields as Statistics and Machine Learning. In this course we will concentrate on providing the working knowledge of basics of probability and a good intuition in this area. The practice shows that such an intuition is not easy to develop. In the end of the course we will create a program that successfully plays a tricky and very counterintuitive dice game. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

De la lección

Project: Dice Games

In this module, we will apply accumulated knowledge to create a project solving a certain dice game. The game is very simple: two players pick a dice each from a given pool of dices with various numbers on their sides. Then each player throws his dice and the one with the greater number on his dice wins. The game looks very simple and it seems that it is very easy to play this game optimally once we know our pool of dices. Yet it turns out that this intuition is overwhelmingly wrong: the game turns out to be very counterintuitive. In this module we will discuss the game in detail and create a program that finds an optimal strategy to play the game on a given pool of dices.

Playing the Game8:22

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Vladimir Podolskii
Associate Professor
Computer Science Department

So, once we come closer to the shady person,

we can see that he has just three dices, and here we are.

So, the first dice has numbers 1, 1,

6, 6, and 8,

8 on its sides.

The second dice has numbers 2,

2, 4, 4, 9, 9.

And the third dice has numbers 3,

3, 5, 5, 7, 7.

So, these are just three dices.

Everything is very simple.

Okay. So, which of the dices should we be picked, if we play this game?

Now, we are educated. We know something now.

We know that we should just compare dices between each other,

compute probabilities, and see which of the dices is the best,

so let's just do it.

Let's start. For example,

we have dice one and dice two.

So, what should we do?

We should consider all possible outcomes and

count winning outcomes for both of the dices for the first dice and for the second one.

And we will see which one is better.

Okay. So, here is the list of all outcomes. There are six outcomes.

So, the first dice and rows of this table correspond to outcomes. So, the first dice.

And there are six outcomes of the second dice,

and columns correspond to outcomes of the second dice.

So, the dice that has larger number wins.

So, we can see from this picture that,

okay, so here are winning outcomes for both dices.

And we can count that dice one has only 16 winning outcomes,

and dice two has 20 winning outcomes.

So, dice two with the probability of five over nine,

which is greater than one half.

If you have to choose, if you are playing,

if dice one against dice two,

we will win in approximately five out of nine games.

And if we play this game long enough,

we will start winning,

we will start gaining some profit.

So, dice two turns out to be better than dice one.

And so, if we play a game with dice two against dice one,

on the long run we will start to win.

Okay. So, now, let's compare dice two and dice three,

and we will find the best dice.

Dice two is better than dice one.

If we compare to dice three,

we will know which one is the best.

Okay. Again, we have to consider all outcomes and

we have to count winning outcomes for each of both dices.

Here is the table again.

So, now, rows correspond to outcomes of dice two,

columns correspond to outcomes of dice three.

And, again, the dice that has larger number wins in this specific outcome.

So, here are winning outcomes for dice three and winning outcomes for dice two.

So, dice two now has only 16 winning outcomes,

and dice three has 20 winning outcomes.

Again, as in the previous case, something similar happens.

Dice three wins the probability of five over nine.

So, dice three is better that dice two.

And overall we have the following.

Dice two is better than dice one,

dice three is better than dice two.

And so, clearly, dice three

is better than dice one since dice three is better than dice two,

dice two is better than dice one, and so dice three should be much better than dice two.

And we are done. We should pick dice three to play this game. Or are we?

Is everything correct? Recall that we are playing with the shady person,

so we should be careful here.

So, let's just check just to be sure.

Okay. Let's compare dice three and dice one.

Again, we have to consider all outcomes.

Again, we have to count winning outcomes for each of the dices.

And here is the table now,

rows correspond to outcomes of dice three,

columns correspond to outcomes of dice one.

And the dice that has larger number wins in a certain outcome.

So, here we can see that,

here are winning outcomes for dice one,

and here are winning outcomes for dice three.

And we can see that there are only 16 winning outcomes for dice three,

and there are 20 winning outcomes for dice one.

And so, dice one wins the probability of five over nine, which is greater than one half.

So, let's summarize what we have.

Dice two is better than dice one,

dice three is better than dice two.

We have showed both of this.

But it turns out that dice one is better than dice three.

So, we did calculation in all of three cases.

So, all of this is true.

So, how is this even possible?

What is going on?

What is happening?

And here is some explanation.

We are used to comparing numbers.

We do it a lot. We do it in real life constantly.

This is a very common thing we do.

And we are used that certain properties hold for numbers.

For example, here is one of them.

If some number A is greater than some number B,

and B is greater than C,

then A should be greater than C,

which is a very common property in mathematics.

It is called "transitivity."

So, we are very used to to use it constantly.

And it translates to real life experience, again, constantly.

So, here is an Olympic motto,

for example: Faster, higher, stronger.

In all of these,

we are mostly used that transitivity holds that if someone is faster than someone else,

and the second person is faster than the third person,

then the first person is faster than the third one.

So, this is very typical and this is very standard.

But note that random variables are not just numbers.

They are more complicated.

And it is way harder to compare random variables.

And even if you find some way to compare them, like in our game,

we compare some random variables in a certain way.

If you find some way to compare random variables,

we are still not guaranteed that properties we are used

to are still holding for random variables.

And so, this is the problem in our puzzle, in our game.

For instance, transitivity in our game doesn't hold.

And that's what we have showed.

Okay. But what does it mean?

What our analysis give us for the game of a shady person?

What does it tell us?

So, let's recall what we have.

Dice two is better than dice one, dice three is better than dice two,

dice one is better than dice three.

And now, note that the shady person who tells you that to give you an advantage,

he will allow you to choose your dice first.

Actually, in this specific moment,

he has gain an advantage.

He's gaining an advantage,

because you choose your dice first.

So, let's see how the shady person will play his game.

He should be playing his game this way.

And he certainly real,

because it was his job.

Dice two is better than dice one,

dice three is better than dice two,

dice one is better than dice three.

So, if you pick dice one,

the shady person will pick dice two,

and on the long run, he will start winning.

If you pick dice two,

the shady person will pick dice three.

And if you pick three,

the shady person will just pick dice two,

which is better than dice three.

And that's the whole strategy for the shady person.

Okay. So, let's review main lessons we have

seen on this video. The probability is tricky.

We should be very careful when we apply our usual intuition to probability.

It is very tricky and very complicated, sometimes very contradicting.

And one more lesson,

we should probably avoid scam games.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play