# Math Help - markov chain problem

1. ## markov chain problem

Two children play a game in which they throw balls: Say that initially boy A has k balls and boy B has (n-k) balls. Boy A throws a ball to boy B with probability p and after this boy B throws a ball to boy A also with probability p (so they both wait for their turn).
There are times at which a boy wants to throw a ball but is out of balls. This happens in a fraction q of the throws, what is the expectation to the first time this happens?

2. I am unclear about a detail of this process. Since each boy has to wait their turn, does a boy dip into their stock whenever they need to throw a ball. Do the balls, then, "disappear" with probability 1-p? Maybe you should detail a few iterations of this process. For instance,

A has 5 balls, B has 5 balls.
A throws ball and has 4 balls remaining.
B receives A's ball and has 6 balls remaining.
B throws ball and has 5 remaining.
A does not receive ball and has 4 remaining.

I would keep a running tally in an ordered pair (A, B) = (k, n-k). Then at each iteration just adjust this object as needed. If you run a simulation of this many times, having it stop once a term of (A, B) reaches 0, scoring the number of turns it took to reach that point, you should get a good sample that represents q. Are you looking for a formal closed form answer or is an approximation from such a simulation alright?

3. Originally Posted by bryangoodrich
I am unclear about a detail of this process. Since each boy has to wait their turn, does a boy dip into their stock whenever they need to throw a ball. Do the balls, then, "disappear" with probability 1-p? Maybe you should detail a few iterations of this process. For instance,

A has 5 balls, B has 5 balls.
A throws ball and has 4 balls remaining.
B receives A's ball and has 6 balls remaining.
B throws ball and has 5 remaining.
A does not receive ball and has 4 remaining.

I would keep a running tally in an ordered pair (A, B) = (k, n-k). Then at each iteration just adjust this object as needed. If you run a simulation of this many times, having it stop once a term of (A, B) reaches 0, scoring the number of turns it took to reach that point, you should get a good sample that represents q. Are you looking for a formal closed form answer or is an approximation from such a simulation alright?
they don't throw with probability (1-p) and the turn goes to the other player. I have to find an expression and can't use a computer program. I can use that q is the fraction of times a player wants to throw but sees that he has no balls left. For example:

time 0: A has 1 ball, B has 5 balls. A throws ball
time 1: B doesn't throw
time 2:A wants to throw but has no balls left (so the time we are interested in is 2)

4. I cant see a clever solution involving q.

For a non-clever solution, you can note that you only need to look at one player. At the start of A's turn, the game will end:
• with probability p if A has no balls (ie, A has no balls and tries to pass one)
• with probability (1-p)p if A has n balls (ie, A has all the balls, doesn't pass one, then B wants to pass one

So, model the number of balls that player A has as a markov chain (it will look a lot like a random walk) and see how that looks for getting your solution.

Note i haven't worked this problem through to solution so I dont know how hard it will be to isolate the answer from the above chain, so apologies if im pointing you towards an unnecessarily messy solution!

5. So if someone doesn't throw with probability (1-p) is that a "skip my turn" then? What about the throw, does that not go into the stock of balls for the other boy or does it just vanish into the aether? There would be two totally different games depending on that structure. If it does not go into the stock, then this process is monotonically decreasing (the stock of balls will never increase). On the other one, it resembles a 1-D random walk experiment. Actually, it just is a 1D random walk with two separate lines that interact in the specified way (either on a turn the ball is "traded"). If the probability is set up in one way or the other, it may tend to end or it may be very unlikely to end (i.e., reach 0 balls on one of the lines or "walks"). I would assume we're interested in the latter experiment. The first one is not that interesting, but I'll think about the formulation of the probabilities in the mean time.

6. yes with probability (1-p) they skip a turn and balls don't vanish.
So i have to look at the expectation of time until one reaches 0 or n in a 1D walk?

7. yes, but be careful with the transition probabilities.

Suppose it's A's turn and he has x balls.

P(A has x balls on his next turn) = P(A throws and B throws) + P(A doesn't throw and B doesn't throw) = $p^2 + (1-p)^2$

P(A has x+1 balls on his next turn) = P(A doesn't throw and B throws) = $p(1-p)$

P(A has x-1 balls on his next turn) = P(A throws and B doesn't) = $p(1-p)$

You would need to be careful about the transition probabilities around x=0 and x=n. Alternatively, you use the same probabilities as above and find the expected time for the process to reach x=-1 or x=n+1. I think (but haven't proven) this will be the desired answer.

8. Originally Posted by sung
yes with probability (1-p) they skip a turn and balls don't vanish.
So i have to look at the expectation of time until one reaches 0 or n in a 1D walk?
That's what it sounds like to me. If you're interested, you can download R for free and run the code I wrote for this. I don't know how best to print it in the forum so I'll just paste the script with a different font. I think it is pretty straight-forward (especially if you know R). I define a function that takes a vector defining the balls (in my case they both have 5 = c(5, 5). The 'turn' variable indicates who goes first. I have 1 for A and 0 for B. Then 't' is the counting variable which is returned along with whose turn it was at the end of the walk. I ran this 1,000 times with p = 0.5 (default) and the summary was (A, B) = (1, 0) = (468, 532). I did it with 1000 and 10000 walks and with different probabilities. Seems to always come out around 50/50-ish. Other than that, 'throw' is 0 or 1 depending if a throw is cast or not (1 you throw). The probability of a sample is dependend on p, and depending on whose turn it is, if one does throw then we augment the vector 'balls' appropriately. Since R does vector arithmetic very well, the algorithm is easy to see (we subtract c(1, 0) and add c(0, 1) in case A throws, e.g.). The '#' comments out a statement that prints the findings to the screen. If you're doing individual walks you can delete the '#' and see the results. After the function I define a matrix 'x' to hold the results of 'k' walks. I then do a simple for loop filling each row of 'x' with the corresponding return vector that includes the count 't' and whose turn it was 'turn'. Cheers.

walk <- function(balls, turn = 1, p = 0.5) {
isFilled = TRUE
t = 0

while(isFilled) {
t = t+1
throw <- sample(0:1, 1, prob = c(1-p, p))
if (turn == 1) {
if (throw == 1) balls = balls - c(1, 0) + c(0, 1)
turn = turn - 1
} else {
if (throw == 1) balls = balls - c(0, 1) + c(1, 0)
turn = turn + 1
} ## end if-else
# print(c(t, ": ", ifelse(turn == 1, "A", "B"), throw, balls), quote = FALSE)
if (any(balls == 0)) isFilled = FALSE
} ## end while loop
return( c(t, turn ))
} ## end function

k = 1000
x <- matrix(NA, nrow = k, ncol = 2)
for(i in seq(k)) x[i, ] <- walk(c(5, 5), p = 0.5)