Question

Done

Answer 1

Didnt fermat already do this? or was it Laplace?

Answer 2

Two players A and B play the following game:

Initially, player A has nA $$ and player B has nB $$, both greater than zero.

They toss a fair coin and

if it turns HEADS,
then player B gives one $ to A.

If it turns TAILS,
then player A gives a $ to B.

The game stops when one of the players loses all his $$.

What is the average number of steps until the end of the game ?

Answer 3

i think i used some taboo dollar signs

Answer 4

Haha! What do you mean about Fermat and Laplace?!

Answer 5

I recall reading somewhere that a few of those old guys used to write letters back and forth about stuff like this, and thats how probability was developed

Answer 6

That's quite interesting! Although I still feel a bit in the dark about how to start this question!

Answer 7

yeah, im not to keen on how to go about it either. Was hoping that sorting out the info would have jogged some memories for me ... Satellite and Zarkon are the kings of this sort of material.

Answer 8

the hint is prolly something basic .... if i can recall that info it might be useful :)

Answer 9

let:\[ M_j=\text{ expected number of steps required, when player A has j pounds}\]
and try to set up a recursive equation for \(M_j\)
\[M_j = M_{j-1}\pm1\]
but then that doesnt account for the expected value of a toss does it

Answer 10

is this from a textbook or is it an online question?

Answer 11

It's a textbook question, Sheldon Ross- First course in probability.
I was thinking that,but I don't understand how to set up this recursive equation.

Answer 12

does the problem have a "title"? if so i think i can find a solution manual

Answer 13

or even the title of the chapter its in?

Answer 14

It's in the section on Markov chains, I think it is to do with random walks?

Answer 15

http://www-personal.umich.edu/~romanv/teaching/2011-12/425/01-25.pdf

this has something close to this problem i thnk

Answer 16

the walk near the end might be adaptable to this, but i cant make heads nor tails of the information ....

Answer 17

Since we are both on the same Assignment let me help you out...
Think of this as a random walked modelling the number of £ that player A has. Then, the game ends either when player A gets to £0 or player A gets to £Na + Nb.
Now consider the following:

"If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or −a is ab"

So I have the answer coming out as Na*Nb, I'm still trying to prove the above quotation though, I think using Pascal's Triangle could be a way to go... look at this section if you are stumped: http://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk

Answer 18

Thanks! So are you not going down the route with the hint?

Answer 19

Might be doing that now. http://copper.math.buffalo.edu/urgewiki/uploads/Miscellaneous/RandomWlak.pdf
If you look at the end of the 3rd page of this, you'll see the recursive equation you desire...

i.e mj = 1 + 1/2(m(j+1) + m(j-1))

Answer 20

@satellite73 take a peek eh?

Answer 21

Did you have any luck?

Answer 22

Have a look at this:
http://galton.uchicago.edu/~lalley/Courses/312/RW.pdf
End of page 2/Start of page 3

Answer 23

This feels like STEP all over again. When will you leave alone?!

Answer 24

I hope your planning on going into research hahaha.
Term is almost over though!

Answer 25

16 weeks til final results day!

Answer 26

Hope you've got it all done, I have a full solution now!

Answer 27

I do not :(
Assume that I could derive that recurrence relation. I then solve it so that I have mj. Then do I have to sub in initial conditions? And then what do I do? Sorry, I am just completely baffled :(

Answer 28

Okay so you should be able to get the recurrence relation:
2m(j+1) - m(j) - m(j+2) - 2 = 0.

Use the Difference Equation notes from last term to help you solve this
tip: Let m(j) = Cj^2 + Dj + E

Now, for initial conditions we have 2. Basically if player A has £0, then m(0) = 0.
Also, if player A has £(nA + nB), then by construction player B has £0, so m(nA + nB) = 0 too.

From these, you get a solution for m(j) in terms of nA, nB and j.
Now think what your m(j) actually is. m(j) is the expected number of steps for the game given player A starts with j.

But we already KNOW what player A starts with (he starts with nA). So then just put in m(nA) and that should give you the solution nA*nB. I'm staying up for about 10 minutes longer if you need any other hints.

Answer 29

In case you didn't realise the initial conditions work since if either player starts at £0 then the game is over as soon as it begins...

Answer 30

You are a God

Answer 31

The only other thing I think is how you managed to derive that relation in the first place?

Answer 32

It's not something I did alone lol. But here are 2 pages that will help grasp why it's that...

http://copper.math.buffalo.edu/urgewiki/uploads/Miscellaneous/RandomWlak.pdf (Check 1.1 Basic Properties)

http://galton.uchicago.edu/~lalley/Courses/312/RW.pdf

Thanks for the medal, glad to help anyone on this assignment. I don't think we are properly prepared for this question really lol

Answer 33

I agree! But on behalf of the many students I can see viewing this, thank you!!! I hope they were all as terrified as me by your comment that final results day is in 16 weeks ;)

Answer 34

To be honest this problem just reminded me of STEP and I thought it was fun (yeah I'm weird). I ask for help on forums way more than I give it out so I guess I owed this one!

Answer 35

Hahaha I'm sure it would be easier to see the fun side if this wasn't so pressured :P