Randomized Algorithm I asked this question earlier but I wanted to change the problem.
A band has tour sites A, B, and C. They get paid every time they play at each tour site, specifically: A: $250
B: $300
C: $200

They first play at site A then they keep randomly choosing a tour site from two sites that they did not just previously visit until they perform at all 3. What is the expected value of their payment?
My attempt at a solution is to find the expected values of how many times they visit each site. Taking for example site A, I built a binary tree and I find that at after n trips:
1 trip: 1/1 chance to visit site A once
2 trip: 1/1 chance to visit site A once
3 trips: 2/4 chance to visit site A twice
4 trips: 4/4 chance to visit site A twice 
5 trips: 2/4 chance to visit site A thrice

I think there is a chance to build a summation here but I'm not sure. Am I on the right track?
A: You could produce a table like this
Route   Probability          Pay
======  =========== =====================
ABC       1/4       1*250 + 1*300 + 1*200
ACB       1/4       1*250 + 1*300 + 1*200 
ABAC      1/8       2*250 + 1*300 + 1*200
ACAB      1/8       2*250 + 1*300 + 1*200
ABABC     1/16      2*250 + 2*300 + 1*200
ACACB     1/16      2*250 + 1*300 + 2*200
ABABAC    1/32      3*250 + 2*300 + 1*200
ACACAB    1/32      3*250 + 1*300 + 2*200
etc.

To find the expected amount, you then need to multiply the pay by the probability of each route and then add these up.  You have an infinite sum, but it is not too difficult to handle.
A: Building from the solution by Henry. Consider the two outcomes which occur with a probability of $1/2^i$ ($i$=2,3,4,...). Each involves a visit to $i+1$ venues. Venue A is visited $i/2$ times if $i$ is even and $(i+1)/2$ times if $i$ is odd. If C is the last venue to be visited then B is visited $i/2$ times if $i$ is even and $(i-1)/2$ times if $i$ is odd. Similarly, if B is the last venue visited then C is visited $i/2$ times if $i$ is even and $(i-1)/2$ times if $i$ is odd. 
Consider the payments arising from two possibilities when $i$ is odd. These are
C last: $Payment = 250(i+1)/2 + 300(i-1)/2 + 200 = 275i + 175$
B last: $Payment = 250(i+1)/2 + 200(i-1)/2 + 300 = 225i + 325$
Since the expected payment across all possibilities is simply the sum of each possibility's payment weighted by its probability and, since these two possibilities both have the same probability ($1/2^i$), it is legitimate to add them together and assign their sum a weight equal to their shared probability value. The resulting payment sum is simply $500i + 500$.
Following a similar approach when $i$ is even yields the same payment sum (i.e. $500i + 500$) across the two possibilities for the last venue.
Thus the expected payment is $$\sum_{i=2}^\infty \frac{500i + 500}{2^i} = 500\sum_{i=2}^\infty \frac{i}{2^i} + 500\sum_{i=2}^\infty \frac{1}{2^i}$$
Calculation of the two sums on the RHS is left as an exercise. The final expected value is $1000  
Note that the fact that the same payment sum ($500i + 500$) occurs irrespective of whether $i$ is even or odd is a co-incidence. It arises because the payment for venue A (250) falls midway between that of B (300) and C (200). If the payments for venues B and C did not have this symmetry about the payment for A then the payment sums would differ between the odd and even cases in terms of the constant term, which is $a + (b+c)/2$ in the odd case and $b+c$ for even, where $a,b$ and $c$ are payments for venues A, B and C, respectively. (The term involving $i$ is always $a + (b+c)/2$.) The calculation of the expected value in the asymmetric situation would be slightly different as a consequence.    
But what kind of band adopts this tour plan/business model??
