lunes, 17 de octubre de 2011

The Game Show Problem

Reading the Book "The man who loved only numbers: The Story of Paul Erdos and the Search for Mathematical Truth" I met "The Game Show Problem". This problem is very simple and doesn't need any background, only simple logic is needed.

I just copy the problem directly from http://www.marilynvossavant.com/articles/gameshow.html.

"Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say #1, and the host, who knows what's behind the doors, opens another door, say #3, which has a goat. He says to you, "Do you want to pick door #2?" Is it to your advantage to switch your choice of doors?"

It is clear that if we don't change our choice, the probability to win is 1/3. But, what's the point here? We are not using an additional info we have: that the door #3 does not contain the car!! What if I change my choice when I have the opportunity and take door #2? Then, at the beginning we could win either if the car is in door #2 or door#3, then our chance to win is 2/3!!

The following tables clear all doubts.



Option 1 (mantaining the initial choice):

                   DOOR 1      DOOR 2         DOOR 3      RESULT
GAME 1     AUTO          GOAT             GOAT         Stay and you win.
GAME 2     GOAT          AUTO             GOAT         Stay and you lose.
GAME 3     GOAT          GOAT             AUTO         Stay and you lose.

   So the probability is 1/3

Option 2 (switching):

                    DOOR 1      DOOR 2         DOOR 3      RESULT
GAME 1     AUTO          GOAT              GOAT         Switch and you lose.
GAME 2     GOAT          AUTO              GOAT         Switch and you win.
GAME 3     GOAT          GOAT              AUTO         Switch and you win.

   
    So 2/3 !!!

jueves, 22 de septiembre de 2011

On the use of recurrent series in the search for roots of equations

Reading original papers can reveal  us “pearls” lost in time; moreover if they don’t  follow modern (and not so modern) standards of rigor. The master of this kind of results was Euler, who arrived at surprising results with amazing methods. The method we state here it's described by Euler in his 1748’s Introductio in Analysin Infinitorum.

 Let's mention two prior prerequisites:

[1] The first one is a well known recurrent series expansion (where the domain it holds…):

[2]The second one can also be easily deduced, we simply state it: 


 Now we have the necessary tools to explain the method. Suppose we have the following equation:

Suppose that all the roots are real and different. The above polynomium can be expressed in the following way:

Let be the following fraction:

The above fraction can be expressed as follows:
By [1] we know that the general term will be:
Let k be a very big number (infinitely big); because of the fact that the difference of numbers powers are bigger than the difference of that numbers, it will be a factor among

clearly bigger than the rest. Let p be the maximum of
Bearing in mind the statement before, we have 
and
 Therefore,
From that it follows that if we go on sufficiently through the serie 

the coefficient of each term divided by the preceding will give us the value p, and, consequently, the value of the smallest root, which will be equal to 1/p.

We can obtain with this method the value of the biggest root by means of the variable substitution x=1/z; in this case, the value p will give us directly the value of the biggest root.

We haven't mentioned the numerator coefficients because, indepently of their values, we will obtain the same value p. So, given

and bearing in mind [2], we can choose freely the values for 

EXAMPLE:

Suppose we want to obtain the biggest root of the following equation:


Let's deal with the variable change z=1/x and build the following fraction:

We choose arbritraily for

the values 1 and 2. The resulting series is: 1, 2, 7, 23, 76, 251, 829, 2738, ...

Therefore, the approximate value of the biggest root is 2738 / 829 ~ 3.3027744

Solving the equation in the traditional way we have as biggest root


which give as 3.3027756; value that exceeds our result by only a millionth.


For more info: Introductio in analysin infinitorum, chapter XIII