Math Is Fun Forum

chineseballer06

Member

Registered: 2011-02-01

Posts: 34

Expected Value

Hey everyone, I am struggling with this problems and would appreciate some help!
The question is:
Calculate the expected value of the greater of two numbers when two different numbers are picked at random from the numbers 1,...,n.  What is the expected value of the absolute difference between the two numbers?

Thanks!!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Expected Value

Hi chineseballer06;

This is straight out of a textbook but I do not remember which one I copied it from to my notes. But I remember this problem.

There are n(n-1) ways to pick two numbers from the unit interval 1 ... n.

If they are ordered high and low then there are:

The standard way now to do this is to look at the ordered pairs. There is 1 way for 2 to be the maximum and 2 ways for 3 to be the maximum and there are generally m-1 ways for m to be the maximum. Using the formula for expected value or expected number:

This checks out. If n=10 then the expected value of the highest number is 7.333333 which matches a simulation.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

chineseballer06

Member

Registered: 2011-02-01

Posts: 34

Re: Expected Value

Oh okay thanks for the help I don't know how I would have gotten that by myself. Do you know how I would do this for the second part?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Expected Value

Hi;

You do it in the same way. There are still

Ways to arrange n numbers with high and low. Now you go through the numbers in the same way. 1 is the lowest n-1 times. 2 is the lowest n - 2 times. n can never be the lowest. n-1 is the lowest one time so generally m is lowest n - m times. We use the same formula for expected value:

This agrees with simulations. Now for the difference.

Just subtract the expected value of the lowest from the highest.

The absolute value is implied in there and this agrees with simulations.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

chineseballer06

Member

Registered: 2011-02-01

Posts: 34

Re: Expected Value

Okay everything is making sense to me except how do you go from the part in the equation with the summation to just having n's?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Expected Value

You do the summation. That leaves just n's.

It is done by the techniques of the summation calculus. Which is the discrete counterpart to the integral calculus. Or you can use the Euler Maclaurin Summation formula or you can use a table. Or you can use polynomial interpolation! Or you can use Wolfram.

Some questions, how can your teacher have asked that question if you have not been exposed to the techniques above? Have you ever seen a summation done before by any of those methods? I know it is not usual for people to be exposed to the summation calculus until they hit DE's.

Okay, where did he go? I was talking to him and he went away.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

chineseballer06

Member

Registered: 2011-02-01

Posts: 34

Re: Expected Value

Yeah I don't know that's why I was so confused with this problem.  He introduced us to a little bit of Euler Maclaurin Summation formulas but thats about it.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Expected Value

Then that is what I will use.

THe EMS is the most amazing formula because it links sums, integrals and derivatives together.

For this problem it will look like this:

The same way in the integral calculus that the integral or the derivative of a polynomial is another polynomial. In the summation calculus the summation of a polynomial is another polynomial. Because of this EMS will terminate after a finite number of terms.

Notice the summation has been turned into a continuous problem, one involving integrals and derivatives.

Let's use the above formula on the first summation.

Cleaning up the RHS by algebra

Dividing by the denominator in the first problem n(n-1)/2

Can you handle the second summation on your own now?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

chineseballer06

Member

Registered: 2011-02-01

Posts: 34

Re: Expected Value

Yeah I think I can handle it! Thank you so much bobbym that helped a ton!!!  I don't get why my teacher assigned that problem lol the whole class was asking questions about it, but it makes a lot more sense now.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Expected Value

Hi;

You are welcome, glad you got it.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.