Problem 151

[fatcatfan]

My initial solution is apparently incorrect. After reviewing my code, adding various levels of intermediate output to verify program flow, I feel it correctly represents and calculates my interpretation of the problem.

So my interpretation is apparently wrong.

When a sheet is selected from the envelope, if there are, for example, two size A4 sheets, I consider them each unique branches in the path to reach a state where only one sheet is in the envelope as well as the path to the last batch.

However, when any sheet larger than an A5 is selected from the envelope and cut, I consider either A5 produced at the end of the cutting as identical. That is, I make no distinction between the A5 that gets used and the A5 that is replaced in the envelope. Should I? and by extension should I make a similar distinction for larger sizes? For example, which of two A4 produced from an A3 gets cut in half and which gets placed in the envelope.

[ed_r]

Why don't you just try it and see?

[fatcatfan]

Well, I'd initially thought it would add considerably more complexity to my algorithm, but after additional thought I realized it only requires adding additional scalars to a few lines, since those additional choices don't affect the state of the envelope at the beginning of each batch.

So I did that, and my answer still appears to be wrong. Perhaps my code needs further checking.

[fatcatfan]

After further checking, I feel confident that my code accurately simulates the problem. I'm think maybe I'm just not extracting the right data from the model to calculate the expected answer. Presently my result is calculated as ( N₁ + 2*N₂ + 3*N₃ ) / ( N₀ + N₁ + N₂ + N₃ ) where N_i represents the number of paths of random choice in which a single sheet of paper is found in the envelope i times in a week. Essentially I calculate a weighted average (expected value!).

I've run the simpler case of a 4 batch week starting with various combinations of A3, A4, and A5 and compared the results to manual calculation, indicating accurate modeling. I've checked the case of starting with a single A2 and verified that N₂ = 3 by code output and manual tree drawing.

With the assumption that my code works and my weighted average is the wrong approach to the answer, I'm just looking for a gentle nudge to help me see why I'm wrong. Perhaps the category of mathematics/probability/statistics that I should consult further. Or maybe an earlier/simpler problem that I should try first before revisiting problem 151. It's all about learning, right? (for reference, I'm a Civil Engineer)

And if you feel I've revealed too much about the problem's solution in this post I'll edit it out so others won't be spoiled to the problem. Somehow I doubt I've revealed too much since I'm getting the wrong answer

[Eigenray]

Have you tried running Monte Carlo simulations to confirm your results?

[fatcatfan]

I haven't. I'll read up on it to see how I could apply it in this case. Thanks.

Expand

I did locate a sort of "off by one" error in my calc. The problem doesn't care which sheet of paper is randomly chosen out of the envelope for the next to last batch, but I was adding that choice into the calc, ending my recursive function only when there was a single A5 in the envelope by itself, even though I didn't count the last single A5. I've fixed that and got a different result, of course, but it is still not the expected answer.

[Ikcelaks]

The problem description specifies that you are to exclude the first and last batches, so altering the code to count the last single sheet of A5 may have actually introduced an off-by-one error.

From what you've revealed about how you calculate the final expected value and how you perform the calculation by hand, I have a strong hunch that your model is incorrect. Do you weight every path equally? Should you?

I think it might be helpful for you to run through some actual small-scale simulations by hand to get a feel for how this problem works. Or, run a monte-carlo simulation as previously suggested. Either way, be sure to run through the actual process of the problem, not your model. That way, you can see how your model compares with reality.

[fatcatfan]

Thank you, I did finally discover my error.

Expand

The off-by-one wasn't counting the last sheet as a single, but there are three potential paths (two unique) from the next to last batch to the last batch, so that was scaling all my results needlessly and disproportionately.

The real problem though, was as you suspected: Even though my code efficiently iterated over only unique paths (40040) and factored in how many ways you could follow each, I had failed to realize that each path does not have the same probabilty, because the envelope doesn't always contain the same number of sheets.

How would/did you apply Monte Carlo methods to this problem? It's a new concept to me, but after some thought, I believe the right approach would be to rewrite the code to follow a random path, instead of iterating over all paths. Then tally the results of a large sample of runs to approximate the answer. Another step could be to tally how often each unique path is followed, thus identifying their relative probabilities and shedding light on the mistake in my thinking.

[Ikcelaks]

It's a new concept to me, but after some thought, I believe the right approach would be to rewrite the code to follow a random path, instead of iterating over all paths. Then tally the results of a large sample of runs to approximate the answer.

That's it. The general concept with a Monte-Carlo simulation is to write code that uses a pseudo-random number generator to simulate the random event and repeat the simulation many times, aggregating the results.

In all honesty, I've never actually written a Monte-Carlo simulation, because it is often more complicated to simulate these problems than to directly compute the expected value (This problem is definitely one of those cases.). However, it's definitely a useful technique for the cases where it's either very difficult to compute the probabilities directly or you have a bug in your logic that you can't track down.

[axelbrz]

Hi, can someone tell me what were the expected number of times (excluding the first and last time) if I were started with a paper of A3 size? (then I'll have one A4, and two A5, but as I'll use an A5, I'll have one A4 and one A5, etc.)

Thank you so much!

[daniel.is.fischer]

For four jobs, starting with an A3 paper, the expected number of times to find exactly one sheet in the envelope (excluding first and last) is 0.5, but that doesn't help you much, does it?

[axelbrz]

Lol, no I just wanted to know if I understood the problem,

Thanks!

[daniel.is.fischer]

Did you?

[pwan]

Does each piece of paper in the envelope have an equal chance of being picked by the foreman, or do the relative sizes of the paper come into play ?

For example, if the envelope contained an A4 and A5 pieces, would it be twice as likely the foreman would pick the A4 piece instead of the A5 piece, given the A4 piece is twice as big as the A5 piece, or would there be an equal chance the foreman would pick either piece ?

[daniel.is.fischer]

Each piece is picked with equal probability (1/(number of sheets in the envelope)).

[axelbrz]

Hi, I'm getting a wrong answer.

I want to know if the probability to get one sheet of paper once from the envelope in a week, rounded to 4 decimals, is 0.3042, and if the probability to get a sheet of paper twice, rounded to 4 decimals too, is 0.0386.

Thank you!

[harryh]

No, I'm afraid that the values you posted are wrong
During each week, and excluding the first and last batch:
- the probability that he finds a single sheet in the envelope exactly once is 0.3100 (rounded to 4 dec.pl.)
- the probability that he finds a single sheet in the envelope exactly twice is considerably higher than 0.0386.

[rockstome]

if he start from A3 size, expected number of times = a
if he start from A2 size, expected number of times = b
if he start from A1 size, expected number of times = c

daniel.is.fischer said that a=0.5
can anyone confirm that b>a>c ?

[oleglyamin]

Could you confirm the following for the case of starting with a sheet of A2-size?

Probability of having one sheet in the envelope exactly 0 times = 0.5714 (rounded to 4 decimal places).
Probability of having one sheet in the envelope exactly 2 times = 0.0714 (the same).
Expected number of times that the envelope has one sheet = 0.5 (exact).

Thanks.

[oleglyamin]

Disregard the last post. Problem solved.