[Prime]

With recent surge of probability problems, I think this one is due.

Prove (mathematically) that it takes on average six rolls of a single die to roll "6".

This math may be useful in solving probability problems like the recent one with dice.

[Guest]

With recent surge of probability problems, I think this one is due.

Prove (mathematically) that it takes on average six rolls of a single die to roll "6".

This math may be useful in solving probability problems like the recent one with dice.

1 = (chance to roll a 6)^(number of rolls)

1 = (1/6)^n

Solving

n = 6

[Yoruichi-san]

Okay, the expectation value of the number of rolls given by sum[n*p(n)] where n is the number of rolls and p(n) is the probability of getting the first 6 on the nth roll exactly.

For the nth roll, the probability of getting the 6 on that roll exactly should be: (probability of getting 6)*(probability of not getting 6 on any previous rolls)

The probability of not getting a six on previous rolls is (5/6)^(n-1) and the probability of getting a 6 is (1/6).

So this gives us a geometric series: E<x> = 1*(1/6)+2*(1/6)*(5/6)+3*(1/6)(5/6)^2...+n*(1/6)(5/6)^(n-1)

or simply E<x> = 1/6*sum[n*(5/6)^(n-1)]

[Guest]

1 = (chance to roll a 6)^(number of rolls)

1 = (1/6)^n

Solving

n = 6

Should be

1 = (chance to roll a 6)*(number of rolls)

1 = (1/6)*n

Solving

n = 6

[Guest]

With recent surge of probability problems, I think this one is due.

Prove (mathematically) that it takes on average six rolls of a single die to roll "6".

This math may be useful in solving probability problems like the recent one with dice.

Sorry but I am confused. Do you mean average 6 rolls for a signle die to roll "6" continuously for 6 rolls, or at least 1 "6" appear?

[Yoruichi-san]

Okay, the expectation value of the number of rolls given by sum[n*p(n)] where n is the number of rolls and p(n) is the probability of getting the first 6 on the nth roll exactly.

For the nth roll, the probability of getting the 6 on that roll exactly should be: (probability of getting 6)*(probability of not getting 6 on any previous rolls)

The probability of not getting a six on previous rolls is (5/6)^(n-1) and the probability of getting a 6 is (1/6).

So this gives us a geometric series: E<x> = 1*(1/6)+2*(1/6)*(5/6)+3*(1/6)(5/6)^2...+n*(1/6)(5/6)^(n-1)

or simply E<x> = 1/6*sum[n*(5/6)^(n-1)]

Okay, I'm rusty on series, but Mathematica confirms...

sum[n*(5/6)^(n-1)] {from n=1 to infinity} = 36

So E<x> = 1/6 *36 = 6

I know there's some Theorem or elegant way of evaluating the convergence of the series, but I forget...

[Yoruichi-san]

Oh, and the generalized form for any p:

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity}

Hmmm...this looks like a derivative...maybe that's how to find the solution to the series...

But I guess the point of applying this to the problem linked to in the OP is proving:

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity} = 1/p

[Prime]

Okay, the expectation value of the number of rolls given by sum[n*p(n)] where n is the number of rolls and p(n) is the probability of getting the first 6 on the nth roll exactly.

For the nth roll, the probability of getting the 6 on that roll exactly should be: (probability of getting 6)*(probability of not getting 6 on any previous rolls)

The probability of not getting a six on previous rolls is (5/6)^(n-1) and the probability of getting a 6 is (1/6).

So this gives us a geometric series: E<x> = 1*(1/6)+2*(1/6)*(5/6)+3*(1/6)(5/6)^2...+n*(1/6)(5/6)^(n-1)

or simply E<x> = 1/6*sum[n*(5/6)^(n-1)]

That's basically the proof. However, a bit more work is required to wrap it up. The series is not a geometric progression. (There is no common ratio between the members of the sequence.) How do you calculate the sum E(n*(5/6)^(n-1)), where n tends to infinity? With a little effort such math problems may be solved without using any books/reference. That in itself could be rewarding.

[Prime]

Sorry but I am confused. Do you mean average 6 rolls for a signle die to roll "6" continuously for 6 rolls, or at least 1 "6" appear?

Roll the die repeatedly until "6" comes up. Count the number of rolls. I hypothesized, on average, you'd roll the die 6 times. Sometimes, "6" comes up on the first roll, other time it may come up only after 15 rolls, but the average is going to be 6 rolls.

