Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Disclaimer: This is a hugely simplified version of a Project Euler problem, but I can't wrap my mind around a simple part of it, so I'm drastically narrowing it down.

I have a length L, and a fraction of it is special. For example:


I want to take a random slice at any point along the length. If it hits the special area, then I stop working. However, if it hits any other part, I remove whatever is to the left. Say,

============##### (1)
    ========##### (2)

Then I repeat the process.

I'm simulating this on Python with L=1 and "critical fraction" f=1/4. I find that for any given round, the expected length of the beam is consistent:

L(1) ~= 1
L(2) ~= 0.625
L(3) ~= 0.470
L(4) ~= 0.400

Thinking in terms of what I was doing physically, I came up with a relation to consistently reach L(2) from any f and any number of slices n:

L_new = (1/(n+1))*(L-f)+f

If I keep replacing L_new into L in this equation, the results aren't terrible:

R(1) = 1
R(2) = 0.625
R(3) = 0.4375
R(4) = 0.34375

If I use the simulation algorithm that produced the L values above starting at any given fraction R(x), L_new does give R(x+1).

However, there is clearly a divergence based on the fact that a number of previous slices can be guaranteed to have occurred in a certain area. I just don't know how to incorporate it into my L_new equation. Any ideas?

share|improve this question
Assuming that by "taking a random slice" you mean choosing a slice point uniformly, and that the special fraction is always on the right-hand end, I don't see how you get $0.625$. In the first step, there is a $\frac34$ chance that a slice will be sliced off, and the average length of that slice is $\frac12\cdot\frac34$, so the expected missing length is $\frac12\cdot\frac34\cdot\frac34=\frac9{32}$, and the expected remaining length is thus $\frac{23}{32}=0.71875$. What am I missing? (By the way, what do you mean by "consistent"? Consistent with what?) –  joriki Sep 19 '12 at 7:40
I apologize for any confusion in my terminology. I did mean uniformly, and the fraction is always on the right hand end. You have the same process as I, but my expected remaining lengths take it as a given that the slice actually happened, which why the probability that a slice what taken off in the previous round is actually 100%. So <pre>1-1/2*3/4=0.625</pre> –  RodericDay Sep 19 '12 at 12:51
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.