This two-part course builds upon the programming skills that you learned in our Introduction to Interactive Programming in Python course. We will augment those skills with both important programming practices and critical mathematical problem solving skills. These skills underlie larger scale computational problem solving and programming. The main focus of the class will be programming weekly mini-projects in Python that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 1 of this course, the programming aspect of the class will focus on coding standards and testing. The mathematical portion of the class will focus on probability, combinatorics, and counting with an eye towards practical applications of these concepts in Computer Science. Recommended Background - Students should be comfortable writing small (100+ line) programs in Python using constructs such as lists, dictionaries and classes and also have a high-school math background that includes algebra and pre-calculus.
Expected Value
Loading...
来自 Rice University 的课程
Principles of Computing (Part 1)
362 个评分
从本节课中
Probability, randomness, and objects/references
This we will learn how to use probability and randomness to solve problems.
与讲师见面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[MUSIC]
So today we'll be talking about the expected value.
What we mean by that is, we will be
looking at a trial, when we conduct a certain trial.
And we will be looking at the outcomes that we see from this trial.
And the question that we are interested in is,
what is the expected value that we expect to see?
So, for example, if I am rolling a dice just once and it is a fair dice
with 6 sides, what is the value that do I expect once I roll that dice?
Okay, so, that question becomes actually interesting,
because what is the meaning of that value?
So, I have one dice and I roll it, the possible outcome that I
can see are one, two, three, four, five, six, these are the possible values.
So now I'm saying, if I roll a dice once, what is the expected value?
So each one of these since the dice is, the dice is fair,
each one of these is going to have a probability of one over six.
All right, it's one over six.
And the question is, what does it mean to say that
I expect to see a certain value when I roll that dice?
One interpretation of that is that, is, is
to think about the following trial or experiment.
If I take that same dice and I roll it a very large number of times.
Think about it, roll it for a million times, a billion times, and so on.
And then I look at the values that I've seen every time.
And then I look at the average value from these values.
And look at the, what do I see there?
So for example, I take this, I take this dice, I roll it.
Let's make our, our life easier and let's say, we roll it 600 times.
So I wrote 600 times, so and every time I roll it,
I write down the, the side I see, the number I see.
So this is the first time.
This is the second time, the third time, all the way to 600.
So if I ask another question, is that for this dice since it is fair.
It has six sides, each one with
the, appearing with the probability one over six.
And I ask you, what do you expect to see here as
number in these boxes when I'm writing down these values 600 times.
I think it makes sense to say that we are
going to see 1 on the order of about 100 times.
We are going to see 2 on the order of 100 times, 3 on the
order of 100 times all the way to 6 of the order 100 times, right?
If the, if the probability of seeing 1 is 1 over 6.
So, but what this mean is that we expect to see 1 every 6 times we roll that dice.
So here, now if I am saying what is the average value
that I expect to see when I roll this dice 600 times?
I would basically say, okay I have, I've seen the value of 1 100 times.
I've seen the value 2, 100 times.
I have seen the value 3 100 times.
I have seen the value 4, 100 times.
I have seen the value 5, 100 times and the value 6,100 times.
I look at this and all this divided by 600, and this
is going to give me the expected value or that I would see from rolling this dice
600 times, or similarly this would be the expected value of seeing each one,
the, the expected value of that I would see when I roll that dice once.
Okay?
So in this case, what we are saying that we basically take
the value that we see times the number of times we have observed.
We take the sum over all these possibilities, divide
by the number of time we repeated that same experiment.
Now going back to the history of expected value and looking at this dice.
What is the expected value that I would observe if I roll the dice only once?
Okay.
So the way would do that again in this case is
1, the value 1 will appear with probability of 1 over 6.
2 with the probability 1 over 6 or 3 with the
probability 1 over 6 plus 4 with the probability 1 over 6.
Okay.
So, this would be the expected value.
When, if I roll this dice only once.
And if we compute this value here, so we have 1 6th
plus 2 6th plus 3 6th plus 4 6th plus 5 6th plus.
1 plus 2, 3, 6, 10, 15,
21 over 6, and this is 3.5.
So this is the expected value for this trial
where I roll this six sided fair dice once.
So I expect to see a value of 3.5.
So this immediately should raise a flag.
What does it mean to say that the expected value is 3.5?
This dice actually does not have a side that has a value of 3.5, okay?
So this is why it makes sense to think about
the meaning of this notion of expected value in terms of
the mean or the average value that we would see if
we had roll this dice a very large number of times.
Mathematically in, in fact is that, if we roll it an infinite number of times, okay?
So this will be the expected value of this dice.
Now if we make this a bit more interesting and
I say, I take this dice and I roll it twice.
Okay.
So I take the dice, roll it once.
I roll it twice, a second time.
And then I record the, the two values that I have seen.
And I look at the sum of these two values.
And then I say, what is the expected value I would see.
The expected sum, of the two numbers I get from rolling that dice twice.
Okay.
So now, the first question we have to ask,
is what are the possible sums that we can see?
Since we have the dice we are rolling
it twice, and we are recording the two numbers.
So we have two numbers, x, y, right?
So we are going to roll the dice first and we are going to see some value x.
We roll it again, we see some value y.
Of course, x can be either 1 or 2 or 3 or 4 or 5 or 6.
The same thing with y.
So if we look at the sum of these two,
we ask what is the possible sum we can observe?
It going to be, the smallest possible is going to
be to where both rows basically showed 1, or
it can be 3, can be 4, all the way to the largest possible sum which is 12.
Now, when we compute the, the expected sum from this experiment or this trial,
we basically have to see what are possible ways of generating each one of these sums.
So for example x plus y equal 2, to,
to get the sum 2, x has to be 1 and y has to be 1.
So the first time I rolled the dice, I've seen 1, second time I have seen 1.
There is no other option for getting a sum
of 2 given this dice that I'm rolling it twice.
Now what is the probability of seeing 1 the first time?
The answer is 1 over 6.
What is the probability that I see 1 the second time?
It is 1 over 6.
Now since these two, two, two events are
independent, the probability of seeing 1 and 1 is 1 over
6 times 1 over 6 and the probability is 1 over 36.
This is for the sum of 2.
What happens if the sum is 3?
The, the, the way I could have gotten a sum of three, is either x is 1 the first
time I rolled the dice I saw 1, the second time it's 2,
or the first time I saw a 2 and the second time I saw a 1.
Again the probability of seeing 1, and then seeing 2
is 1 over 6 time 1 over 6, 1 over 36.
And this is 1 over 6, 1 over 6 equal 1, 36.
So the probability of seeing this is this plus this area, right?
So it is.
Okay.
And then again we can get what is the
probability, for example, that x plus y is 4.
And we just have to list all the possibilities, which are either x
is, the first time I rolled the dice it was, I saw 1.
Then I saw 3, or the first time it's 2 and
the second time is 2 or the, sorry this is x.
Or the first time is 3 and the second time is 1.
And using similar, computation like this, the probability of this happening, this
event, 1 and 3 is 1 over 36, 1 over 36, 1 over 36.
So the probability that the sum is 4 is 3 over 36.
We can re-repeat this all the toward 12, what
is the probability of seeing a sum of 12?
Again, in this case, the only possibility is seeing
6 first time and seeing 6 the second time.
We end up with a probability of 1 over 36.
So now we can say what is the expected value of the sum?
What is the expected sum that we, okay, we would see
from this trial where we roll the dice, the dice twice?
It's basically the probability of observing any of the sums.
I or we can say probability of whatever variable of x plus y times x plus y.
And we sum over all possible values of xy, x plus y equal 2, 2 16th.
So this notation here is saying that the sum x plus y can be
2 or 3 or 4 all the way to, to 12, sorry, not 16.
And what is the probability of observing each sum times the sum itself.
Which is in our case, is the probability of 2
times 2, plus the probability of the sum being 3 times 3, the
probability of 4 times 4, the probability observing 12 times 12.
We have seen that the probability that the sum is 2 is 1 over 36 times
2 plus the probability of, that see we, we have sum of 3 is 2 over 36 times 3.
The
probability of 12 again is 1 over 36 times 12, and
this will give us the expected value of that sum.
So, now this is again the expected value for rolling
a dice twice and looking at the sum and so on.
But, there are even more, much more interesting
applications of this expected value and what, what
kind of value we expect to see when
we have a [UNKNOWN] process or a random process.
For example, in the case of DNA sequences, if I am having 2 sequences, A-C-C-T
and A-C-G-T, and I am saying that this sequence evolved from this sequence.
For after a given amount of time, the question is some observe
these two sequences and they ask are these two sequences the same?
Or do they correspond?
Of course if I compare these two sequences,
I see they differ at the third position, right?
But the question is, given that we know that mutations happen, that they change
the letters, these DNA nucleotides, is this something that I would expect to see?
So for example, if I know that there's a probability of .25, a probability
of one quarter, that the position would change in the sequence, okay?
And every position is independent, then this is expected after a
certain amount of time, because if I'm saying that every letter here
has a probability of 1 over 4 of changing to a different
letter, then I would expect this after certain amount of time, right?
Because mutations will happen.
I wouldn't, I wouldn't expect this if not time has past, the
sequence stays the same, but if time has passed and mutation can
happen, then we have this notion of expectation or what is the
expected sequence after certain amount of time and knowing something about mutation.
So, in this case the notion of expectation, and the
expected value is central to us being able to say
whether this sequence and this sequence are related, versus are
they different because they have nothing to do with each other.
