Results 1 to 8 of 8

Math Help - markov chain problem

  1. #1
    Junior Member
    Joined
    Jul 2009
    Posts
    27

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2009
    Posts
    27
    Quote Originally Posted by bryangoodrich View Post
    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)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    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!
    Last edited by SpringFan25; May 23rd 2011 at 11:27 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jul 2009
    Posts
    27
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    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.
    Last edited by SpringFan25; May 23rd 2011 at 12:02 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    Quote Originally Posted by sung View Post
    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Markov Chain of random variables from a primitive markov chain
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 19th 2011, 08:12 AM
  2. Markov chain problem
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: October 18th 2009, 04:52 AM
  3. Markov Chain Problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 21st 2009, 07:59 AM
  4. Markov Chain Problem
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 1st 2009, 07:29 PM
  5. Replies: 2
    Last Post: October 28th 2008, 06:32 PM

Search Tags


/mathhelpforum @mathhelpforum