# Summation of expectation

Lets suppose we are in a casino, having two slot machines. Our strategy is to flip a coin to decide which machine to start on. (Without loss of generality, we say that we play the slot one first with probability $c_1$ and play the slot two first with probability $1-c_1$)

Then, we play on that machine until losing one game, then we switch to another slot machine to continue playing, we play a total n games (n is finite here).

Suppose the probability to win in slot one and slot two is i.i.d $Bernoulli(p_1)$ and $Bernoulli(p_2)$, respectively, and each win just gain 1 dollar, and each loss just get nothing.

Then, what should be the expected earning using this strategy???

I approached it by iteration (drawing a tree), hoping that there will be some pattern and if we find the expected winning in each turn, then we can sum the n rounds up because the trials are independent.

The expected winning in round 1 is: $$c_1\cdot p_1 + (1-c_1) \cdot p_2$$

The expected winning in round 2 is: $$c_1 \cdot[p_1^2+(1-p_1)\cdot p_2]+ (1-c_1)\cdot[p_2^2+(1-p_2)\cdot p_1]$$

The expected winning in round 3 is: $$c_1 \cdot \Big[p_1^3 + p_1(1-p_1) p_2 +(1-p_1)p_2^2 + (1-p_1)(1-p_2)p_1\Big] + (1-c_1) \Big[p_2^3 + p_2(1-p_2) \cdot p_1 + (1-p_2)p_1^2+(1-p_2)(1-p_1)p_2\Big]$$

I counted the expected winning up till round 4, which is: $$c_1 \cdot \Big[p_1^4 + p_1^2(1-p_1)p_2 + p_1(1-p_1) p_2^2 + p_1(1-p_1)(1-p_2)p_1 +(1-p_1)p_2^3 + (1-p_1)p_2(1-p_2)p_1 + (1-p_1)(1-p_2)p_1^2 + (1-p_1)^2(1-p_2)p_2\Big]$$ $$+ (1-c_1) \cdot \Big[p_2^4 + p_2^2(1-p_2)p_1 + p_2(1-p_2) p_1^2 + p_2(1-p_2)(1-p_1)p_2 +(1-p_2)p_1^3 + (1-p_2)p_1(1-p_1)p_2 + (1-p_2)(1-p_1)p_2^2 + (1-p_2)^2(1-p_1)p_1\Big]$$

This calculation seems endless so it does not work well. How could I find the expected winning in this case?

• Oh it is the former, n is the number of times I pull a slot machine's lever~~ We switch only if we lose one game – son520804 Dec 5 '17 at 20:54
• Let $X_1$ be the number of winning pulls on machine 1 before a losing pull. So $X_1 - 1$ is your payoff if you were to play machine 1. What is the expectation of $X_1$? And do any of these formulas for sums of a series help you compute the expectation of $X_1$? – Matthew Gunn Dec 5 '17 at 22:36
• I could not easily compute the number of winning on each slot. We choose to play at slot 1 first by probability $c_1$ and play at slot 2 first by probability $c_2$. Then we play at the slot continuously, until lose 1 game and then play the another slot. (And the slot 1 and slot 2 each has winning probability $p_1$ and $p_2$) – son520804 Dec 5 '17 at 22:42

Consider $d$ machines numbered $1,2,\ldots, d$, each with chance $p(d)$ of winning. Let's find the expectation of beginning with machine $1$, playing until a loss, proceeding to machine $2$, etc, and cycling around from machine $d$ to machine $1$ if necessary until $n$ games have been played. The question concerns the case $d=2$, but the analysis (and computation) isn't any harder for larger $d$.

Let $e_j(k)$ denote the expected winnings from playing $k$ games beginning with machine $j$. Because each game is either a win (gaining $1$ dollar) with probability $p(j)$ or a loss with probability $1-p(j)$, leaving $k-1$ games to go, the rules of conditional expectation imply

$$e_j(k) = p(j)(e_j(k-1) + 1) + (1-p(j))(e_{(j \operatorname{mod} d)+1}(k-1))$$

when $k \ge 1$ and otherwise $e_j(k)=0$.

This is a simple dynamic program requiring $O(dn)$ computational effort and $O(dn)$ storage: in other words, it's a quick easy computation. You can even do it by hand.

As an example, here is an R implementation. The argument p is an array of probabilities $p(j)$. It returns a $d\times n+1$ array indexed by machine and number of games (from $0$ through $n$).

expectation <- function(p, n=10) {
d <- length(p)
P <- matrix(0, d, n+1, dimnames=list(Machine=names(p), Plays=0:n))
if (n > 0)
for (i in 1:n) {
for (j in 1:d) {
P[j, i+1] <- p[j] * (P[j, i] + 1) + (1-p[j]) * P[j%%d + 1, i]
}
}
return(P)
}


Given an initial probability distribution $c(1), c(2),\ldots, c(d)$ for the choice of which machine to start with, the rules of conditional expectation state that the expected winnings will be the sum of $c(j)e_j(n)$. This answers the question.

Intuitively, machines that tend to fail will rarely be operated and those that tend to win are allowed to run. The $e_j(n)$ therefore will rapidly tend to a common value approximately equal to the $p$-weighted average of the $e_j(n)$ as $n$ grows, and the differences among the $e_j(n)$ will be no greater than the differences among the raw probabilities $p(j)$. Here are some examples for $d=2$.

The panel headings list the probabilities for machine "a" and machine "b" in order.

It's always good to check probability calculations. I carried out simulations as shown in this R program:

p <- c(a=0.5, b=0.2)
set.seed(17) # Comment this out when repeating simulations!
sim <- replicate(1e4, n - sum(cumsum(rgeom(n, 1-p) + 1) <= n))


It exploits the fact that the number of wins obtained from a machine has a geometric distribution, allowing the simulation to proceed fairly quickly. (The computation actually amounts to counting how many machines were tried in turn, rather than counting the wins directly.)

The output is an array of winnings, one for each iteration of the scenario. Because this dataset is large and not too skewed, we may compare its mean to the theoretical calculation using a Z-test.

m <- mean(sim)
s <- sd(sim)
mu <- expectation(p, n)[1,n+1]
c(Simulation=m, Calculation=mu, Z=(m - mu)/s * sqrt(length(sim)))


The output in this (reproducible) case is

 Simulation Calculation           Z
3.950       3.930       0.889


It says the average among the (10,000) simulations was 3.95, the calculation of the expectation came out to 3.93, and the Z-score is 0.889 (which is not a significant difference). Repeated simulations for different $p$ and $n$ continue to agree with the calculations, providing assurance the calculations are correct.