Уфф, решал когда-то эту задачу. Решение такое:
Давайте найдем матожидание интересующего Вас количества шагов (обозначим количество шагов за S, а его матожидание за E(S)).
Понятно, что с равными вероятностями (для k от 1 до n) набор перейдет в набор k, k, k, ..., k. Все эти вероятности равны 1/n. Давайте это событие обозначим через

.
Тут очень хочеться верить, что Вы знакомы с понятиями условной вероятности и условного матожидания. Если нет, напишите об этом или прочитайте, что это такое. Хотя для того, чтобы освоиться с подобными вычислениями нужно некоторое время.
1. Утверждается что наше искомое матожидание E(S) равно условному

, которое, в свою очередь, не зависит от k. (попробуйте подумать, почему это так)
2. Зафиксируем k=1 и сосчитаем

. Для этого, как писал jetyb, поставим несколько более общую задачу. Пусть в последовательности, изменяющейся по описанному Вами правилу есть m чисел "1" и, соответственно, n-m других (назовем это состояние

). Нас будут интересовать 2 объекта:
во первых

в описанных только что начальных условиях, которое мы обозначим за

,
и вероятность

(в тех же условиях), которую мы обозначим за

.
3. Из условий Вашей задачи вероятности перехода из состояния a_m равны:
в

---

в

---

в

---

4. Напишем уравнения на

:

(если первых уже нет, то они не появятся)

(если все числа --- первые, то мы достигли конечного состояния)
Из пункта 3 получаем, что при остальных m

, откуда

.
Напрашивается (верное) решение:

, то есть вероятность того, что "единички победят" равна отношению количества "единичек" к количеству всех (то есть к n). Можно было до этого догадаться и без длинных формул.
5. Перед подсчетом

сделаем еще один важный шаг: вычислим вероятности увеличения или уменьшения количества единичек (если их было m) при условии, что они все-таки победят. Обозначим их за

и

соответственно. Тогда их количество останется неизменным с вероятностью

. В этом пункте

.
Для примера

= 0: если единички победят, а сейчас их одна штука, то не может же их количество уменьшится.
Используя формулу

и сосчитанные в предыдущих двух пунктах вероятности находим

.
Аналогично

.
Отсюда

.
6. Теперь подумаем, сможем ли мы сосчитать

.

не определено, т.к. в этом случае условие (что "единички победят") заведомо ложно. Его вероятность

.

(если единички уже победили, то мат.ожидание количества ходов до победы единичек равно 0)

"то же мат.ожидание на следующем ходу"

, откуда получаем уравнение

.
Если ввести обозначение

, то получается, что интересующее нас матожидание равно

, а уравнения на

имеют вид

,

.
Осталось решить систему уравнений. То есть найти

.
7. Решим вспомагательную систему уравнений.

, где m пробегает все целые числа. Решение такой системы ---

.
8. Теперь решим чуть более сложную систему.

,

при всех m от 1 до n-1, кроме некоторого значения k и

при m=k.
Понятно, что везде, кроме m=k решение должно иметь вид, полученный в пункте 7. Подумав, находим

,

(при m=k определения согласуются).
В частности

.
9. Складывая решения из пункта 8 с коэффициентами из правой части пункта 6 находим, что нужной нам системе (той, что в п. 6) удовлетворяют

с

Если выше нет ошибки, то ответ: в среднем придется подождать

шагов.
Так при n=1 ждать придется 0 шагов (правда)
При n=2 ждать в среднем придется 3 шага. Тоже правда. На каждом шаге с вероятностью 1/3 заканчиваем, с вероятностю 2/3 продолжаем. Посчитав получаем 3. Так что можно надеятся, что ошибки действительно нет.
P.S. если придумаете, как сократить эти вычисления, напишите.