How to determine the expected number of items to be selected before the first right item

Question

There are n balls of different colors in a row in a given order. We need to rearrange the balls by swapping 2 balls at a time until the arrangement satisfies certain conditions defined on their colors. What is the expected number of swaps you'll make. It is guaranteed that at least one arrangement exists that satisfies the conditions.

A function f determines that a given arrangement satisfies the condition. A function g returns a set of all possible arrangements.

Example cases:

• 1 ball. 0 swaps need to be made since it already satisfies the conditions.

• 3 balls: two reds and a green. There are two possible arrangements that satisfy the condition, out of 6 possible arrangements in total. With 3 balls, we have three distinct arrangement by color. Each arrangement by color repeated twice. Hence, there's a 1/3 probability that any given arrangement will be made. By supplying our arrangements to f, we determine that there is one of the three distinct arrangements that satisfies the conditions. Therefore, there are two of six total arrangements. In this case, the expected number of swaps is 3.

  3. 7 balls: a red, two greens and 4 blues. There are 144 possible arrangements that satisfy the condition, out of 5040 possible arrangements in total. That gives a 1/35 probability of making a valid arrangement. There are 105 distinct arrangements by color and 3 that satisfy the condition repeated 48 times each. In this case, the expected number of swaps is 59.3380 correct to four decimal places.

My findings: The number of possible arrangements is n! With f and g, we can determine the number of valid arrangements and hence the probability of choosing a valid arrangement.

Question is, the expected values gotten in the sample, how were they determined?

Answer 1

I guess you want to calculate the expected smallest number of swaps required. I will continue assuming this.

Call $x$ a possible initial arrangement and $h(x)$ the number of swaps that need to be made to get from $x$ to an arrangement that satisfies your condition. Now, if $p(x)$ is the probability that $x$ is the initial arrangement, then the expected number of swaps is $$\sum_{x\in X}p(x)h(x)$$ where $X$ is the set of all possible initial arrangements.

I guess that you can calculate $p(\cdot)$ from your problem's primitives, as you do in your examples and $h(\cdot)$ after using some optimisation algorithm (one would need to know more details to help with that).