[Yoruichi-san]

Oh, and the generalized form for any p:

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity}

Hmmm...this looks like a derivative...maybe that's how to find the solution to the series...

But I guess the point of applying this to the problem linked to in the OP is proving:

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity} = 1/p

Aha! I figured out how to do the series:

So the proof for a geometric series: sum[r^(n-1)] {n=1 to infinity} = 1/(1-r) is:

Denote the series by Sg

Sg = 1+r+r^2+r^3+...r^(n-1)

r*Sg = r+r^2+r^3+r^4+...r^n

Subtracting the two cancels out most of the terms:

Sg-r*Sg = 1-r^n

Since Sg-r*Sg=(1-r)*Sg, we divide both sides by (1-r)

Sg = (1-r^n)/(1-r)

Letting n->infinity, Sg{n=1 to infinity} = 1/(1-r)

So for this problem, we weight each term by its index Sn=sum[nr^(n-1)], so

Sn = 1+2r+3r^2+4r^3+...nr^(n-1)

r*Sn= r+2r^2+3r^3+4r^4+...r^n

Again, subtracting, we get the geometric series:

Sn-r*Sn = 1+(3-2)r^2+(4-3)r^3+(5-4)r^4+...(n-(n-1))r^(n-1) = 1+r+r^2+r^3+r^4...r^(n-1) = Sg = (1-r^n)/(1-r)

Again, dividing by (1-r), we get:

Sn = (1-r^n)/(1-r)^2

Again, letting n-> infinity, Sn {n=1 to infinity} = 1/(1-r)^2

Applying this result to the problem:

r=(1-p)

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity} = p*Sn{from n=1 to infinity} = p*(1/(1-r)^2) = p*(1/(1-(1-p))^2) =p*(1/p^2) = 1/p

Voila! So the expected value of the number of events for an outcome with probability p to happen is 1/p

Edit: Oh, you posted this while I was writing it up...

That's basically the proof. However, a bit more work is required to wrap it up. The series is not a geometric progression. (There is no common ratio between the members of the sequence.) How do you calculate the sum E(n*(5/6)^(n-1)), where n tends to infinity? With a little effort such math problems may be solved without using any books/reference. That in itself could be rewarding.

See above ;P

Edited September 26, 2008 by Yoruichi-san

[Prime]

Oh, and the generalized form for any p:

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity}

Hmmm...this looks like a derivative...maybe that's how to find the solution to the series...

But I guess the point of applying this to the problem linked to in the OP is proving:

E<x> = p*sum[n*(1-p)^(n-1)] {from n=1 to infinity} = 1/p

So how do you arrive to 1/p?

I believe, it is basic math. No books/reference are needed. If you need formula for Geometric series, I can provide. Although, I never remember it myself and have to derive it every time I need it.

The sum of Geometric progresssion (Geometric Series) is G_n = a(1 - rⁿ)/(1 -r)

Here is how to derive it:

In Geometric sequence each next member is obtained by multiplying its predecessor by a common ratio "r". The first member "a" is called scale factor.

(1) Thus Geometric series: G_n = a + ar¹ + ar² + ar³ + ... + ar^n-1

(Series could be infinite too).

(2) Thus, G_n+1 = G_n + arⁿ

(3) On the other hand, G_n+1 = a + r(ar¹ + ar² + ar³ + ... + ar^n-1) = a + rG_n

Therefore, from (2) and (3): G_n + arⁿ = a + rG_n

Solving for G_n we find: G_n = a(1 - rⁿ)/(1 -r)

Note, if r < 1, the sum of infinite sequence can be a finite number, since rⁿ = 0 when n tends to infinity.

[Yoruichi-san]

So how do you arrive to 1/p?

I believe, it is basic math. No books/reference are needed. If you need formula for Geometric series, I can provide. Although, I never remember it myself and have to derive it every time I need it.

The sum of Geometric progresssion (Geometric Series) is G_n = a(1 - rⁿ)/(1 -r)

Here is how to derive it:

In Geometric sequence each next member is obtained by multiplying its predecessor by a common ratio "r". The first member "a" is called scale factor.

(1) Thus Geometric series: G_n = a + ar¹ + ar² + ar³ + ... + ar^n-1

(Series could be infinite too).

(2) Thus, G_n+1 = G_n + arⁿ

(3) On the other hand, G_n+1 = a + r(ar¹ + ar² + ar³ + ... + ar^n-1) = a + rG_n

