Cutting random pieces of string

From a string of length 1 m , 1 \text{ m}, we choose a length uniformly at random between 0 m 0 \text{ m} and 1 m , 1 \text{ m}, and cut as many of these lengths as possible from the string.

What is the expected length of the remaining string (in meters)?


Bonus: If we have a random number a a chosen with uniform distribution over the interval ( 0 , 1 n ] , \big(0,\frac{1}{n}\big], where n N n\in\mathbb{N} , what's the expected value of the remainder 1 m o d a 1\bmod a for a particular n ? n?


The answer is 0.1775.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Zico Quintina
May 28, 2018

Relevant wiki: Discrete Probability Distribution - Uniform Distribution

Let l l be the length of the piece(s) being cut, and r r the length of the remaining piece.

  • P [ 1 2 l 1 ] = 1 1 2 = 1 2 P \left[ \dfrac{1}{2} \le l \le 1 \right] = 1 - \dfrac{1}{2} = \dfrac{1}{2} ; and r r will be uniformly distributed between 0 0 and 1 2 \dfrac{1}{2} , so its expected length will be 1 4 \ \dfrac{1}{4} \\ \\

  • P [ 1 3 l < 1 2 ] = 1 2 1 3 = 1 6 P \left[ \dfrac{1}{3} \le l < \dfrac{1}{2} \right] = \dfrac{1}{2} - \dfrac{1}{3} = \dfrac{1}{6} ; and r r will be uniformly distributed between 0 0 and 1 3 \dfrac{1}{3} , so its expected length will be 1 6 \ \dfrac{1}{6} \\ \\

  • P [ 1 4 l < 1 3 ] = 1 3 1 4 = 1 12 P \left[ \dfrac{1}{4} \le l < \dfrac{1}{3} \right] = \dfrac{1}{3} - \dfrac{1}{4} = \dfrac{1}{12} ; and r r will be uniformly distributed between 0 0 and 1 4 \dfrac{1}{4} , so its expected length will be 1 8 \ \dfrac{1}{8}

\qquad \vdots \\

  • In general, P [ 1 n + 1 l < 1 n ] = 1 n 1 n + 1 = 1 n ( n + 1 ) P \left[ \dfrac{1}{n+1} \le l < \dfrac{1}{n} \right] = \dfrac{1}{n} - \dfrac{1}{n+1} = \dfrac{1}{n(n+1)} ; then r r will be uniformly distributed between 0 0 and 1 n + 1 \dfrac{1}{n+1} , so its expected length will be 1 2 ( n + 1 ) \ \dfrac{1}{2(n+1)} \\ \\

So the expected length of the remaining piece is

( 1 2 ) ( 1 4 ) + ( 1 6 ) ( 1 6 ) + ( 1 12 ) ( 1 8 ) + . . . . + ( 1 n ( n + 1 ) ) ( 1 2 ( n + 1 ) ) + . . . . \left( \dfrac{1}{2} \right) \left( \dfrac{1}{4} \right) + \left( \dfrac{1}{6} \right) \left( \dfrac{1}{6} \right) + \left( \dfrac{1}{12} \right) \left( \dfrac{1}{8} \right) + \ .... \ + \left( \dfrac{1}{n(n+1)} \right) \left( \dfrac{1}{2(n+1)} \right) + \ ....

The general term can be re-written using partial fractions as

( 1 n ( n + 1 ) ) ( 1 2 ( n + 1 ) ) = 1 2 ( 1 n ( n + 1 ) 2 ) = 1 2 ( 1 n 1 n + 1 1 ( n + 1 ) 2 ) \begin{aligned} \left( \dfrac{1}{n(n+1)} \right) \left( \dfrac{1}{2(n+1)} \right) &= \dfrac{1}{2} \left( \dfrac{1}{n(n+1)^2} \right) \\ \\ &= \dfrac{1}{2} \left( \dfrac{1}{n} - \dfrac{1}{n+1} - \dfrac{1}{(n+1)^2} \right) \end{aligned}

We can then write the expected length of the remaining piece as

1 2 [ n = 1 ( 1 n 1 n + 1 ) n = 1 1 ( n + 1 ) 2 ] = 1 2 [ n = 1 ( 1 n 1 n + 1 ) ( ( n = 1 1 n 2 ) 1 ) ] \dfrac{1}{2} \left[ \ \sum_{n=1}^{\infty} \left( \dfrac{1}{n} - \dfrac{1}{n+1} \right) - \sum_{n=1}^{\infty} \dfrac{1}{(n+1)^2} \right]= \dfrac{1}{2} \left[ \ \sum_{n=1}^{\infty} \left( \dfrac{1}{n} - \dfrac{1}{n+1} \right) - \left( \left( \sum_{n=1}^{\infty} \dfrac{1}{n^2} \right) - 1 \right) \right]

