By the symmetry of the operation, if the probability that black ball is at the leftmost position is \(p\), then that of being each of the other positions is \(\displaystyle \frac{1 - p}{N - 1}\). Thus, one can solve the problem by finding the probability that \(K\) operations make the leftmost ball black. This can be computed with Dynamic Programming (DP). Define

• \(\mathrm{dp}[i] := \) Probability that \(i\) operations make the leftmost ball black.

What we want is \(\mathrm{dp}[K]\). The transition requires the following two probabilities:

• the probability that an operation moves the leftmost black ball to somewhere else
• the probability that an operations moves the black ball elsewhere to the leftmost position

Denoting them by \(p, q\), the transitions are as follows:

• \(\mathrm{dp}[0] = 1\)
• \( \mathrm{dp}[i+1] = (1 - p) \mathrm{dp}[i] + q(1 - \mathrm{dp}[i])\)

By simple combinatorics, \(p\) and \(q\) is represented as

• \(\displaystyle p = \frac{2(n - 1)}{n^2}\)
• \(\displaystyle q = \frac{2}{n^2}\).

Implementing it naively yields \(\mathcal{O}(K)\) solution, but it is boiled down to a first-order recurrence relation, whose general term can be represented simply (a typical high-school math problem). Thus, \(\mathrm{dp}[K]\) can be found in \(\mathcal{O}(\log K)\) time, where computing power is the bottleneck.

Sample code (C++)

More generally, there are algorithms that find the \(N\)-th term of a linear recurrence relation such as matrix powering algorithm and Fiduccia’s algorithm.