задачка (теория вероятностей)

[avva]

Вот такую задачку рассказали:

В мешке лежат n шаров, раскрашенных в n разных цветов. Вы повторяете следующую операцию: запускаете руки в мешок, достаете не глядя два шара, по одному в каждой руке, затем красите шар в правой руке в цвет шара в левой руке и кладете оба обратно. Найти математическое ожидание числа таких операций, после которого все шары будут одного цвета.

(я знаю ответ, но понятия не имею, как доказать)

Update: ссылку на доказательство дал в комментариях kdv2005, не идите по ней, если хотите решать самостоятельно.

Comments

[amarao-san.livejournal.com]

как можно покрасить шар в цвет, не посмотрев на него?

[avva.livejournal.com]

доставать не глядя, потом посмотреть и покрасить.

[deadkittten.livejournal.com]

Прпробовать свести к задаче об оценки времени сортировки?
Типа, каждая операция либо сохраняет количество цветов либо уменьшает на 1...

[lagu-na-bel.livejournal.com]

взрыв мозга

[ded_flint.livejournal.com]

два корня из двух n? :)

[ded_flint.livejournal.com]

мне кажется задачу можно решить, нарисовав диаграмму Эрланга, подход по типу задач СМО.

[avva.livejournal.com]

Как ответ может быть меньше n?

[kdv2005.livejournal.com]

http://www.math.niu.edu/~rusin/known-math/00_incoming/walk
Look for reply by Robert Israel.

[kdv2005.livejournal.com]

You may screen the reference, if you want.

[avva.livejournal.com]

Спасибо! Просто и красиво. Как всегда, аддитивность матожидания carries the day.

[avva.livejournal.com]

Ну то есть задним умом просто, я хотел сказать :)

[leonwolf.livejournal.com]

мне упорно кажется, что ответ будет (n-1)^2, но это из-за гипотезы Черны :)
на бумажке даже для n=4 не получается быстро посчитать матожидание :(

[ded_flint.livejournal.com]

я имел в виду 2*sqrt(2)*n

Реклама в блоге

[kondratic.livejournal.com]

Здравствуйте Анатолий. Хочу поговорить с Вами о рекламе в вашем блоге. Ответьте мне пожалуйста на почту katia.korop@gmail.com

woe betide, for I have forgotten all my probability theory.

[0qwerty0.livejournal.com]

using System;

namespace ballshuffle
{
class Program
{
public static void Main(string[] args)
{
int nsteps, niterations=100000, sumnsteps;
Ballset bs;
Random r = new Random(DateTime.Now.Millisecond);

for(int nballs = 1; nballs<20; nballs++) {
sumnsteps = 0;
for(int i=0;i<niterations;i++) { bs = new Ballset(nballs,r); for(nsteps = 0; !bs.arethesame(); nsteps++) { bs.draw(); } sumnsteps += nsteps; } Console.WriteLine(nballs + ": average number of draws (" + niterations +" interations): "+ (double)sumnsteps/niterations); } } } class Ballset { private int[] balls; private Random r; public Ballset(int n, Random r){ balls = new int[n]; this.r = r; for(int i=0; i<n; i++) balls[i] = i; } public void print(){ for(int i=0; i<balls.GetLength(0);i++) Console.Write(balls[i]+" "); Console.WriteLine(); } public void draw(){ int left = (int)(r.NextDouble()*balls.GetLength(0)); int right = left; while(right == left) { right = (int)(r.NextDouble()*balls.GetLength(0)); } balls[left] = balls[right]; } public bool arethesame() { for(int i=1; i<balls.GetLength(0);i++) if(balls[i]!=balls[0]) return false; return true; } } }

Re: Реклама в блоге

[braindancer.livejournal.com]

Гы.

www.naidicheloveka.ru

[iservicecorp.livejournal.com]

НайдиЧеловека.RU — единственная 100% работающая система определения местоположения абонента. Тестовый поиск выполняется совершенно бесплатно. www.naidicheloveka.ru