The first summation telescopes to 1 1 ; the second is known as the Basel Problem , which Euler famously found to be π 2 6 \dfrac{\pi^2}{6} . Thus the expected length of the remaining piece is

1 2 ( 1 ( π 2 6 1 ) ) = 1 2 ( 2 π 2 6 ) = 1 π 2 12 \dfrac{1}{2} \left( 1 - \left( \dfrac{\pi^2}{6} -1 \right) \right) = \dfrac{1}{2} \left( 2 - \dfrac{\pi^2}{6} \right) = \boxed{1 - \dfrac{\pi^2}{12}}

This is very nice—you avoid directly computing integrals. This is very desirable.

R Mathe - 3 years ago

The first way I solved it was with Matlab (quasi cheating :-). I then went for a walk and came up with a germ of an idea, which turned out to be the same as Zico Quintana's method. I did resort to Wolfram for doing the sum.

Ian Leslie - 3 years ago

Oh my * *! I forgot to multiply by the 1/2;

Ariijit Dey - 3 years ago

if i cut the string by 0.6 m , remaining is 0.4m

if i cut it by 0.4 the .4+.4=.8, remaining 0.2m i am not understanding the language of the question

snehit panghal - 3 years ago

Log in to reply

Umm… you’re computations are correct. You’re not not understanding. Now ‘simply’ compute the ‘average value’ of these remainder lengths.

R Mathe - 3 years ago

Log in to reply

why should i do that? i am not understanding the meaning of the question

snehit panghal - 3 years ago

Log in to reply

@Snehit Panghal The problem is as follows:

  1. For any cutting-length, a [ 0 , 1 ] a\in[0,1] , define the ‘remainder length’ as L ( a ) = min { 1 m a m > 0 , 1 m a 0 } L(a)=\min\{1-ma\mid m>0, 1-ma\geq 0\} .

  2. Now assume a U ( [ 0 , 1 ] ) a\sim U([0,1]) ie a a is a r.v. uniformly randomly distributed in [ 0 , 1 ] [0,1] . Compute E [ L ( a ) ] \mathbb{E}[L(a)] , ie compute the expected (‘average’) value of the remainder lengths.

You already understood 1 fine, as you demonstrated in your computations L ( 0.6 ) = 1 0.6 = 0.4 L(0.6)=1-0.6=0.4 and L ( 0.4 ) = 1 2 0.4 = 0.2 L(0.4)=1-2\cdot 0.4=0.2 . Now do 2. That is what this problem asks.

PS: not ‘I am not understanding’ ⟶ but ‘I don’t understand’. Ing-forms are used to describe what one is doing right now . The former is an unnatural expression.

R Mathe - 3 years ago

can somebody explain meaning of the question

snehit panghal - 3 years ago

I got the process right but I miscalculated it as π^2/12 - 1/2 and hence this is the only question I got wrong this week.

Aatman Supkar - 3 years ago
Lucas Viana Reis
May 20, 2018

Relevant wiki: Expected Value - Definition

The question is equivalent of asking the expected value of 1 m o d a 1 \bmod a for random a ( 0 , 1 ] a\in(0,1] (why?!).

The graph below shows the behavior of 1 m o d x 1 \bmod x from 0 to 1, which represents the fraction of the string left when making cuts x x units long. As you can see, you get discontinuities at 1 n \frac{1}{n} for n N n\in\mathbb{N} (note that 1 = 1 n n + 0 \small 1=\frac{1}{n}n+0 ). So we can separate the graph into a series of segments from ( 1 n , 1 n ) (\frac{1}{n},\frac{1}{n}) to ( 1 n + 1 , 0 ) (\frac{1}{n+1},0) , starting from n = 1.

The n n th interval has a leght 1 n 1 n + 1 \frac 1{n}-\frac 1{n+1} and an avarage height 1 2 ( n + 1 ) \frac 1{2(n+1)} , so the expected value, which corresponds to the avarage height of the entire function, is equal to the sum of the average heights of the segments weighted by the relative lenght of each interval the segment is contained. As those lenghts add up to 1, the weights are simply the lenghts themselves:

