By the way, I decided the expected value, E, is computed as follows:

E=SUM(as t from 1 to infinity) of [((P(t,n)-P(t-1,n))*t]

where P(t,n) = ((2^t -1)/2^t)^n.

I'd love to know how to simplify that.

 

That's a bold assumption. But I'll stipulate simply because I don't want to deal.

It is an assumption, or perhaps more of a hope. But I think that at least THIS misunderstanding has been resolved. Let's resolve any others as they come up and try to do so civilly on all sides. I would hate to see an interesting thread get closed.

Do you have an opinion on my solution?

I like the approach and think that it is well reasoned. I have another idea for taking your insight and seeing if it works out a bit cleaner. I'll get to that when I can.

The only thing that I am a bit unsure of (primarily because my background in prob/stats is extremely limited and several decades in the past) is how to properly tie this to the expected value. But I think that can be done by just doing a weighted sum over the number of tosses.

 

By the way, I decided the expected value, E, is computed as follows:

E=SUM(as t from 1 to infinity) of [((P(t,n)-P(t-1,n))*t]

where P(t,n) = ((2^t -1)/2^t)^n.

I'd love to know how to simplify that.

Yes, that was what I was thinking would need to be done to get the necessary weighted sum.

Here's my slightly different angle.

The probability that we need MORE than t tosses is the probability that at least one of n coins has landed tails up on every one of the t tosses. If the probability of landing heads is p, then the probability of coming up tails t times is

p(all tails after t tosses) = (1-p)^t

Thus the probability that a coin comes up heads at least once is

p(heads at least once after t tosses) = 1 - p(all tails after t tosses) = 1 - (1-p)^t

To not require an additional toss, all n coins must come up tails at least once.

p(not needing another toss after t tosses with n coins) = [1 - (1-p)^t]^n

Therefore the probability of needing one more toss is

p(another toss is needed after t tosses with n coins) = 1 - [1 - (1-p)^t]^n

Therefore expected number of tosses for n coins should be

\(E(n) = \sum_{t = 1}^\infty \; \( 1 - [1 - (1-p)^t]^n \) \)

I may have made a goof along the way. I've just had some cadets come in and they need me to do something right away, so I'll come back and check things out later. But I'm bothered by that leading 1 in a sum with an infinite number of terms.

 

Yes, that was what I was thinking would need to be done to get the necessary weighted sum.

Here's my slightly different angle.

The probability that we need MORE than t tosses is the probability that at least one of n coins has landed tails up on every one of the t tosses. If the probability of landing heads is p, then the probability of coming up tails t times is

p(all tails after t tosses) = (1-p)^t

Thus the probability that a coin comes up heads at least once is

p(heads at least once after t tosses) = 1 - p(all tails after t tosses) = 1 - (1-p)^t

To not require an additional toss, all n coins must come up tails at least once.

p(not needing another toss after t tosses with n coins) = [1 - (1-p)^t]^n

Therefore the probability of needing one more toss is

p(another toss is needed after t tosses with n coins) = 1 - [1 - (1-p)^t]^n

Therefore expected number of tosses for n coins should be

\(E(n) = \sum_{t = 1}^\infty \; \( 1 - [1 - (1-p)^t]^n \) \)

I may have made a goof along the way. I've just had some cadets come in and they need me to do something right away, so I'll come back and check things out later. But I'm bothered by that leading 1 in a sum with an infinite number of terms.

Assuming it is correct, this is a nice general solution for E given p and n.

I am comparing on my spreadsheet. So far, your E's are exactly one toss greater than my E's for any n and p=0.5. I am trying to discover where I (likely) erred.

 

Assuming it is correct, this is a nice general solution for E given p and n.

I am comparing on my spreadsheet. So far, your E's are exactly one toss greater than my E's for any n and p=0.5. I am trying to discover where I (likely) erred.

If I perform your sum from 0 to infinity (instead of 1 to infinity) our answers agree. I think this is because you are summing the odds of (not success) whereas I am summing the odds of (success). Does this make sense?



Edit: If this is the case, I find it interesting that the problem can be approached from "either end" with identical results. Not surprising...just interesting.

 

In fact, your formula (inside the summation) is equivalent to 1-((2^t-1)/2^t)^n for p=0.5.

This answers 1/2 of the question: how do I simplify my equation for E?

The other half is: Can we remove the summation and express E as a simple algebraic function of n and p?

 

MOD NOTE: Gentlemen, please let's not let this degenerate. A misinterpretation was made, it took a bit of back and forth to identify what it was and to clear it up. It has been cleared up. Let's move on with the discussion of the problem now that everyone is on the same page.

OK, I can agree that I misinterpreted the, apparent, initial intent. As I re-read the thread, it is clear that I was not the only one who misinterpreted - and that occurs all the time in a forum. Specification of terms such as "toss" and "flip" is important and maintaining civility is even more important. So, yes @WBahn, I am fine with moving on.

Given my "new" understanding, I would like to respond again to the initial questions.

Take n coins. Assume P(0.5) when tossed (no bias). Re-toss all heads-down (as a group) until only heads-up remain.

What is the average number of tosses required until all coins are heads up, and what does the distribution look like?

For the example of n=100 coins and counting the number of tosses until all coins end up heads. Again, any coin that is not heads is tossed as a group, regardless of the number. Thus, a toss continues with as many coins are not heads up until all coins are heads up.

Based on an n=100 coins and 10000 trials, where a trial consists of the number of tosses required to achieve a result where all coins are heads up, I see the following distribution.



Edited graph to remove density function because it insisted on padding something or not using the column I told it to or otherwise being annoying and I am too lazy to do in SAS

To address one part of the question, that is what the distribution of tosses looks like from a simulation as described.
To address the other part of the question, the average number of tosses required is observed, in this simulation, to be 8.01 with the 95% CI as 0.038.

Is that close to your expected value?

 

OK, I can agree that I misinterpreted the, apparent, initial intent. As I re-read the thread, it is clear that I was not the only one who misinterpreted - and that occurs all the time in a forum. Specification of terms such as "toss" and "flip" is important and maintaining civility is even more important. So, yes @WBahn, I am fine with moving on.

Given my "new" understanding, I would like to respond again to the initial questions.

Take n coins. Assume P(0.5) when tossed (no bias). Re-toss all heads-down (as a group) until only heads-up remain.

What is the average number of tosses required until all coins are heads up, and what does the distribution look like?

For the example of n=100 coins and counting the number of tosses until all coins end up heads. Again, any coin that is not heads is tossed as a group, regardless of the number. Thus, a toss continues with as many coins are not heads up until all coins are heads up.

Based on an n=100 coins and 10000 trials, where a trial consists of the number of tosses required to achieve a result where all coins are heads up, I see the following distribution.

View attachment 150159

To address one part of the question, that is what the distribution of tosses looks like from a simulation as described.
To address the other part of the question, the average number of tosses required is observed, in this simulation, to be 8.01 with the 95% CI as 0.038.

Is that close to your expected value?

The graph closely matches my computed data if the first blue bar represents t=5. It's hard to tell as the pips are misaligned with the bars.

Edit: and the smoothed curve appears shifted one t to the right.

Edit 2: actually, maybe one t/2 rightward.

 

I think you can compute the expected value of the number of steps \(E_N\) for N 'coins' as follows:

for 1 coin, from Joey's link https://www.codechef.com/wiki/tutorial-expectation

\(E_1 = 0.5*1 + 0.5*(1+E_1)\)


which gives you \(E_1 = 2\)

for 2 coins:

\(E_2 = 0.25*1 + 0.5*(1+E_1) + 0.25*(1+E_2)\)

there is a 25% chance that it will happen on the first throw - a run of 1, a 50% chance that you will have to rethrow one coin, so the expected value for this strand is \((1+E_1)\) and a 25% chance that you will have to rethrow both, with an expected value of \((1+E_2)\) (as you have already thrown once). This gives

\(E_2 = 8/3\)

going on I get \(E_3 = 22/7 = 3.14\) and \(E_4 = 384/105 = 3.65\)

You can generate a recurrence formula:

\((1-2^{-N})E_N = 1 + 2^{-N}(^NC_1E_1 + ^NC_2E_2 + ... + ^NC_{N-1}E_{N-1})\)

at that point I got sick of playing....

 

...at that point I got sick of playing....

That is exactly why I chose not to pursue that line of thought!

 

Hey! I just realized @WBahns solution is applicable to the old Yahtzee game:

What is the likelihood of getting Yahtzee (5 of a kind on 5 six sided dice) after three rolls?

For a single value, say 5 sixes, P=[1 - (1-p)^t]^n where p=1/6, n=5, and t=3.

For any set of five of a kind, just multiply the answer by 6.

Am I right?

 

Assuming it is correct, this is a nice general solution for E given p and n.

I am comparing on my spreadsheet. So far, your E's are exactly one toss greater than my E's for any n and p=0.5. I am trying to discover where I (likely) erred.

A couple good Monte Carlo sims might be in order to determine which one of us (if either) is correct.

 

In fact, your formula (inside the summation) is equivalent to 1-((2^t-1)/2^t)^n for p=0.5.

This answers 1/2 of the question: how do I simplify my equation for E?

The other half is: Can we remove the summation and express E as a simple algebraic function of n and p?

I believe so. At first blush the series looks suspiciously like that for the natural log. Since we are pretty sure it should be a base-2 log of something close to n, that's probably a good place to start.

 

If I perform your sum from 0 to infinity (instead of 1 to infinity) our answers agree.

And I think my sum NEEDS to start from 0, since there is a 100% chance that, after 0 tosses, another toss is required. That would increase my result by 1.

 

That is exactly why I chose not to pursue that line of thought!

It's at least as much fun as a monte-carlo sim!

To help you plan when you will be home for dinner without running a MC sim, a good approximation is
E(N) = 1.4085 * ln(N) + 1.4735

 

Aside:
If you mount them on their edge they will have lower inductance.

 

It's at least as much fun as a monte-carlo sim!

To help you plan when you will be home for dinner without running a MC sim, a good approximation is
E(N) = 1.4085 * ln(N) + 1.4735

Yes. But I have been trying (for fun) to find the form of the equation that exactly matches the predicted E(p,n). I figured if I could find the form, then working backwards to an equivalent Taylor series would be easy -- and from there I should arrive at @WBahn's generalized solution.

This is the table for E(0.5,n):



Clearly, for large n, each octave adds one additional t to E, therefore, log2(n). But the non-linearity for small n is turning out to be a major headache. I've got a nice curve matching program that maps the data against thousands of possible forms, but there is apparently no simple function that exactly matches the expected result.

Giving up now.

 

This is the best fit I was able to come up with. I don't even want to try to come up with a Taylor series for it:

 

And I think my sum NEEDS to start from 0, since there is a 100% chance that, after 0 tosses, another toss is required. That would increase my result by 1.

Based on this page, it seems that log expansions are all summed 1 to infinity. So I hoped I could change your expression from:

\(E(p,n) = \sum_{t = 0}^\infty \; \( 1 - [1 - (1-p)^t]^n \) \)

to

\(E(p,n) = \sum_{t = 1}^\infty \; \( 1 - [1 - (1-p)^{(t-1)}]^n \) \)

and find a suitable match.

No luck. I think I have exceeded the limit of my math skills.

Luckily, I am just an engineer.

 

If anyone is wondering the reason why I am pursuing this, the answer is:

None at all. It is a complete waste of my time.

I just like to see apparently complex phenomena reduced to a simple set of expressions.

That, and @WBahn continues to amaze. I wish he had more time to invest in this.