Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Are there any pairs

  1. Dec 19, 2008 #1
    This question is part of a larger problem I'm working on, but it seams to be causing me the most problems. Any help or tip would be appreciated. So here it goes. We have n objects which can have any of the m allowed values. If we find a pair of objects with equal values, we change their values to new random values (from 1 tom m). We repeat this until there are no more pairs. What is the distribution of the number of steps this game can last.?

    I did some numerical simulations but I would like to have an analytical solution. I only managed to get an analytical solution for the probability that the game ends in the first step. I also noticed that the probability has a peak close to the beginning (it's not monotonous as I first suspected).
     
  2. jcsd
  3. Dec 20, 2008 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    So if we have for example
    1 2 3 2 4 2
    Would we first randomize the first occurrence of the 2's; and then if one of them again happens to form a pair, for example
    1 5 3 2 4 2
    we do it again.

    If there are two pairs, for example
    1 2 3 4 2 5 1
    will we do them separately (first the 1's, then the 2's)? If so, and randomizing the 1's again produces a pair, do we first do the new pair or first the 2's (not sure if this matters).
    Is a 'step' each time we randomize a pair, or each time we have to start over after randomizing all the initial pairs?
     
  4. Dec 20, 2008 #3
    No, we choose which pair to randomize at random. And we repeat the proces until there are no more pairs.

    Yes.

    We allways choose pairs at random (if there are any ofcourse).

    Each time we randomize a pair.
     
  5. Dec 20, 2008 #4
    Well, for n = 2, we could have:

    1 1
    1 2
    2 1
    2 2

    2 of these games last zero turns (already good).

    so P(t = 0) = 1/2

    Whichever of the two identical pairs we have, we
    have a 1/2 chance of winning on the next turn. So,
    for n = 2, we have

    P(T = t) = (1/2)^(t+1)

    For n = 3, we could have:

    1 1 1
    1 1 2
    1 1 3
    1 2 1
    1 2 2
    1 2 3
    1 3 1
    1 3 2
    1 3 3

    2 1 1
    2 1 2
    2 1 3
    2 2 1
    2 2 2
    2 2 3
    2 3 1
    2 3 2
    2 3 3

    3 1 1
    3 1 2
    3 1 3
    3 2 1
    3 2 2
    3 2 3
    3 3 1
    3 3 2
    3 3 3

    We see that exactly 6 of these are favorable immediately,
    and so P(t = 0) = 6/27 = 2/9.

    If we have one of the ones with all of them the
    same, then the probability we win on the next turn
    is 1/4, because we can pick one pair randomly in
    4 ways, and only one will be favorable.

    If we start with 2 of a kind and 1 off, then the
    same is true: we can pick the pair to randomize in
    one of 4 ways, 1 of which is favorable.

    So...

    P(T = 0) = 2/9

    P(T = 1) = 7/9 * 1/4

    P(T = 2) = 7/9 * 3/4 * 1/4

    P(T = 3) = 7/9 * 3/4 * 3/4 * 1/4

    P(T = t) = 7/9 3^(t-1) / 4^(t)


    Just from the n=2 and n=3 cases, I can make a wild
    guess that the general solution looks something
    like...

    P(T = t) = c (n-1)^(t-1) / n^t

    for some c, which may vary a little bit.

    Does that look about right, as far as fitting the curve goes?

    DISCLAIMER: this is all wild and speculative conjecture.
     
  6. Dec 20, 2008 #5
    Your 2 examples seam to work OK but the generalization doesn't. I will see if I can do something with it. There is also still the problem if m doesn't equal n. If m<n the solution is trivial (the game can not end).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Are there any pairs
  1. Ordered pair (Replies: 52)

  2. Paired t test? (Replies: 3)

Loading...