**Source:**A book on probability puzzles

**Problem:**

Suppose we play a game with a die where we roll and sum our rolls as long as we keep rolling larger values. For instance, we might roll a sequence like 1-3-4 and then roll a 2, so our sum would be 8. If we roll a 6 first, then we’re through and our sum is 6.

Three questions about this game:

(a) What is the expected value of the sum?

(b) What is the expected value of the number of rolls?

(c) If the game is played with an n-sided die, what happens to the expected number of rolls as n approaches infinity?

**Update**(Aug 31, 2011)

Solution posted by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) and Siva in comments!

What if we get say:

ReplyDelete1 1..

Will we continue or not?

a. Its 6 (=n)

ReplyDeleteb. for n its like (1+1/n)^(n-1)

c. e

Mostly used recursion.

care to enlighten us on the name of the puzzle book?

siva has already given answers for a general n-face die. for parts (b) & (c) i got slightly different answers.

ReplyDeletei post the detailed solutions

part (a):

suppose S(r) is the expected sum if u get r on first roll.

in the next roll,if we get a number <=r then we stop otherwise sequence continues. pl. note we can get 1,2,...,n all with probability 1/n.

So, S(r)= r +(1/n)*( S(r) +S(r+1)+...+S(n)).

replacing r by r+1, we get

S(r+1)=r+1+(1/n)*(S(r+1)+...+S(n)).

substracting the above two equations, we get

S(r)= (1+1/n)* S(r+1)-1.

now we know that S(n)=n.

hence on repeated application of above recurrence , S(n-1)=...=S(1)=n.

the final answer we want is then

(1/n) sigma S(i), i= 1 to n.

=n as each S(i)=n.

Part (b): Similar to above. if we let X(r) be the expected number of rolls if we get r on first roll, then

X(r)=1+(1/n)*( X(r+1)+...+X(n)).

replacing r by r+1, and substracting the two equations, we get,

X(r)=X(r+1)(1+1/n).

X(n)=1.

So, X(r)= (1+1/n)^(n-r).

our final answer will then be

(1/n) sigma X(r), r= 1 to n.

=(1+1/n)^n -1

part(c): lim n->infinity,

(1+1/n)^n -1

=e-1.

the above answer to part (c) makes me wonder if there is some mistake.

a typo mistake in part (a) of my previous post: i repost entire solution.

ReplyDeletepart (a):

suppose S(r) is the expected sum if u get r on first roll.

in the next roll,if we get a number <=r then we stop otherwise sequence continues. pl. note we can get 1,2,...,n all with probability 1/n.

So, S(r)= r +(1/n)*(S(r+1)+...+S(n)).

replacing r by r+1, we get

S(r+1)=r+1+(1/n)*(S(r+2)+...+S(n)).

substracting the above two equations, we get

S(r)= (1+1/n)* S(r+1)-1.

now we know that S(n)=n.

hence on repeated application of above recurrence , S(n-1)=...=S(1)=n.

the final answer we want is then

(1/n) sigma S(i), i= 1 to n.

=n as each S(i)=n.

Part (b): Similar to above. if we let X(r) be the expected number of rolls if we get r on first roll, then

X(r)=1+(1/n)*( X(r+1)+...+X(n)).

replacing r by r+1, and substracting the two equations, we get,

X(r)=X(r+1)(1+1/n).

X(n)=1.

So, X(r)= (1+1/n)^(n-r).

our final answer will then be

(1/n) sigma X(r), r= 1 to n.

=(1+1/n)^n -1

part(c): lim n->infinity,

(1+1/n)^n -1

=e-1.

the above answer to part (c) makes me wonder if there is some mistake.

@chera.. your solution is correct. But there is a small mistake. Answer to part c) is e and not e-1. You made a minor mistake in calculating the limit because you did not keep the brackets correct.

ReplyDeleteThanks.

@siva. Thanks for the solution. Link to probability book: http://www.madandmoonly.com/doctormatt/mathematics/dice1.pdf

@sumit.. it will not continue. the sequence has to be increasing.

@ pratik. i checked from the link u gave of book. i think, siva has made a bracketing mistake, and answers i gave r correct.

ReplyDeleteMy mistake. Yes, your solution is right.

ReplyDeleteSiva, can you please check if there is a mistake in your solution. Thanks.

@chera and @pratik, I guess the solution by @siva is right for part b) and c). I did all this in a very similar way as @chera using recursion and got expected no. of rolls as (1+1/n)^(n-1) which goes to e as n->infinity. The only mistake @chera has done is while calculating the expectation, he has missed to add 1 to the expression as we are supposed to count the first role also. In other words.

ReplyDeleteIf E(r)=Expected no of future rolls given that the last roll is r. So according to law of total expectation.

E( total no of rolls) = (1/n)Sum_{ r = 1 to n} (E(r)+1)= 1+(1/n)Sum_{ r = 1 to n } => E(r) = (1+1/n)^(n-1)