Therefore, from (2) and (3): G_n + arⁿ = a + rG_n

Solving for G_n we find: G_n = a(1 - rⁿ)/(1 -r)

Note, if r < 1, the sum of infinite sequence can be a finite number, since rⁿ = 0 when n tends to infinity.

Err...I think you missed my last post...

...oh, and there is a typo in my last post, it should be (n)r^(n), not r^n on that last series...

[Yoruichi-san]

Err...I think you missed my last post...

...oh, and there is a typo in my last post, it should be (n)r^(n), not r^n on that last series...

Oh, yeah, also I forgot to put in the stipulation: 0<r<1 (for the n->infinity part, so that r^n -> 0)

[Prime]

Err...I think you missed my last post...

I was typing my posts while watching TV and got a bit slow. I missed few of your posts.

Yoruichi-san gets full marks for the solution! That's an honest mathematical proof.

I'll re-write with comments and organize it a little here:

An average is a sum of the value/weight of each individual entity/event times its probability divided by collective probability, which is in case of exhaustive collection is 1.

Let’s say probability of an individual event (such as rolling "6") is p. Then probability of the event not occurring is q = 1 - p. For example, the probability to roll "6" exactly on the 4th roll is pq³ – that is the probability not to roll "6" 3 times in the row times probability to roll "6" on the 4th attempt.

The average number of rolls to get "6" is the sum:

(1) S = p + 2pq + 3pq² + 4pq³ + … and so on to infinity. (Note, each term is multiplied by its weight – the number of rolls.)

The above sum is not a geometric series, each consecutive term is not obtained from predecessor by multiplying by a common factor.

A geometric series would be:

(2) G = p + pq + pq² + pq³ + …

We know, the formula for this Geometric series is p(1-qⁿ)/(1-q) and with n tending to infinity and q<1, that exp​ression becomes G = p/(1-q)

Let's subtract exp​ression (2) from (1):

S = p + 2pq + 3pq² + 4pq³ + …

-

G = p + pq + pq² + pq³ + …

______________________________________________

S - G = pq + 2pq² + 3pq³ + …

Making further transformations: S - G = q(p + 2pq + 3pq² + 4pq³ + …)

Or S - G = qS. Solving for S: S = G/(1-q).

Now substituting the sum of geometric series G = p/(1-q) (found earlier) and 1-q = p (as defined in the beginning) we get S = 1/p.

Thus the average number of trials for an event with probability of p is 1/p.

[Yoruichi-san]

I was typing my posts while watching TV and got a bit slow. I missed few of your posts.

Yoruichi-san gets full marks for the solution! That's an honest mathematical proof.

I'll re-write with comments and organize it a little here:

An average is a sum of the value/weight of each individual entity/event times its probability divided by collective probability, which is in case of exhaustive collection is 1.

Let’s say probability of an individual event (such as rolling "6") is p. Then probability of the event not occurring is q = 1 - p. For example, the probability to roll "6" exactly on the 4th roll is pq³ – that is the probability not to roll "6" 3 times in the row times probability to roll "6" on the 4th attempt.

The average number of rolls to get "6" is the sum:

(1) S = p + 2pq + 3pq² + 4pq³ + … and so on to infinity. (Note, each term is multiplied by its weight – the number of rolls.)

The above sum is not a geometric series, each consecutive term is not obtained from predecessor by multiplying by a common factor.

A geometric series would be:

(2) G = p + pq + pq² + pq³ + …

We know, the formula for this Geometric series is p(1-qⁿ)/(1-q) and with n tending to infinity and q<1, that exp​ression becomes G = p/(1-q)

Let's subtract exp​ression (2) from (1):

S = p + 2pq + 3pq² + 4pq³ + …

-

G = p + pq + pq² + pq³ + …

______________________________________________

S - G = pq + 2pq² + 3pq³ + …

Making further transformations: S - G = q(p + 2pq + 3pq² + 4pq³ + …)

Or S - G = qS. Solving for S: S = G/(1-q).

Now substituting the sum of geometric series G = p/(1-q) (found earlier) and 1-q = p (as defined in the beginning) we get S = 1/p.

Thus the average number of trials for an event with probability of p is 1/p.

Lol...thanks...what's on on Thursdays...Lost?

And thanks for posting the complete solution for everyone else to understand, lol...I'm always bad at making things readable to others (I pity the TAs who had to grade my problem sets...XP)...I'm always like "as long as it makes sense in my head"...;P