n = 1 1 2 ( n + 1 ) ( 1 n 1 n + 1 ) \sum_{n=1}^{\infty}\frac 1{2(n+1)}\left(\frac 1n-\frac 1{n+1}\right )

This can be rewritten to 1 2 [ n = 1 1 n ( n + 1 ) n = 1 1 ( n + 1 ) 2 ] \frac 1{2}\left [\sum_{n=1}^{\infty}\frac 1{n(n+1)}- \sum_{n=1}^{\infty}\frac 1{(n+1)^2} \right ]

The first term is a telescoping series sum that equals 1, and the second term is the sum of the reciprocal of squares minus the first term, which equals ζ ( 2 ) 1 = π 2 6 1 \zeta(2)-1=\frac {\pi^2}{6}-1

Thus, the answer is: 1 2 [ 1 ( π 2 6 1 ) ] \frac 1{2}\left [1-\left (\frac {\pi^2}{6}-1 \right)\right ] 1 π 2 12 0.1775 1-\frac{\pi^2}{12} \approx 0.1775

R Mathe
May 27, 2018

Relevant wiki: Expected Value - Problem Solving

Let a a denote the r. v. in both problems. Since a a is continuously distributed, it is a.e. not of the form 1 n \frac{1}{n} for any n n . So a.e. a m 1 ( 1 m + 1 , 1 m ) a\in\bigcup_{m\geq 1}(\frac{1}{m+1},\frac{1}{m}) respectively a m n ( 1 m + 1 , 1 m ) a\in\bigcup_{m\geq n}(\frac{1}{m+1},\frac{1}{m}) in the second problem.

Let m N m\in\mathbb{N} . For a ( 1 m + 1 , 1 m ) a\in(\frac{1}{m+1},\frac{1}{m}) it holds that m a < 1 ma<1 and ( m + 1 ) a > 1 (m+1)a>1 , hence the length a a can be cut maximum of m m times from 1 1 leaving L ( a ) = 1 m a L(a)=1-ma as the remainder. We may thus compute the expected values as follows

[ m ] r c l E [ L ( a ) a ( 0 , 1 n ] ] = m n P [ a ( 1 m + 1 , 1 m ) a ( 0 , 1 n ] ] E [ L ( a ) a ( 1 m + 1 , 1 m ) ] = m n 1 m 1 m + 1 1 n 0 E [ 1 m a a ( 1 m + 1 , 1 m ) ] = m n n m ( m + 1 ) ( 1 m E [ a a ( 1 m + 1 , 1 m ) ] ) = m n n m ( m + 1 ) ( 1 m 1 2 ( 1 m + 1 + 1 m ) ) = m n n m ( m + 1 ) ( 1 2 m + 1 2 ( m + 1 ) ) = n 2 m n 1 m ( m + 1 ) 2 = n 2 m n 1 m 1 m + 1 1 ( m + 1 ) 2 = n 2 ( 1 n lim m 1 m + 1 m n 1 ( m + 1 ) 2 ) = n 2 ( 1 n m 1 1 m 2 = ζ ( 2 ) = π 2 / 6 + 1 m n 1 m 2 ) = n 2 ( 1 n + 1 m n 1 m 2 π 2 6 ) \begin{array}{c}[m]{rcl} \mathbb{E}[L(a)\mid a\in(0,\frac{1}{n}]] &= &\sum_{m\geq n}\mathbb{P}[a\in(\frac{1}{m+1},\frac{1}{m})\mid a\in(0,\frac{1}{n}]] \cdot\mathbb{E}[L(a)\mid a\in(\frac{1}{m+1},\frac{1}{m})]\\ &= &\sum_{m\geq n}\dfrac{\frac{1}{m}-\frac{1}{m+1}}{\frac{1}{n}-0} \cdot\mathbb{E}[1-ma\mid a\in(\frac{1}{m+1},\frac{1}{m})]\\ &= &\sum_{m\geq n}\frac{n}{m(m+1)} \cdot\left(1-m\mathbb{E}[a\mid a\in(\frac{1}{m+1},\frac{1}{m})]\right)\\ &= &\sum_{m\geq n}\frac{n}{m(m+1)} \cdot\left(1-m\cdot\frac{1}{2}(\frac{1}{m+1}+\frac{1}{m})\right)\\ &= &\sum_{m\geq n}\frac{n}{m(m+1)}\cdot\left(1-\frac{2m+1}{2(m+1)}\right)\\ &= &\frac{n}{2}\sum_{m\geq n}\frac{1}{m(m+1)^{2}}\\ &= &\frac{n}{2}\sum_{m\geq n}\frac{1}{m}-\frac{1}{m+1}-\frac{1}{(m+1)^{2}}\\ &= &\frac{n}{2}\left(\frac{1}{n}-\lim_{m\rightarrow\infty}\frac{1}{m+1} -\sum_{m\geq n}\frac{1}{(m+1)^{2}}\right)\\ &= &\frac{n}{2}\big(\frac{1}{n}-\underbrace{\sum_{m\geq 1}\frac{1}{m^{2}}}_{=\zeta(2)=\pi^{2}/6}+\sum_{1\leq m\leq n}\frac{1}{m^{2}}\big)\\ &= &\frac{n}{2}\left(\frac{1}{n}+\sum_{1\leq m\leq n}\frac{1}{m^{2}}-\frac{\pi^{2}}{6}\right)\\ \end{array}

