# Game involving probability

• Oct 16th 2007, 08:51 PM
ThePerfectHacker
Game involving probability
Here is a nice probability problem I saw in class about a week ago. It involves playing a game.

Consider a game where the player has initially $d$ dollars. The player tosses an unfair die (or flips an unfair coin, or whatever) so that the probability of winning is $p$. If he wins he earns a dollar, if he loses he loses a dollar. This is played until one of two situations occurs: either he reachers a certain amount $n$ or he is bankrupt i.e. he loses all his money. Given $d,p,n$ find a formula that will give the probability of succes (meaning he reaches $n$).

According to our textbook this is a classic going all the way back to Bernoulli (I just forgot which one it is :D).
• Oct 17th 2007, 03:52 AM
DivideBy0
Ok I'll have a crack at it, it might be wrong though

Let random numbers $x-y=n-d$. It doesn't matter how many trials there are, but as long as the difference between the number of times a success (x) is flipped and a failure (y) is flipped is the same, then we will have increased by x-y = n-d to reach n.

Then there are $\ _{x+y}C_x$ ways to arrange the probabilities

So

$Pr(Success)={{x+y} \choose x} p^x (1-p)^y$

Of course it requires to know 3 things:
1. N
2. D
3. The number of trials.
It also looks quite similar to hypergeometric distribution

thanks for posting this problem :P
• Oct 17th 2007, 04:27 AM
CaptainBlack
Quote:

Originally Posted by DivideBy0
Ok I'll have a crack at it, it might be wrong though

Let random numbers $x-y=n-d$. It doesn't matter how many trials there are, but as long as the difference between the number of times a success (x) is flipped and a failure (y) is flipped is the same, then we will have increased by x-y = n-d to reach n.

Then there are $\ _{x+y}C_x$ ways to arrange the probabilities

So

$Pr(Success)={{x+y} \choose x} p^x (1-p)^y$

Of course it requires to know 3 things:
1. N
2. D
3. The number of trials.
It also looks quite similar to hypergeometric distribution

thanks for posting this problem :P

Except if y>d, you may have gone bust before winning n dollars.

In fact if you don't worry about your fortune becoming negative you will
be n dollars up at some time with probability 1 as long as p>0.

RonL
• Oct 17th 2007, 04:58 AM
DivideBy0
Quote:

Originally Posted by CaptainBlack
Except if y>n, you may have gone bust before winning d dollars.

I have an example here... i dunno, things are getting pretty weird...

Say x + y = 10
Take n = 2, d = 1

Also x - y = n - d

So x - y = 1

Then x=11/2, y = 9/2, so now you have to do non-integer factorials! Is this always the case with y>n? I'm getting pretty bogged down with the maths here.
• Oct 17th 2007, 12:50 PM
Opalg
One way of analysing this is by stochastic matrices. You have a system with n states 0,1,2,...,n, in which 0 (the losing state) and n (the winning state) are absorbing states (once you get there, you stay there). The matrix of transition probabilities is

$\begin{array}{c|ccccccc}&n&0&1&2&3&\ldots&n-1\\ \hline
n&1&0&0&0&0&\ldots&p\\ 0&0&1&q&0&0&\ldots&0\\ 1&0&0&0&q&0&\ldots&0\\ 2&0&0&p&0&q&\ldots&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\ddots&\ddots&\ vdots\\n-2&0&0&0&\ldots&\ldots&0&q\\ n-1&0&0&0&\ldots&\ldots&p&0\end{array},$

where q = 1-p. This matrix can be partitioned into blocks as follows:

$\begin{bmatrix}I&S\\0&R\end{bmatrix}$, where I is the 2x2 identity matrix, S is the 2x(n-2) matrix $\begin{bmatrix}0&0&\ldots&0&p\\ q&0&\ldots&0&0\end{bmatrix}$, R is the (n-2)x(n-2) matrix

$\begin{bmatrix}0&q&0&\ldots&0\\ p&0&q&\ldots&0\\ \vdots&\ddots&\ddots&\ddots&\vdots\\0&\ldots&\ldot s&0&q\\ 0&\ldots&0&p&0\end{bmatrix}$ and 0 is an (n-2)x2 matrix of zeros.

The theory of Markov processes tells you that the probabilities of winning and losing, given that you started with d dollars, are given by the two entries in the d'th column of the matrix $S(I-R)^{-1}$.

The only snag is that the inverse matrix is not easy to compute, even for a relatively small value of n (unless maybe you have access to a good computer algebra package, which I don't).
• Oct 17th 2007, 01:23 PM
ThePerfectHacker
This problem is from my book is on chapter on conditional probability. The classical solution does not involve the use of Markov Chains or Stotaic Processes*.

*)In fact, I have no idea what these things even are. I definitely heard of them but never used them.
• Oct 20th 2007, 06:59 PM
ThePerfectHacker
Hint: Consider the following probabilities $P_i = \mbox{ probability of winning with }i \mbox{ dollars }$. So $P_0 = 0$ and $P_n =1$.
(So you want to find $P_d$).
• Nov 7th 2007, 06:15 PM
ThePerfectHacker
In case you are interested here is Bernoulli's elegant solution.

Let $P_k$ ( $0\leq k \leq n$) be the probability that the player will win the game with $k$ dollars. So $P_0=0$ because at zero dollars the game is over and he will not win. And $P_n=1$ because he already reached his desired amount.

If the player gets wins on coin flip then his probability of winning is now $P_{k+1}$. If the player loses on a coin flip his probability is now $P_{k-1}$. Since the probability of getting a win on a die throw is $p$ it and the probability of losing is $(1-p)$ is means: $P_k = pP_{k+1} + (1-p)P_{k-1}$.

This means, $pP_k + (1-p)P_k = pP_{k+1} + (1-p)P_{k-1}$ thus $P_{k+1} - P_k = \frac{1-p}{p} (P_k - P_{k-1})$.

Now we will list all these values from $1$ to $n$:
$P_2 - P_1 = \frac{1-p}{p} (P_1 - P_0) = \frac{1-p}{p}P_1$
$P_3 - P_2 = \frac{1-p}{p} (P_2 - P_1) = \frac{(1-p)^2}{q^2}(P_1 - P_0) = \frac{(1-p)^2}{p^2}P_1$
...
$P_n - P_{n-1} = \frac{1-p}{p} (P_{n-1}-P_{n-2}) = \frac{(1-p)^{n-1}}{p^n} (P_1 - P_0) = \frac{(1-p)^{n-1}}{p^{n-1}}P_1$

We want to know $P_d$, that is what we are trying to find.

So add the frist $d-1$ equations:
$P_d - P_1 = P_1 \sum_{j=1}^{d-1} \frac{(1-p)^j}{p^j}$
This is a geometric series.
So the solution depends whether or not $(1-p)/p=1$ (i.e. $p=1/2$) or not.

I am not going to go further because it gets a little messy but the algebra is straightforward.

And finally to complete this problem we need to find $P_1$ be that is easy to find if we sum all these equations and use the fact that $P_n = 1$.