[bonanova]

With recent surge of probability problems, I think this one is due.

Prove (mathematically) that it takes on average six rolls of a single die to roll "6".

This math may be useful in solving probability problems like the recent one with dice.

Wondering what all these infinite series are about ...

After 6 rolls of the die, 6 numbers will appear.

The average number of appearances of the numbers 1-6 is the same [for a fair die] and they total 6.

If 6 quantities are equal and total 6, each of them equals 1. <_<

[bonanova]

Corollary:

If the probability of achieving result R in one trial is p,

the average number of trials necessary [expectation value] to achieve R is 1/p.

By analogy.

A man is walking on a road to the city named Result.

After one day he achieves 1/5 of his objective.

What is the expected number of days walking required for him to arrive at Result?

That would be 1/(1/5) = 5 days.

If 1 trial achieves a fraction p of the desired result,

on average, 1/p trials are required to achieve the result.

If 1 roll of the die produces a 6 with a probability 1/6, then expect 6 rolls to produce a 6.

[Yoruichi-san]

Corollary:

If the probability of achieving result R in one trial is p,

the average number of trials necessary [expectation value] to achieve R is 1/p.

By analogy.

A man is walking on a road to the city named Result.

After one day he achieves 1/5 of his objective.

What is the expected number of days walking required for him to arrive at Result?

That would be 1/(1/5) = 5 days.

If 1 trial achieves a fraction p of the desired result,

on average, 1/p trials are required to achieve the result.

If 1 roll of the die produces a 6 with a probability 1/6, then expect 6 rolls to produce a 6.

I'm sorry, it's an interesting way of looking at it, but I don't really think the analogy works for me, because the dice rolls are independent variables, whereas achieving part of a result is not. If I try to look at the days as independent, the man walks 1/5 of the total distance on day 1, then the next day the distance he walks is actually 1/4*4/5=1/4 of his remaining distance, i.e. on day 2 he achieves 1/4 his objective (looking at the days as independent). Whereas if I roll the dice one time, the probability of getting a 6 is 1/6 and if I roll the dice a second time the probability of getting a 6 is still 1/6 and on the 100th roll the probability of getting a 6 is still 1/6.

Also, the walk is deterministic, not probabilistic, i.e. after 5 days he will have gotten to the end, no matter what (unless he gets eaten by a large jungle cat), but after 6 rolls, the probability of getting a 6 is not 1, it is 1-prob(no 6s)=1-(5/6)^6.

[bonanova]

I'm sorry, it's an interesting way of looking at it, but I don't really think the analogy works for me, because the dice rolls are independent variables, whereas achieving part of a result is not. If I try to look at the days as independent, the man walks 1/5 of the total distance on day 1, then the next day the distance he walks is actually 1/4*4/5=1/4 of his remaining distance, i.e. on day 2 he achieves 1/4 his objective (looking at the days as independent). Whereas if I roll the dice one time, the probability of getting a 6 is 1/6 and if I roll the dice a second time the probability of getting a 6 is still 1/6 and on the 100th roll the probability of getting a 6 is still 1/6.

Also, the walk is deterministic, not probabilistic, i.e. after 5 days he will have gotten to the end, no matter what (unless he gets eaten by a large jungle cat), but after 6 rolls, the probability of getting a 6 is not 1, it is 1-prob(no 6s)=1-(5/6)^6.

Analogies are only suggestive, to guide thinking.

By achieving 1/5 of his objective we mean travel 1/5 of the distance from start to finish, not 1/5 of the remaining distance.

We can take away the determinism by saying the man had walked to the city a large number of times in the past and on average it took him 5 days to arrive.

If a day were 8 hours of walking, and on different days the man was well rested or not, or the weather was conducive or not to travel, then each time he made the trip his arrival time would be different from 40 hours although 40 hours was his average result.

Then it is valid to assert that, on average, a day's travel achieved 1/5 of the total distance. You get what I mean.

And then the equivalence of that statement with the statement that on average it takes him 1/(1/5) = 5 days is clear.

However, the first argument is a rigorous proof, not that the infinite series isn't, and is simpler.

Six trials, six equally likely results.

On average, one result each.

[Prime]

Wondering what all these infinite series are about ...

After 6 rolls of the die, 6 numbers will appear.

The average number of appearances of the numbers 1-6 is the same [for a fair die] and they total 6.

If 6 quantities are equal and total 6, each of them equals 1. <_<