Hence the expected length in the second problem is n 2 ( 1 n + 1 m n 1 m 2 π 2 6 ) \frac{n}{2}\left(\frac{1}{n}+\sum_{1\leq m\leq n}\frac{1}{m^{2}}-\frac{\pi^{2}}{6}\right) . The first problem is just a special case of this with n = 1 n=1 . This yields E [ L ( a ) ] = 1 2 ( 1 + 1 π 2 6 ) = 1 π 2 12 0 , 1775329666 \mathbb{E}[L(a)]=\frac{1}{2}(1+1-\frac{\pi^{2}}{6})=1-\frac{\pi^{2}}{12}\approx 0,1775329666 .

I did the same, but there's a typo at the end, π^2/6 must be after a minus sing.

Pau Cantos - 3 years ago

Log in to reply

Thanks—typing things up often yields progressive errors when 1 typing mistake occurs—in this case it was generated in the second last line of the longer calculation.

R Mathe - 3 years ago

A person with good eyesight should be able to see something .04mm wide (or .0004 metres). It would be sensible to believe the same about length, meaning you can cut 25,000 equal pieces of .04mm rope.

Joshua Mendez - 3 years ago

Log in to reply

Are you referring to the a. e. statement? This means, a choice of cuts in { 1 n : n N + } \{\frac{1}{n}:n\in\mathbb{N}^{+}\} occurs with probability 0 0 . It is certainly a possible event, but empirically improbable, as it represents a mere dust of options, compared to the thick range of options of the rest of the unit interval ( 0 , 1 ] (0,1] .

R Mathe - 3 years ago

Log in to reply

No, for the first question as to how long the last piece would be.

Joshua Mendez - 3 years ago

Log in to reply

@Joshua Mendez The questions statement talks about picking a random lenght to cut first, and then making cuts of this lenght until the remaining piece is smaller than this lenght. It's an ideal situation, what do you mean by visual limitations?

Lucas Viana Reis - 3 years ago

@Joshua Mendez In your example it would be 0 0 . But your kind of example occurs with probability 0 0 . If one randomly chooses a length, then almost certainly (with probability 1 1 ) for any choice the remaining length will be positive. It follows that the average remaining length will be positive.

R Mathe - 3 years ago
Andrew Kerr
May 30, 2018

I plotted the result as y = x % 1.

The y axis is the length of string left, and the x axis represents the starting length. The average length is equal to the integral of this line between 0 and 1. I asked Mr Wolfram, and he didn't give me an answer... 😥

But then I wrote a little JS program to estimate it close enough! 😆

1
2
3
4
5
6
7
sum = 0
steps = 100000000
for (var i = 1/steps; i <= 1; i+=1/steps){
    sum += (1%i)/steps
}

// sum =>  0.1775329597217881

Nice 😃 btw don't you mean y = x % 1 instead of y = x % 3?

Lucas Viana Reis - 3 years ago

Log in to reply

Ooops yep, typo, thanks! Great problem!

Andrew Kerr - 3 years ago

Also, I find it really cool how when you go: sqrt(12(1 - 0.17753...)) you get a really nice estimate for pi.

Andrew Kerr - 3 years ago
Justin Chen
May 31, 2018

Expected value can be determined using a vast amount of trials. Doing this by hand is not clever, however if you have the patience, go ahead. A simple program in python 3 can bash out the numbers pretty quick and a value that is off by less then 0.0001. Here is the main gist of the program:

The answer you get is something along the lines of 1774.5759.... Now, since we used 10,000 instead of 1, we need to move the decimal place back 4 places. This turns 1774.5759.. into 0.17745, or roughly 0.1775

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...