0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Also, 'for n large enough' I can give you some hints/answer right now, if you want. By the way, do you need an analytical solution, or can the answer be reduced to an equation, whose solution you can find numerically? $\endgroup$ – Aahz Aug 27 '14 at 12:10
  • $\begingroup$ Any solution would be appreciated. Thank you! $\endgroup$ – Bardo Aug 27 '14 at 14:42
  • $\begingroup$ Sure thing. You should edit your question then, to reflect you do not only seek the meaning of the expected value, but also a way to solve the problem. I'll edit my answer shortly. $\endgroup$ – Aahz Aug 27 '14 at 15:24
  • $\begingroup$ Thank you!!! Would you mind taking a look there: math.stackexchange.com/questions/911050/… . I have posted another question that hopefully will help me understand this concept. Thank you again for your time!! I really appreciate it! $\endgroup$ – Bardo Aug 27 '14 at 15:41
  • $\begingroup$ May I suggest you edit your question to broaden it (i.e. you ask not only the meaning of expectation, but also solution). Also, plaese insert some more LaTeX editing in the body of the question. Thanks. $\endgroup$ – Aahz Aug 27 '14 at 16:15
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer! So, basicaly E(T), this expected value is actually a probability, right? $\endgroup$ – Bardo Aug 27 '14 at 14:41
  • $\begingroup$ No, E(T) is not a probability. T is a random variable, and E(T) is the Expected value. $\endgroup$ – Aahz Aug 27 '14 at 15:05
  • $\begingroup$ Added my solutions. $\endgroup$ – Aahz Aug 27 '14 at 16:12
  • $\begingroup$ A very complete answer. I now understand. I got even the second part. One small question though: for keeping notations..in your first solution, that n's shouldn't be capital n's ? $\endgroup$ – Bardo Aug 27 '14 at 20:00
  • $\begingroup$ Yes. Edited. Also, T and $\tau$ are the same. $\endgroup$ – Aahz Aug 28 '14 at 4:27
1
$\begingroup$

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..

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In your first equation, did you mean $q$ instead of $p$? $\endgroup$ – Aahz Aug 28 '14 at 15:19
  • $\begingroup$ Indeed. It was a typo. Sorry about that. So..what do you think? $\endgroup$ – Bardo Aug 28 '14 at 16:11
  • 1
    $\begingroup$ I'll be honest, the way you formulated it is little unclear. I do think that's you've got the idea correctly, because your final recursive formula seems to be correct, so good job! Also, I should note that when you say that the expectation is the average for a large sample of results, this it is true in general in many, many cases. It is called the Law of Large Numbers. $\endgroup$ – Aahz Aug 28 '14 at 17:25
  • $\begingroup$ Thank you for your feedback! But could you please tell me what seems unclear? Because I really want to reformulate it if needed. $\endgroup$ – Bardo Aug 28 '14 at 18:28
  • $\begingroup$ Due to my English I have probably not written my arguments in a very good way. What I'm interested in is...have I applied the formula for the expected value in a correct way? Have I found the correct "x's" and "p's" ? $\endgroup$ – Bardo Aug 28 '14 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.