# Probability Analysis of a Randomized Algorithm

A rock band has three sites A, B, and C that it needs to perform at. The band performs at site A, then randomly chooses between B and C as to where it performs next. The band keeps choosing one of the two sites (not recently visited) until it performs at all three sites. What is the expected number of times the band plays at each site?

This is as much as I've done.

A = number of times performed at site A B = number of times performed at site B C = number of times performed at site C

Ai = I{ ith trip went to A } Bi = I{ ith trip went to B } Ci = I{ ith trip went to C }

Taking for example Site B:

Since there is a 1/2 chance for a site to be chosen, E[Bi] = 1/2.

E[B] = E[sum(1 to n,Bi)] = sum(1 to n, E[Bi]) = sum(1 to n, 1/2) = n/2

This means the expected number of times the band performs at site B is n/2 times.

However, this does not seem right. Can anyone offer any suggestions?

-

## migrated from mathoverflow.netFeb 26 at 5:42

This question came from our site for professional mathematicians.

It performs at A first. You may as well assume it performs at B next (else switch B and C's names). If it performs at C next, that's 3. Else it performs at A next. If it performs at C next, that's 4. Else it performs at B next. And so on. The expected value is thus $$3\times\frac12+4\times\frac14+5\times\frac18+\cdots=\sum_{n=1}^\infty\frac n{2^n}+\sum_{n=1}^\infty\frac2{2^n}=2+2=4$$

The above, my original answer, answers the expected value of the number of times the band plays in total, not per site, because I misread the question. The addition below addresses the per-site question:

I assumed the band's second stop is B. Using the probabilities above and counting visits to A, we have an expected value of $$1\times\frac12+2\times\frac14+2\times\frac18+3\times\frac1{16}+3\times\frac1{32}+\cdots=\sum_{n=2}^\infty\frac n{2^{2n-1}}+\sum_{n=1}^\infty\frac n{2^{2n-2}}\\=\frac34+\frac12=\frac54$$

The number of visits to B and to C have the same expected value by symmetry, which is thus $$\frac{4-\frac54}2=\frac{11}8$$

-
I think you answered how many times the band plays but not how many at each site. –  joshualan Feb 26 at 23:41
@joshualan, quite right: I'd misread the question. –  msh210 Feb 27 at 0:06
If you'd like to give it another go, I reimagined the question here. –  joshualan Feb 27 at 0:08
@joshualan, actually, I'm amid editing this answer. –  msh210 Feb 27 at 0:09
Could you explain the series for A? I'm also confused to why we got (4-(5/4))/2 for B and C. –  joshualan Feb 27 at 1:08
show 1 more comment