Finding the Distribution of Steps for Pairs Game with n Objects and m Values

[LENIN]

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).

 

[CompuChip]

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?

 

[LENIN]

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.

No, we choose which pair to randomize at random. And we repeat the proces until there are no more pairs.

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)?

Yes.

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).

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

Is a 'step' each time we randomize a pair, or each time we have to start over after randomizing all the initial pairs?

Each time we randomize a pair.

 

[csprof2000]

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.

 

[LENIN]

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).