Meaning of 'expected value' in the following problem

Question

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement:

"What is the expected number of dice throws needed to attain a value of at least n (candies, in this problem)?"

So, the problem asks us to find the expected number of throws to obtain at least N candies. I'm not sure I get the meaning of 'expected value'. Thisi is some sort of average value needed to obtain at least N candies. So if I have K ways of obtaining at least N candies, and each way consist of a_i throws, then the expected value, would be:

E = ( a_1 + a_2 + ... + a_k )/k ?

But how do i find these ways? Because...as far as I'm cocerned, I would need to take into account an infinite number of values, because, if I need to obtain at least 10 candies, then obtaining 1000000 candies is indeed a valid method. So, could somebody give me a clearer picture of the concept of 'expected value', as it is used here, in this problem, and perhaps explain me why my reasoning is wrong?

Another thing...wouldn't it be use ful to know c[i][j], the probability of obtaining exactly i candies using j throws?

c[i][0] = 1, if i <= 0;

And then, if I know how to obtain, say, c[i-1][j-1] candies, then if I throw the dice now and I get a 1, I can obtain i candies. The probability of getting a 2 is 1/6. So, with a little reasoning and basic probabilty knowledge, we have:

c[i][j] = 1/6 ( c[i-1][j-1] + c[i-2][j-2] + c[i-3][j-3] + c[i-4][j-4] + c[i-5][j-5] + c[i-6][j-6] ), right ??

The answer of this problem is:

Res[n] = 1 + Res[n-1]/6 + Res[n-2]/6 + Res[n-3]/6 + Res[n-4]/6 + Res[n-5]/6 + Res[n-6]/6

Where Res[n] is the expected number of throws needed to obtain at least a value of n.

It is indeed clear for me that Res[n] = 1, and, for the purpose of easily implement this reccursion in a programming language, Res[n] = 0, n <= 0.

So, what eaxctly is meant here when 'the expected value' it's used?

Edit: Here are the examples the problem gives

n = 1, answer 1.0 n = 2, answer 1.1666666666666667 n = 7, answer 2.5216263717421126 n = 47, answer 13.90476189046144

Answer 1

For $N$ the expected value is the expected value until first seeing a number $\geq N$. For instance, for $N = 10$ and dice results $4,5,3,5,3,...$ the answer would be $3$, because $4+5 < 10,\text{ and } 4+5+3>10$, and for $5,6,3,2,1...$ it would be $2$. The bound on the expected value from above would be 10 (all 1's) and from above would be 2( you can't get 10 in fewer than two throws).

More formally, let $x_i$ be your dice results, and $S_n = x_1 + ... + x_n$. Then the expected number is $E(\tau)$, where $\tau = \min\{n|S_{n-1}<N, ~ S_n>=N\}$.

For example, for $N = 2$, $\tau$ is either 1 w.p. $\frac56$ (first die is in$\{2,...,6\}$) or it is $2$ w.p. $\frac16$ (first die is $1$, and then any other result brings you above $N=2$). So $E(\tau) = 1 \times \frac 56 + 2 \times \frac16 = 1.16161616$

---

For the second part of your question, here are two attempts to solve the problem itself, one for smaller numbers of $N$, the other for larger, and uses asymptotic.

---

For small numbers of $N$:

Denote $e_i$ the expected value of turns to get from $i$ to one of the states $\{N,N+1,...,N+5 \}$. Since we use a six-sided die, we will necessarily reach one of these, and will stop there.

Then we can write the following relations: $$e_0 = 1 + \frac 16 e_1 + \frac 16 e_2 + ... + \frac 16 e_6$$ $$e_1 = 1 + \frac 16 e_2 + \frac 16 e_3 + ... + \frac 16 e_7$$ $$...$$ $$e_{N-7} = 1 + \frac 16 e_{N-6} + \frac 16 e_{N-5} + ... + \frac 16 e_{N-1}$$ $$e_{N-6} = 1 + \frac 16 e_{N-5} + \frac 16 e_{N-4} + ... + \frac 16 e_{N-1} + \frac 16 0$$ $$e_{N-5} = 1 + \frac 16 e_{N-4} + \frac 16 e_{N-3} + ... + \frac 16 e_{N-1} + \frac 16 0 + \frac 16 0$$ $$...$$ $$e_{N-1} = 1$$

These is simply a system of linear equations that you can solve numerically.

An explanation on the (say) first equation. You start out at $0$. To get to the end set $\{N,...,N+5\}$ you need to make one step (that the $+1$ at the beginning), at which point w.p. 1/6 you end up on $1$, and will need further $e_1$ steps ("on average". Hence the expectation.) And so forth.

---

For large values of $N$:

The process $S_n = \sum_1^n x_i$, where $x_i$ are the results of the die, is a Markov Chain.

Our process ends at one of the states $\{N,...,N+5\}$.

For large values of $N$, we can use the theory of Markov Chains, and prove that the process will end on the state $N+i$ with probability $\pi_0 = \frac1{3.5}$ for $i = 0$, and $\pi_i = \frac{6-i}{6} \pi_0$. I am not presenting here the proof currently, to not overcomplicate things. If asked for, I could present it (though possibly it would be better to open another question for that.)

Then, we can invoke a version of the Wald's Equation. For a stopping time $\tau$ (which is well defined in our case, and is definitely finite), we write: $$E(S_{\tau}) = E(x)E(\tau)$$ ($S$ is the sum of $x_i$, $x$ is an individual die cast).

We wish to solve for $E(\tau) = \frac{E(S_{\tau})}{E(x)}$. $E(x)$ = $3.5$. From the probabilities above, $$E(S_{\tau}) = N \pi_0 + (N+1) \pi_1 + ... + (N+5) \pi_5 = ... = N + \frac53$$

