The Nation Has Problems 4
Posted by GreekHouse on Monday, November 5th, 2007 at 6:21 pm
One of the most important concepts in sports as well as probability deals with the concept of expectation. Statistics such as ERA or points per game are attempts to use expectation to quantify how good a player or team is. Although these stats aren't perfect, they are based on the concept of expectation.
In a nutshell, the expectation of a random variable is the average value. If there are only a finite number of possible outcomes, the technique for finding the expectation is simple. We take the sums of all possible outcomes times the probability of that outcome. For instance, if we're rolling a balanced 6-sided die the expectation of the number that we roll is
1/6*1 + 1/6*2 + 1/6*3 + 1/6*4 + 1/6*5 + 1/6*6 = 3.5
This technique works even if not all the probabilities are equal. Suppose we have a coin that falls on head 75% of the time. We want to know the expected number of heads if we flip the coin once. This gives E(Heads) = 0*.25 + 1*.75 = 75%.
If we are dealing with a situation in which there are an infinite number of possible outcomes, it may still be possible to calculate expectations in this way. This would require doing an infinite summation, which unfortunately means that our expectation may also be infinite.
Linearity of Expectation
One of the important properties of expectation is that it is linear. This means that if X and Y are random variables with finite expectations and a and b are constants, then E(aX+bY)=aE(X) + bE(Y).
Suppose we have a red die which we'll call R and a green die which we'll call G. We want to know the expectation of 3R+5G. Computing this expectation manually would be tough since we'd have to consider all possible outcomes. However, using the linearity of expectation it becomes easy. We know that E(G)=E(R)=3.5 and so E(3R+5G) = 3E(R)+5E(G)=8*3.5=28.
Another example is if we flip a balanced coin 100 times and want to know the expected number of heads. Calculating this directly would be extremely difficult, but using the fact that we know this expectation is 1/2 for a single coin, the expectation is 100*1/2=50.
Expectation and Gambling
If you want to become a successful gambler, the most important question you will need to ask yourself before making any bet is "What is the expectation of this bet?" (Ok, that last statement isn't entirely true based on practical conditions, but assuming you have a large enough bankroll, it's basically the only question that matters). If the expectation of a bet is greater than zero, it is said to have positive expectation (also denoted +EV). For instance, suppose I make a bet with SBG saying that we will flip a coin and he will pay me $100 if the coin is heads and I will pay him $105 if it is tails. Half of the time SBG will lose $100 and half the time he will win $105. So the expectation for SBG in this bet is .5*$105 + .5*(-$100) = $2.50. This bet is +EV for SBG and so he should take it (assuming he can afford the $100 if he loses). From my perspective, the bet is -EV and so I should avoid it unless I figure I will gain at least $2.50 in entertainment from the wager.
One common misconception about sports bettors is that they need to be able to predict winners with incredibly accuracy. This is not necessarily true. In fact, a sports bettor can lose more than half of his bets and still make money. Consider a baseball game between the Red Sox and the Royals. The Red Sox would likely be heavily favored to win this game and so a sports book might offer you 2:1 odds if you're willing to bet on the Royals. You have done extensive mathematical calculations and concluded that the Royals will win 40% of the time. If you wager $1, you will lose $1 60% of the time and win $2 40% of the time. This gives an expectation of .6*(-1)+.4*2=20 cents. Even though you will be losing money 60% of the time, you will be making 20 cents on the dollar for every. Note also that due to the linearity of expectation, you will win 40 cents on a $2 bet, $2 on a $10 bet, $200 on a $1000 bet, etc.
Sports and Expectation
This topic deserves its own post, so I will save it for later.
Problems
1. A typical sports book will offer -110 lines for things such as spread bets and totals. This means that in order for you to bet on these lines, you will have to wager $110 to win $1000 (these need not be actual amounts, you could wager $55 to win $50 or $1100 to win $100 for instance). Assuming there is a 50% chance of either side winning, how much will the sports book will the sports book make on average for a $100 bet (This quantity is called the vig)? How frequently does your side need to win in order to make this a profitable bet for you?
2. In role-playing games, you will frequently roll 4 balance 6-sided dice and compute the sum of the largest three (for instance, if you roll 2,3,5,6 your total will be 14. If you roll 4,4,4,4 your total will be 12). What is the expected value of this sum?
Rules
- I don’t care if you cheat, but if you do, don’t post the answer.
- Post all solutions/hints in white text (see below for instructions). Please post some dummy text at the beginning so that your solution doesn't show up on the main page.
- Ask questions and state ideas about the problem to generate discussion.
- I will post the solution eventually (assuming I know how to solve it) if nobody else does.
To post the answer in white use the following template below. If you're posting in a gray box, change "white" to "#f8f8f8"
<font color="white">
before your answer and
</font>
after your answer. You are encouraged to cut and paste that little bit of HTML.
Note to anyone with comment modification privileges: if you see an answer posted and not in all white, please edit the comment to add the whitening HTML.



