Suppose you have $20 and need $50 for a bus ride home. Your only chance to get more money is by gambling in a casino. There is only one possible bet you can make at the casino--you must bet $10, and then a fair coin is flipped. If "heads" results, you win $10 (in other words, you get your original $10 back plus an additional $10), and if it's "tails", you lose the $10 bet. The coin has exactly the same 50% probability of coming up heads or tails. What is the chance that you will get the $50 you need?
This is very similar to my original question, and I have changed it here for simplicity. In this case the casino is player A and the person is player B. Note that casino (Player A) has MUCH more coins than player B. I will now prove the question...
This problem is known as the ``Gambler's Ruin Problem''--a gambler keeps betting until he goes broke, or until he reaches a certain goal, and there are no other possibilities. Here is a nice matrix-based approach.
At any stage in the process, there are six possible states, depending on your ``fortune''. You have either $0 (and you've lost), or you have $10, $20, $30, $40 (and you're still playing), or you have $50 (and you've won). You know that when you begin playing, you are in a certain state (having $20 in the case of the latest problem). After you've played a while, lots of different things could have happened, so depending on how long you've been going, you have various probabilities of being in the various states. Call the state with $0 ``state 0'', and so on, up to ``state 5'' that represents having $50.
At any particular time, let's let P0 represent the probability of having $0, P1 the probability of having $10, and so on, up to P5 of having won with $50.
We can give an entire probabilistic description of your state as a column vector like this:
P0
P1
P2
P3
P4
P5
Now look at the individual situations. If you're in state 0, or in state 5, you will remain there for sure, because that is where the game ends. If you're in any other state, there's a 50% chance of moving up a state and a 50% chance of moving down a state. Look at the following matrix multiplication:
1 0.5 0 0 0 0 x P0 = P0 + 0.5P1
0 0 0.5 0 0 0 x P1 = 0.5P2
0 0.5 0 0.5 0 0 x P2 = 0.5P1 + 0.5P3
0 0 0.5 0 0.5 0 x P3 = 0.5P2 + 0.5P4
0 0 0 0.5 0 0 x P4 = 0.5P3
0 0 0 0 0.5 1 x P5 = 0.5P4 + P5
Clearly, multiplication by the matrix above represents the change in probabilities of being in the various states, given an initial probabalistic distribution. The chance of being in state 0 after a coin flip is the chance you were there before, plus half of the chance that you were in state 1. Check that the others make sense as well.
So if the matrix on the left in equation (3) is called P, each time you multiply the vector corresponding to your initial situation by P, you'll find the probabilities of being in the various states. So after 1024 coin-flips, your state will be represented by P1024.
Here is a probability matrix of probabilities of various states after 1024 flips:
1 0.8 0.6 0.4 0.2 0
0 0.0 0 0.0 0 0
0 0 0.0 0 0.0 0
0 0.0 0 0.0 0 0
0 0 0.0 0 0.0 0
0 0.2 0.4 0.6 0.8 1
I write 0.0 because in actual fact that coordinate is 1.549x10^-93 which is an extremely small number (EXTREMELY SMALL!)
So for practicality I will write it like this
1 0.8 0.6 0.4 0.2 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0.2 0.4 0.6 0.8 1
So what does this probability matrix tell us? Well it tells us that we have a 100% chance of winning! Look at the 1 in the bottom right hand corner. This coordinate represents where the game finishes by winning. It says 1 which represents 100% chance. But there is also a 100% of losing?!
Can anyone tell me why this is?
Also know think of why Casino's always end up on top!
.