So finally, we get the answer $E(\tau) = \frac{N+\frac53}{3.5}$. Is it good? Let's substitute $N = 47$ from the question. We get $13.9047619$. Hooray! It matches!

For $N = 7$ we get $2.4761$, which is not the number in your question, but is rather close, and is not bad for such a small value of $N$.

Answer 2

Is it a correct approach if I think of it like this? $f(n)$ is the number of throws to obtain a value of at least n. So my experiment is throwing the dice until I get a value of at least $n$. Every time I get a value $\geq n$ I note the number of throws I needed. Let's say I have done the experiment $q$ times, with q being a very large number, and that in the ith throw I registred $t_i$ thrwos (so every time I registred a different possible value for $f(n)$). Then, the meaning of $E(f(n))$ is:

$$ E(f(n)) = \frac{t_1+t_2+...+t_p}{q} $$

Is that correct? I believe that intepretation is a good one.

Now, following the deffinition from wikipedia: "Suppose random variable X can take value x1 with probability p1, value x2 with probability p2, and so on, up to value xk with probability pk. Then the expectation of this random variable X is defined as:"

$$ E[x] = x_1*p_1 + x_2*p_2 + ... + x_n*p_n $$

Now I'm gonna show how this formula is applied in our problem. Well, the first obvious question anyone that has diffculties understanding how this formula is applied will ask is 'who is X?'. Well in our case the random variable that can take different values is $f(n)$.

The next question is: 'what values can it take? (who are those x1,x2,x3..?)'. Beware, because we are going to use reccursion!! Well I can obtain a total of at least $n$ points by:

1) obtaining a total of at least n-1 points and thrwoing 1 on the current throw. 
2) obtaining a total of at least n-2 points and thrwoing 2 on the current throw.
3) obtaining a total of at least n-3 points and thrwoing 3 on the current throw.
4) obtaining a total of at least n-4 points and thrwoing 4 on the current throw.
5) obtaining a total of at least n-5 points and thrwoing 5 on the current throw.
6) obtaining a total of at least n-6 points and thrwoing 6 on the current throw.

There are not any other posiblities to hit at least $n$ at the current throw since the maximum value I can obtain by rolling a dice is 6!

Now, to compute the effective valuse of that x's. if I throw a 1 on the current throw then the value of $x_1$ will be the expected numbers of hitting n-1, that is $E(f(n-1))$ plus the current throw: $$ x_1 = E(f(n-1))+1$$ With a similar thinking it immediately follwos that: $$ x_2 = E(f(n-2))+1$$ $$ x_3 = E(f(n-3))+1$$ $$ x_4 = E(f(n-4))+1$$ $$ x_5 = E(f(n-5))+1$$ $$ x_6 = E(f(n-6))+1$$

The next question is 'who are those p's(those p1,p2,p3)'. This is a little bit easier to answer and I'm only going to show the argument for p1, since for the other valuse it goes exactly the same way, and in fact we ar going to obtain the same value for p1,p2,p3,p4,p5,p6.

We are asking ourselves: "what is the probability that my random variable f(n), takes the value $x_1$, that is: what is p_1?" Well my random variable f(n) (I'm reapeating this to emphasize the meaning of f(n) in our wikipedia formula) can take the value $x_1$ found above if and only if I hit a 1 on this roll. The probability of hitting a 1 on this role is $\frac{1}{6}$ so $p_1 = \frac{1}{6}$. Not it shoudl be clear why $ p_1=p_2=p_3=p_4=p_5=p_6 = \frac{1}{6}$.

And finally the last step, is putting the pieces head to head and obtaining our final formula:

$$E(f(n)) = x_1p_1 + x_2p_2 + x_3p_3 + x_4p_4 + x_5p_5 + x_6p_6 $$ $E(f(n)) = [ E(f(n-1))+1 ]\frac{1}{6} + [ E(f(n-2))+1 ]\frac{1}{6} + [ E(f(n-3))+1 ]\frac{1}{6} + [ E(f(n-4))+1 ]\frac{1}{6} + [ E(f(n-5))+1 ]\frac{1}{6} + [ E(f(n-6))+1 ]\frac{1}{6} $

Now, by some very very easy algebra we end up with a somehow nicer form:

$E(f(n)) = E(f(n-1))\frac{1}{6} + E(f(n-2))\frac{1}{6} +E(f(n-3))\frac{1}{6} + E(f(n-4))\frac{1}{6} +E(f(n-5))\frac{1}{6} + E(f(n-6))\frac{1}{6} + 1 $

This formula is rigurously typed but for the purpose of implementing it in a programming langugage we can replace that f(...) with simply ...:

$E(n) = E(n-1)\frac{1}{6} + E(n-2)\frac{1}{6} +E(n-3)\frac{1}{6} + E(n-4)\frac{1}{6} +E(n-5)\frac{1}{6} + E(n-6)\frac{1}{6} + 1 $

I should have mentioned this earlier, but I'm doing it now. Of course that every reccurence needs some base case that assures the fact that the reccurence can be calculated, that is when we need some already calculated values we have them. And so, for this purpose, we make the observastion that E(n) = 1, since I get a value of at least 1 by only throwing a single dice!!! So, we define $$E(1) = 1, E(k) = 0,k \leq 0$$. I believe it is clear why.

Now I have come across this explanation by some thinking...I have used some of yours ideas of which I am now perfectly sure that they are correct, that is I have understood the problem. This discussion that I had with you and the other one on the other question mentioned in one of my comments helped me to achieve something..

I have chosen to write this explanation because it involes a little less math, and because probably somebody will be as lost as I was in understanding a similar problem and maybe this, along with your very detalied mathematical analysis will help him understand..