Corollary:

If the probability of achieving result R in one trial is p,

the average number of trials necessary [expectation value] to achieve R is 1/p.

...

That is an intuitive approach that looks convincing enough. But as a proof it seems recursive. Basically, what it says is: Because we know that the average is this, we can show that it is indeed this.

As for the corollary that was the very thing that we were proving here.

Y-s proof is the one we can't argue with since it makes no presumption of what average is, but establishes it from the initial conditions (probabilities).

However, there are simpler "cuter" proofs, although may be also questionable. For example:

The average of an event is its probability times its weight (number of occurences).

Say probabiblity of an event to occur on a single try is "p" (known) and we designate the average as "a" (an unknown to be derived).

We can view the average as a sum (probability times number of occurences) of the event occuring on the first try, and not occurring on the first try. Then the average may be expressed as following:

a = p*1 + (1-p)*(1+a) (If it did not occur on the first try, now we expect it should take a+1 tries.) --> a = p + (1-p) + (1-p)a --> a = 1/p.

[Yoruichi-san]

Analogies are only suggestive, to guide thinking.

By achieving 1/5 of his objective we mean travel 1/5 of the distance from start to finish, not 1/5 of the remaining distance.

We can take away the determinism by saying the man had walked to the city a large number of times in the past and on average it took him 5 days to arrive.

If a day were 8 hours of walking, and on different days the man was well rested or not, or the weather was conducive or not to travel, then each time he made the trip his arrival time would be different from 40 hours although 40 hours was his average result.

Then it is valid to assert that, on average, a day's travel achieved 1/5 of the total distance. You get what I mean.

And then the equivalence of that statement with the statement that on average it takes him 1/(1/5) = 5 days is clear.

However, the first argument is a rigorous proof, not that the infinite series isn't, and is simpler.

Six trials, six equally likely results.

On average, one result each.

I think I see what you're saying, but I still don't think we can look at independent variables as "achieving a result". If I suddenly lost count (due to my mind being on another of your problems ;P), and then you asked me "what is the expected number of rolls you have to do to get a 6", I would still say 6. Independent of past rolls, if you ask at any time for the expected number of rolls, it is still the same because they are independent variables. However, if the man bumps his head one night, and the next morning wakes up with amnesia, the expected days he has to go is not 5, it depends on his past actions.

[Prime]

...

However, the first argument is a rigorous proof, not that the infinite series isn't, and is simpler.

Six trials, six equally likely results.

On average, one result each.

I type too slow and people manage to make several posts while I work on one.

So I'll repeat what I said in my previous post. I think you use a recursion here. "Six trials, six equally likely results" is a presumption of what the average is. The consecutive reasoning is based entirely on that presumption. It is not a proof. Such reasoning is simply a demonstration that if the average was what we presumed it was (1/p) that would lead to no contradiction.

[bonanova]

I think I see what you're saying, but I still don't think we can look at independent variables as "achieving a result". If I suddenly lost count (due to my mind being on another of your problems ;P), and then you asked me "what is the expected number of rolls you have to do to get a 6", I would still say 6. Independent of past rolls, if you ask at any time for the expected number of rolls, it is still the same because they are independent variables. However, if the man bumps his head one night, and the next morning wakes up with amnesia, the expected days he has to go is not 5, it depends on his past actions.

OK. Fair enough.

[bonanova]

I type too slow and people manage to make several posts while I work on one.

So I'll repeat what I said in my previous post. I think you use a recursion here. "Six trials, six equally likely results" is a presumption of what the average is. The consecutive reasoning is based entirely on that presumption. It is not a proof. Such reasoning is simply a demonstration that if the average was what we presumed it was (1/p) that would lead to no contradiction.

The only presumption is a fair die and each roll gives a result.

[Prime]

The only presumption is a fair die and each roll gives a result.

I understand. However, formal proof is not necessarily the same as common sense. You say that we roll six times and each number appears once (on average) because all numbers equal and we should not give a preference to any one of them over the other. That is an obvious sensible view, but I don't see it as a proof. I would be more inclined to accept that line of reasoning as a proof if you showed that all other possible views lead to a contradiction. E.g., Suppose some numbers are more equal than others. Then ...

[bonanova]

... [1] I don't see it as a proof...

... [2] Suppose some numbers are more equal than others. Then ...

1. I will take without proof your assertion that you do not see this as a proof.

2. It would not be a fair die.