Cheeseburger in paradise
Heaven on earth with an onion slice
Not too particular, not too precise
I'm just a cheeseburger in paradise
I'm not sure if this right - it seems a bit simplistic.
One die's expectation does not depend on the other numbers rolled, so I figured you could just multiply the expectation of 3.5 across the 4 die and get 14.
This would be right, except that you're not summing all 4 dice, you're only summing the largest 3. If you're summing all 4, your answer is correct.
Leave it to me to get bit on the ass by the details.
At least you'll have your cheeseburger. Mmmm...cheeseburger.
Damn sandwich took a bite out of me!
When I was just a baby,
My Mama told me, "Son,
Always be a good boy,
Don't ever play with guns,"
But I shot a man in Reno,
Just to watch him die.
Here's my crack at number 1:With a 50-50 chance of me losing my $110, then I can expect to lose $5n after n bets in the long run. Because for every $110 I lose, I have an equal chance of winning $100 next time, thus a net loss of $10 split over 2 bets is -$5/bet. I can show this with GH's equation: E(win)+E(loss)=0.5(100)-0.5(110)=50-55=-5. So, the house can then expect to take in those $5/bet.
Yep. Now try the second part of #1.
I was waiting on confirmation of that part before proceeding. I am finally getting the hang of "The Nation Has Problems".
Please don't cry
This world of words and meanings
That you feel outside
Something that you feel already
Deep inside
You deny
Go ahead and cry
On and on and on
To profit, my per bet expectancy would have to be at minimum $1. I then x(100)+y(-110)=1 where x is the expectancy where I win $100 and y the expectancy where I lose $110. Because I must either win our lose, x+y=1. Solve for y=1-x and substitute. Then (1-x)(100)+x(-110)=1. Expanding and collecting like terms leaves -210x=-99 => x=99/210 => x=.47. Thus, I would need to lose just 47% of the bets, or win 53%, to expect a profit.
Cause I need to watch things die
From a distance
Vicariously, I
Live while the whole world dies
You all need it too - don't lie.
Yeah, that's basically right. You actually need your expectation to be greater than 0 instead of 1. For instance, even if we restrict ourselves to integer dollar amounts, we could still wager an extremely large amount of money in hopes of gaining a tiny edge (for instance betting a million dollars with an expectation of +$1). This changes the result slightly, giving us a necessary probability greater than 11/21.
This is a test to see if I can do
white text.
We're gonna win Twins,
We're gonna score.
We're gonna win Twins,
watch that baseball soar.
Knock out a homerun,
Shout a Hip-hooray.
Cheer for the Minnesota Twins today.
You can even generalize this more, if the line is -X (where you bet X to win Y), you need to win at a rate of (X)/(X+Y). In your example, you need to win at a rate of (110)/(110+100) = 110/210 = 11/21. But if the line is -180, you need to win at a rate of 18/28, which is logical because a -180 line means that the team is more favored so you have a better chance to win. Alternatively, if you have a +150 line (where you bet 100 to win 150), you would be picking the underdog and would only have to win at a rate of 10/25, or 40%.
Right. When I used to do sports betting, this is what I would do. I would calculate the probability that a team would win and compare that to my break even case. This gives a good idea of how much of an edge you have on a particular bet.
In role-playing games, you will frequently roll 4 balance 6-sided dice and compute the sum of the largest three
I will not frequently do this, but I do know people who frequently do this.
It helps.
I walked into the office of one of my fellow grad students when he was struggling through this problem. I'm not a role playing guy anymore (except for video games), but I'm pretty sure I did this when I was younger.
The answer to #1 is that the house/book always wins in the long run.
This is mostly true (blackjack is beatable, but the house might kick you off). With sports books, the story is a little bit different.
The books will always win, but that doesn't mean that a skilled bettor can't also win. The general strategy is a bit counter intuitive, because you want to bet against the public. The books are not necessarily interested in maximizing their expectation, but they're also interested in minimizing their risk. If the books get the same amount of money in on a particular bet (here we're talking a standard -110 bet, other bets have similar strategy) they will make money no matter who wins. If there is a side in a particular bet that is expected to get a lot of money the house may lower odds on the opponent to encourage action on the other side. If the house lowers the odds enough, it can turn into a profitable bet. If you're an opportunistic bettor, you can notice these spots and place your bet 4TW!
In baseball, you could basically make money by betting against the Yankees and the Cubs every game of the season. It would be interesting to see how well you could do with this strategy, and I'd be interested in trying it some season.
The books will always win, but that doesn't mean that a skilled bettor can't also win.
The ability of one good gambler to win is subsidized by the dumb bets of 100 other bets of the ill-informed. I wish I was the former, but I'm usually the latter.
When it comes to something like betting on sports, if your goal is to win then the most important thing is your EV. If your goal is simply to have fun, then it's perfectly fine to gamble (hey, you're talking to the guy who lost $60 playing nickel slots in the Vegas airport).
Now that you know how to do it, you can calculate your EV on a particular bet. So if you're interested in betting on a football game, you can calculate how much you expect to lose and decide if it's worth it to you. I would typically assume you're 50/50 unless you have a good reason to believe otherwise. If your good reason is "my intuition is better than the skilled lines makers" you're wrong. The books make TONS of money off of people who think that their intuition is good.
Of course, the best way to go would be to just know something that most others do not.
I've wondered just how far you could push a stats-based system to account for things like pitching matchup and hitter-pitcher interaction to get odds on baseball games that might beat the bookies if you selectively chose bets where you had the greatest deviations from the stated line. Also, I would tend to think that sometimes when news breaks about a game that the line overreacts to the news before settling down to its proper value, so I think if you could time your bets right you'd help yourself out, too. Of course, if you believe much in the wisdom of crowds, this would still probably be a breakeven at best strategy in the long run.
Sabr-types always talk about how the postseason is so unpredictable, but I've never seen a good model fleshed out for how often one team should beat another team. To me, that would really tie the story together nicely. (The arguments I've seen have basically convinced me that the playoffs are mostly luck and all, I've just been a bit unsatisfied by those arguments these days.)
the (Bud) Black/(Steve) Schmoll option-betting formula??
Funny you should mention that. Recently, on the bus, I've been reading about futures and options. I wish I'd read about them in high school, because my dad would always listen to the Linder Farm Network in the morning, and I had NO IDEA what they were talking about. I knew they were listing the prices of something, but I didn't know the first thing about why people participated in the commodities market or how it is useful.
Anyway, the more I read about options, the more I think that you could view contracts to baseball players in terms of options. I'm not sure if that would be especially useful, but I think that there's a rough analogy that would hold.
I think there was an article on Hardball Times that talked about the value of player/team options in contracts by using a financial option valuation.
You might be able to use advanced statistics to gain an edge on the bookmakers. They are all doing the same thing though, I'm sure. They've had years and years of practice doing this stuff, and unlike the sports media, if they're wrong they pay for it. If you really want to be a successful sports bettor, you really need to know what the true line is in order to be able to identify those lines that have deviated from it. Because of the vig, betting most games isn't profitable and you will typically only find a few bets worth taking. If you want work on a system with me, I'd be happy to do it.
When it comes to stars getting injured, you are right. It is almost always best to bet on their team after the announcement is made. The public will all bet against that team and so the books will punish them by giving them a terrible line.
I wouldn't say the playoffs are unpredictable, I'd say they are predictably random. It's like flipping a coin. You may not know what side it's going to land on, but you do know that it will land on heads about 1/2 the time. I ran a simulation a few years back using Pythagorean methods for predicting winners and found that the top team should win the World Series about 20% of the time and the worst team in the playoffs should win about 5% of the time. The best team will win more than its fair share, it just won't win as much as people expect it to.
If you want work on a system with me, I'd be happy to do it.
I'm in, but we should be careful so that the Feds don't RICO our asses or haul us in for violating the Federal Wire Act.
Sounds to me like you need a bet placer in LV.
I wouldn't say the playoffs are unpredictable, I'd say they are predictably random.
Kind of like a crapshoot.
Yeah, that analogy works. It just seems to me that when people say that they are basically using it to mean that there is no skill involved (which is obviously false). Because of the parity in the league, your skill can only give you an edge, it can't guarantee victory.
But this swift business
I must uneasy make, lest too light winning
Make the prize light.
The quick brown fox jumps over the lazy dog.
Bring this old whisky to the blond smoking judge.
Franz speeds through Bavaria in a completely dilapidated taxi.
Okay, I feel like there has to be a better way to solve the second problem, but here I go.
The expectation of the largest three values is the same as the expectation of all four values minus the expectation of the smallest value. Thus, I will focus my attention on computing the expectation of the smallest value.
The first thing I want to do is generalize the problem a bit, so that we are working with n dice and m-sides per die.
I would like to know is the probability that x is the minimum, where x is a value on a face of a die. This can be calculated in the following way:
Let us count the ways that x can be a minimum. If x is a minimum, then all the die must read from x, x+1, ..., m-1, m. There are clearly (m+1-x)^n ways to do this. However, within those permutations where the die are exclusively in the set {x+1, x+2, ..., m-1, m}. There are (m-x)^n ways to do this. Thus, there are
(m+1-x)^n - (m-x)^n
ways for x to be the minimum given n dice with m sides per die. There are m^n total ways for the dice to land. Thus, the probability that x is the minimum is:
p(x) = ((m+1-x)^n - (m-x)^n)/(m^n)
Given this function, the expectation is:
<x> = Sum(x*p(x),{x,1,m})
This sum may seem daunting at first, but it is not so bad. I will leave out the overall factor of 1/(m^n) for the moment.
First split the sum into two parts:
Sum(x*(m+1-x)^n,{x,1,m}) - Sum(x*(m-x)^n,{x,1,m}
Re-index the first sum as a sum over y where y=x-1.
Sum((y+1)*(m-y)^n,{y,0,m-1}) - (same as above)
Since the name of the variable we are summing over is arbitrary, we can now set y=x. Also, in this step, I will distribute the (x+1) multiplication, so that we get something that looks like this:
Sum(x*(m-x)^n,{x,0,m-1}) - Sum(x*(m-x)^n,{x,1,m}) + Sum((m-x)^n,{x,0,m-1})
Now here's where our hard work pays off in spades. Clearly the terms from x=1 to x=m-1 cancel. Just as clearly, the term with x=0 is equal to zero, and the term with x=m is zero. Just to make things a bit prettier, I'll re-index the last sum so that q=m-x, and I'll bring back the factor of 1/m^n, so that:
<x> = Sum((q/m)^n,{q,1,m})
Is this the correct result? One thing in its favor is that it has the correct behavior in the limit n->inf. When the number of dice n gets very large, then (q/m)^n -> 0 except if q=m, so that <x>->1 when n-> inf, which is what we expect. (Intuitively, the more dice you throw, the more likely it is that you will throw a one, and once you throw a one, you can't get any lower than that!)
Still, this seems like a straightforward enough formula, that there should be an easier way to see that it is the right answer. Going back to our specific case with n=4 and m=6, it gives us:
<x> = 1 + (5/6)^4 + (4/6)^4 + (3/6)^4 + (2/6)^4 + (1/6)^4 = 2275/1296
Staring at that didn't help me interpret the result, unfortunately. Nevertheless, we can still answer the question at hand.
The expectation for the total of four dice is 3.5*4 = 14. Thus, the expectation for the greatest three of the four dice should be 14-(2275/1296). This is really quite an awful (or beautiful, I guess, depending on your tastes) number:
15869/1296
In its prime factorization, this is (and yes, 2267 is a prime number): (7*2267)/(2^4 * 3^4). As a decimal approximation, it's equal to roughly 12.24. That seems pretty reasonable to me, I suppose.
I'd feel more comfortable if I had a more straightforward argument, but I think that's the right answer.
Using the BFM, I have determined that your answer is correct.
What's BFM?
Big effin' mallet, if it's the same acronym we used to use.
Brute Force Method.
I built a spreadsheet with all 1296 combinations to check ubes' answer.
Big effin' mallet - Brute Force Method. Either way, you're beating the problem into submission.
this is similar to a tool common in the handyman/building trade: the BFH. 'cept that it is hardware as opposed to software.
And also in Doom, the BFG.
Yeah, that's certainly not the most elegant solution to the problem.
Says the mathematician. Although not necessarily the an elegant way of brute forcing (I'm partial to my Perl script), whatever works.
Reminds me of the problem of building a computer to solve chess. There were two methodologies, the "Right Way" and brute forcing it. Turns out one runs a lot faster when factoring in 40 years of speed improvements.
KOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOORN!!!!
Also, this problem gets much harder if you decide to throw out more than 1 die from your sum.
This is pretty much the way I did it too. I looked at the distribution of the minimum of the 4 dice. It is perhaps easier to think of it in terms of strings. For instance, there is only one string where you would throw out a 6, which is the string 6666. In order to throw out a 5, you have to have strings that only contain 5s or 6s. There are 2^4 of these, but one of them is the one the contains only 6s, so there are 2^4-1 of them. If you go on, you can write the expectation of this minimum in the same way you did.
If you wish to generalize, there is a lot of nice telescoping that goes on and so you end up with a (relatively) simple form. The expectation of the sum of n m-sided dice is n(m+1)/2 and so the expectation of the sum of the largest m-1 of these dice is
n(m+1)/2 + sum_{i=1}^m (i/m)^n
The sum above actually can be expressed as a closed form for any m and n, although the closed form is usually ugly. We had to prove this for n=4 in my combinatorics class last year. This has the form
sum_{i=1}^n i^4 = n(n+1)(2n+1)(3n^2 + 3n + 1)/30
In the case of n=6, we get 2275.
I'm seriously considering going back to bed. I'd like to blame the half-decaf. But that would be a lie. Mebbe the 24-oz porterhouse is slowing me down.
Actually, there is a section in my stats book that talks about ordering values of independent, identically distributed variables. This theory gives us answers, unfortunately, it becomes very hard if we care about anything other than the max or min values.
You can use this theory along with this technique to find a solution if you're really interested. Suppose generally you throw n m-sided dice and you want to find the expectation of the sum of the largest k values:
You can do this by either subtracting the smallest n-k values from the overall expectation or by simply calculating the expectation of the largest k. The proof presented by ubelmann represents the former and is easiest since it only involves finding the expectation of the minimum value. So this sum would be represented by
E(sum)=n(m+1)/2 - sum_{i=1}^{n-k} E(the ith smallest value)
Equivalently, you could have
E(sum)= sum_{i=1}^{n-k} E(the ith largest value)
Both ways work, in a particular case, you'd just want to look at whatever one is easiest to compute.
In general, I don't think there is any simpler way to compute these.
Also, this problem gets much harder if you decide to throw out more than 1 die from your sum.
I tried throwing out the two smallest (of four) die using my method (described below), and it was pretty similar in terms of the amount of work:
Expectancies:
aaaa - 7
aaab - 8+1/6
aabb - 9+1/3
aabc - 9+1/3
abcd - 9+4/5
6*7+120*8.1666+90*9.333333+720*9.3333333+360*9.8 = 12110
Expectancy of 12110/1296 = 9.34
You're the only one who can hold your head up high,
Shake your fist at the gates saying,
"I have come home now.
Fetch me the spirit, the son, and the father,
tell them their pillar of faith has ascended.
It's my time now, give me my wings."
There are only 5 possible patterns for the 4 die:
aaaa (i.e. 1111, 2222, ...)
aaab (1112, 2221, ...)
aabb (1122, 2233, ...)
aabc (1123, 2235, ...)
abcd (1234, 1456, ...)
For each pattern we can easily determine how many ways there are to roll that pattern (in parentheses is the number when we disregard rearrangements of the same 4 numbers)
aaaa - 6 (6)
aaab - 120 (30)
aabb - 90 (15)
aabc - 720 (60)
abcd - 360 (15)
So then we can figure the expectancy for each of these 5 groups. For instance, in the 'aaaa' group, (3+6+9+12+15+18)/6 gives 10.5. This part was a little bit "hammer and tongs", but it can be simplified so it is only necessary to calculate values for less than 100 of the 1296 possible rolls.
Expectancies:
aaaa - 10.5
aaab - 11.7
aabb - 11 2/3
aabc - 12.25
abcd - 12.6
So then, summing those gives 6*10.5+120*11.7+90*11.6666+720*12.25+360*12.6 = 15869.
Dividing that by the 1296 possibilities gives about 12.24 as the expected value for these rolls.
A little bit of brute force in there, and I sure wouldn't want to try to apply it to a larger case. But my answer agrees with ubelmann's so I feel good about that.
That first step is something I would have never thought of in a million bazillion years.
Questions for Big Mak regarding his answer
Round round get around
I get around
Yeah
Get around round round I get around
I get around
aaaa - 6 (6)
aaab - 120 (30)
aabb - 90 (15)
aabc - 720 (60)
abcd - 360 (15)
Mak: I just had my first cup of coffee and it's half decaf. But if there are 30 "aaab" patterns, mustn't there also be 30 "aabb" patterns? There's six unique "aa" patterns for a six-sided die. Once you fix the value of "a", that leaves five possible values for "b". What am I missing?
so with the "aaaa" pattern, you have 6*1*1*1 = 6 different outcomes; "aaaab" you have 6*1*1*5; "aabb" you have 6*1*5*1; "aabc" you have 6*1*5*4; "abcd" you have 6*5*4*3
isn't that 6+30+30+120+360= 546 different outcomes?
They tanned in the Florida sun a little too long. Ben Woodside, Lucas Moormann, Brett Winkelman, Mike Nelson and Tom Lunde were sunburned. “We were purple,” Nelson said.
Mak: I just had my first cup of coffee and it's half decaf. But if there are 30 "aaab" patterns, mustn't there also be 30 "aabb" patterns? There's six unique "aa" patterns for a six-sided die. Once you fix the value of "a", that leaves five possible values for "b". What am I missing?
so with the "aaaa" pattern, you have 6*1*1*1 = 6 different outcomes; "aaab" you have 6*1*1*5; "aabb" you have 6*1*5*1; "aabc" you have 6*1*5*4; "abcd" you have 6*5*4*3
isn't that 6+30+30+120+360= 546 different outcomes?
Your "'aaab' you have 6*1*1*5" doesn't account for different orders
1112 1113
1121 1131
1211 1311
2111 3111
etc. Three 1s and any other number can be rolled 20 times. 6*20 = 120.
No, the latter is more common than the former. I'll let you figure out why.
BrianS,
There's a very simple answer to your question which I have provided below all this verbiage.
first question about 'aaab' vs. 'aabb': 1112 != 2221, but 1122 = 2211
To count up the values, I put them all in order, assigning a the lowest and b the next lowest and so on.
So the 15 'abcd' possibilities are:
1234
1235
1236
1245
1246
1256
1345
1346
1356
1456
2345
2346
2356
2456
3456
Each of which can be rearranged 24 different ways. 24x15 = 360 = 6*5*4*3
Hope that clears it up.
first question about 'aaab' vs. 'aabb': 1112 != 2221, but 1122 = 2211
yah, that kinda shines light onto the dark recesses of my sleepy mind right there.
Mak,
You seem to have a very logical approach to these problems. I considered trying something like this for this problem, but decided it would be much too computational. You should be an engineer or something.
I think he's a chemist.
well, you know.
biology is applied chemistry. Chemistry is applied physics. Physics is applied math. Math is applied philosophy. Philosophy is applied bullshit. So, anywhere along the line, you are producing half-baked crap. Which means you fit right in here
... and bullshit is just applied biology, right?
Currently a Ph.D. candidate in chemistry, but I was a math/chem double major in college. My focus was on abstract algebra though, not so much with the probability.
I'm doing my research in graph theory/combinatorics. The thing about those subject is that there is basically no area of math that is out of bounds in terms of proof techniques. You can use combinatorial, algebraic or even analytical methods of proof.
One of the big trends in graph theory now is using probabilistic techniques for graph theory. Basically, you come up with an algorithm for showing how to build a graph (randomly) with a certain property. You then take the expected value of whatever it is you are looking at. You then calculate the expectation of that number. This can give you either an upper or lower bound since you know there is at least one graph that will have expectation >= the expectation. Likewise, there will be one <=.
How does that give you an upper or lower bound if there is at least one graph that will have expectation >= the calculated value and one that will have <= the calculated value?
Does one of those necessarily have to be equal to the calculated value? Or am I misinterpreting the whole explanation?
It's a little hard to explain it without going into excessive detail. You can check the wikipedia entry for a more detailed explanation.
I'm gettin' bugged driving up and down the same old strip
I gotta finda new place where the kids are hip
My buddies and me are getting real well known
Yeah, the bad guys know us and they leave us alone
still on that same cup of coffee. Problem 2 confuses me. I'm going to roll a fair, six-sided die 4 times and keep the 3 best rolls. The expectation for each independent roll is 3.5. So, uh, why isn't the expectation for the sum just the sum of the first three expectations, 10.5?
It was a painful celebration, with older teammates slapping them on their backs every chance they got. Perhaps it was a little payback for the times the five freshmen took it to them in practice.
That works when you don't throw any dice out or if you throw out the first die without regard to its value (I think). But, once you start throwing out the minimum, you have skewed the expectation. This is my understanding.
Consider 1666. The average of that throw is 4.75. Throw out the 1, though, and the average is 6. Skewing, I tell you!
We always take my car cause it's never been beat
And we've never missed yet with the girls we meet
None of the guys go steady cause it wouldn't be right
To leave their best girl home now on Saturday night
argh. Right. The probability distribution is being truncated (censored? I can never keep those two straight).
I typically do this for my students when I teach. We'll have weekly quizzes or homework and I'll allow them to drop the lowest few scores from their grade. It's nice because then I can have a strict policy of no make-ups. If they miss a quiz, then they'll just get to drop that one from their grade.
The only reason I ever look at these is for the song lyrics.
Heh - I thought I was the only one.
*high fives Rev. Jeff*
Taste the fruitful inhibitions of the human
Incapable of future seeing, beyond his thoughts of music