Average length of the longest segment
$begingroup$
This post is related to a previous SE post If a 1 meter rope …. concerning average length of a smallest segment.
A rope of 1m is divided into three pieces by two random points. Find the average length of the largest segment.
My answer is 11/18. Here is how I do it:
Here we have two independent random variables $X,Y$, both uniform on $[0,1]$. Let
$A=min (X,Y), B=max (X,Y)$ and $C=max (A, 1-B, B-A)$. First we want to find the probability
density function $f_C(a)$ of $C$. Let $F_C(a)$ be the cumulative distribution function. Then
$$ F_C(a) = P(Cle a)=P(Ale a, 1-Ble a, B-Ale a).$$ By rewriting this probability as area in the unit square, I get
$$F_C(a)=left{begin{array}{ll} (3a-1)^2 & frac{1}{3}le ale frac{1}{2}\ 1-3(1-a)^2 & frac{1}{2}le ale 1end{array}right.$$ from which it follows that
$$f_C(a)=left{begin{array}{ll} 6(3a-1) & frac{1}{3}le ale frac{1}{2}\ 6(1-a) & frac{1}{2}le ale 1end{array}right.$$ Therefore
the expected value of $C$ is
$$int_{1/3} ^{1/2}6a(3a-1) da+int_{1/2} ^{1}6a(1-a) da= frac{11}{18}.$$
My questions are:
(A) Is there a "clever" way to figure out this number 11/18?
(B) What is the answer if the rope is divided into $n>3$ segments?
probability
edited Apr 13 '17 at 12:21
Community♦
1
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
$endgroup$
add a comment |
$begingroup$
This post is related to a previous SE post If a 1 meter rope …. concerning average length of a smallest segment.
A rope of 1m is divided into three pieces by two random points. Find the average length of the largest segment.
My answer is 11/18. Here is how I do it:
Here we have two independent random variables $X,Y$, both uniform on $[0,1]$. Let
$A=min (X,Y), B=max (X,Y)$ and $C=max (A, 1-B, B-A)$. First we want to find the probability
density function $f_C(a)$ of $C$. Let $F_C(a)$ be the cumulative distribution function. Then
$$ F_C(a) = P(Cle a)=P(Ale a, 1-Ble a, B-Ale a).$$ By rewriting this probability as area in the unit square, I get
$$F_C(a)=left{begin{array}{ll} (3a-1)^2 & frac{1}{3}le ale frac{1}{2}\ 1-3(1-a)^2 & frac{1}{2}le ale 1end{array}right.$$ from which it follows that
$$f_C(a)=left{begin{array}{ll} 6(3a-1) & frac{1}{3}le ale frac{1}{2}\ 6(1-a) & frac{1}{2}le ale 1end{array}right.$$ Therefore
the expected value of $C$ is
$$int_{1/3} ^{1/2}6a(3a-1) da+int_{1/2} ^{1}6a(1-a) da= frac{11}{18}.$$
My questions are:
(A) Is there a "clever" way to figure out this number 11/18?
(B) What is the answer if the rope is divided into $n>3$ segments?
probability
edited Apr 13 '17 at 12:21
Community♦
1
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
$endgroup$
$begingroup$
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n
$endgroup$
– Yudong Tang
Mar 23 '14 at 20:59
add a comment |
$begingroup$
This post is related to a previous SE post If a 1 meter rope …. concerning average length of a smallest segment.
A rope of 1m is divided into three pieces by two random points. Find the average length of the largest segment.
My answer is 11/18. Here is how I do it:
Here we have two independent random variables $X,Y$, both uniform on $[0,1]$. Let
$A=min (X,Y), B=max (X,Y)$ and $C=max (A, 1-B, B-A)$. First we want to find the probability
density function $f_C(a)$ of $C$. Let $F_C(a)$ be the cumulative distribution function. Then
$$ F_C(a) = P(Cle a)=P(Ale a, 1-Ble a, B-Ale a).$$ By rewriting this probability as area in the unit square, I get
$$F_C(a)=left{begin{array}{ll} (3a-1)^2 & frac{1}{3}le ale frac{1}{2}\ 1-3(1-a)^2 & frac{1}{2}le ale 1end{array}right.$$ from which it follows that
$$f_C(a)=left{begin{array}{ll} 6(3a-1) & frac{1}{3}le ale frac{1}{2}\ 6(1-a) & frac{1}{2}le ale 1end{array}right.$$ Therefore
the expected value of $C$ is
$$int_{1/3} ^{1/2}6a(3a-1) da+int_{1/2} ^{1}6a(1-a) da= frac{11}{18}.$$
My questions are:
(A) Is there a "clever" way to figure out this number 11/18?
(B) What is the answer if the rope is divided into $n>3$ segments?
probability
edited Apr 13 '17 at 12:21
Community♦
1
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
$endgroup$
This post is related to a previous SE post If a 1 meter rope …. concerning average length of a smallest segment.
A rope of 1m is divided into three pieces by two random points. Find the average length of the largest segment.
My answer is 11/18. Here is how I do it:
Here we have two independent random variables $X,Y$, both uniform on $[0,1]$. Let
$A=min (X,Y), B=max (X,Y)$ and $C=max (A, 1-B, B-A)$. First we want to find the probability
density function $f_C(a)$ of $C$. Let $F_C(a)$ be the cumulative distribution function. Then
$$ F_C(a) = P(Cle a)=P(Ale a, 1-Ble a, B-Ale a).$$ By rewriting this probability as area in the unit square, I get
$$F_C(a)=left{begin{array}{ll} (3a-1)^2 & frac{1}{3}le ale frac{1}{2}\ 1-3(1-a)^2 & frac{1}{2}le ale 1end{array}right.$$ from which it follows that
$$f_C(a)=left{begin{array}{ll} 6(3a-1) & frac{1}{3}le ale frac{1}{2}\ 6(1-a) & frac{1}{2}le ale 1end{array}right.$$ Therefore
the expected value of $C$ is
$$int_{1/3} ^{1/2}6a(3a-1) da+int_{1/2} ^{1}6a(1-a) da= frac{11}{18}.$$
My questions are:
(A) Is there a "clever" way to figure out this number 11/18?
(B) What is the answer if the rope is divided into $n>3$ segments?
probability
probability
edited Apr 13 '17 at 12:21
Community♦
1
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
edited Apr 13 '17 at 12:21
Community♦
1
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
1
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
asked Dec 13 '10 at 16:41
TCLTCL
9,21952059
9,21952059
$begingroup$
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n
$endgroup$
– Yudong Tang
Mar 23 '14 at 20:59
add a comment |
$begingroup$
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n
$endgroup$
– Yudong Tang
Mar 23 '14 at 20:59
$begingroup$
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n
$endgroup$
– Yudong Tang
Mar 23 '14 at 20:59
$begingroup$
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n
$endgroup$
– Yudong Tang
Mar 23 '14 at 20:59
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
The answer to (B) is actually given in both Yuval Filmus' and my answers to the question about the average length of the shortest segment. It's $$frac{1}{n} H_n,$$ where $H_n = sum_{k=1}^n frac{1}{k},$ i.e., the $n$th harmonic number.
"Clever" is of course subjective, but here's an argument for (A) in the $n$-piece case. At least there's only one (single-variable) integration in it. :)
If $X_1, X_2, ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the pieces of rope.
The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, ldots, c_k$, respectively (where $sum_{i=1}^k c_i leq 1$), is $$(1-c_1-c_2-ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.
If $V_{(n)}$ denotes the largest piece of rope, then
$$P(V_{(n)} > x) = P(V_1 > x text{ or } V_2 > x text{ or } cdots text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above,
$$P(V_{(n)} > x) = n(1-x)^{n-1} - binom{n}{2} (1 - 2x)^{n-1} + cdots + (-1)^{k-1} binom{n}{k} (1 - kx)^{n-1} + cdots,$$
where the sum continues until $kx > 1$.
Therefore,
$$E[V_{(n)}] = int_0^{infty} P(V_{(n)} > x) dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} int_0^{1/k} (1 - kx)^{n-1} dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} frac{1}{nk} $$
$$= frac{1}{n} sum_{k=1}^n frac{binom{n}{k}}{k} (-1)^{k-1} = frac{H_n}{n},$$
where the last step applies a known binomial sum identity.
edited Apr 13 '17 at 12:19
Community♦
1
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
$endgroup$
1
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
add a comment |
$begingroup$
A more intuitive answer. Let's arrange the segments from smallest to largest. Let the three segments be $x$, $x+y$ and $x+y+z$.
${rm sum of segments}$ = 1
$implies 3x + 2y + z = 1$;
subject to the constraints: $xgeqslant 0,y geqslant 0,z geqslant 0$
$implies x leqslant 1/3 , y leqslant 1/2, z leqslant 1$.
Within these limits, we can assume $x$,$y$ and $z$ can take on any values as long as we renormalize the total length to be equal to 1, sort of building the larger string from its constituent parts. These relative limits are equivalent to the following:
Let $x$ be chosen randomly among a pool from $[0,2n]$, $y$ be chosen randomly from a pool $[0,3n]$ and $z$ from a pool $[0,6n]$ where $(x,y,z,n)$ $in$ $mathbb R$.
Expected value of $x = n$, expected value of $y = 1.5n$ and expected value of $z = 3n$.
Expected length of longest segment = $x+y+z = 5.5n$
Expected total length = $3x+2y+z = 9n$
Therefore the expected length of longest segment is
$(x+y+z)/(3x+2y+z)= 5.5/9= 11/18 $.
The expected length of the shortest segment is
$x/(3x+2y+z) = 1/9$.
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
$endgroup$
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
add a comment |
$begingroup$
Neat as it is, I don't think Rahul's answer can be correct. If we have $3x+2y+z=1$ and $3x+2y+z=9n$, then $n=1/9$, which means $x leq 2/9$, which can't be right, as one solution is all pieces being of length 1/3 (however unlikely this exact solution may be, $x$ can take values in $(2/9,1/3]$).
Stefan's answer is wrong because the probability of any given point on the stick being in the longest piece (when cut in 2) is not uniform. That can be seen by considering the point halfway along, which is always in the longest piece. You can find the probability density function for the likelihood of any given point being in the longer half, then integrate to get the answer below.
My preferred solution is to let the cuts be at $X, Y$, with $Y gt X$:
Image of cut positions
Then each piece is equally likely to be the longest, and the expected length of the longest piece doesn't depend on which piece we choose. Then we can calculate $mathop{mathbb{E}}(X|X text{ is the longest piece} )$.
We have the three inequalities:
$$X gt Y-X implies Y < 2X$$
$$X gt 1-Y implies Y > 1-X$$
and, from our setup,
$$Y gt X$$
These can be represented by the following diagram:
Diagram of inequalities
Then the area satisfying our inequalities is the two triangles A and B. So we wish to find the expected value of $X$ within this area.
The expected value of $X$ in A is $bar{X}_A = frac{1}{2}-frac{1}{3}(frac{1}{2}-frac{1}{3}) = frac{8}{18}$.
The expected value of $X$ in B is $bar{X}_B = frac{1}{2}+frac{1}{3}(frac{1}{2}) = frac{4}{6} = frac{12}{18}$
The area of A is $A_A = frac{1}{2} times frac{1}{2}times (frac{1}{2}-frac{1}{3}) = frac{1}{24}$.
The area of B is $A_B = frac{1}{2} times frac{1}{2}times frac{1}{2} = frac{1}{8} = frac{3}{24} = 3 A_A$.
So $mathop{mathbb{E}}(X|X text{ is the longest piece} ) = frac{tfrac{8}{18} + 3left(tfrac{12}{18}right)}{4} = frac{11}{18}$
(Apologies for the comments on other solutions and the links, but I haven't got a high enough reputation to comment or embed directly)
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
$endgroup$
add a comment |
$begingroup$
Why is this answer wrong?
Let the length of the longest segment created by the FIRST cut be $L_1$. Now consider the second cut. With probability $(1-L_1)$ it will be in the shorter segment made by the first cut, and the longest of the 3 segments will then have length $L_1$.
On the other hand, with probability $L_1$ the second cut will be in the longer first segment, and the longest of the 3 segments will then be the max of the longer segment made by the second cut, call it $L_2$, or the shorter segment made by the first cut, of length $(1-L_1)$.
This gives an expected length of the longest segment as:
$(1-L_1)L_1+L_1 max[L_2,(1-L_1)]$. If we now average this over cut positions, it is easy to reason that $L_1=3/4$, and $L_2=L_1^2=9/16$, giving the average length of the longest segment to be 39/64. This disagrees with 11/18, but only by 0.3%!
I assume there is a problem with performing the "averaging" over the $max$ function, but I don't understand why. Any feedback would be great! Thanks!!
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
$endgroup$
add a comment |
$begingroup$
A similar, but a bit more complex problem, that highlights how important it is to understand the exact wording of a formulation:
cut a rope (or break a rod) at a random point. Set aside a piece. Cut (or break) the remaining piece at another random point.
Question is the same (expected length of the longest segment).
That's how I initially understood the problem..
Got stuck in algebra and closed-form anti-derivatives..
Same principle, heavier calculations.
I got an answer $2ln2 - ln3 + 3/8 approx 0.663$, that matches what a MatLab script gives for $1000$ tests.
edited Jan 16 at 21:27
dantopa
6,67442245
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f14190%2faverage-length-of-the-longest-segment%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The answer to (B) is actually given in both Yuval Filmus' and my answers to the question about the average length of the shortest segment. It's $$frac{1}{n} H_n,$$ where $H_n = sum_{k=1}^n frac{1}{k},$ i.e., the $n$th harmonic number.
"Clever" is of course subjective, but here's an argument for (A) in the $n$-piece case. At least there's only one (single-variable) integration in it. :)
If $X_1, X_2, ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the pieces of rope.
The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, ldots, c_k$, respectively (where $sum_{i=1}^k c_i leq 1$), is $$(1-c_1-c_2-ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.
If $V_{(n)}$ denotes the largest piece of rope, then
$$P(V_{(n)} > x) = P(V_1 > x text{ or } V_2 > x text{ or } cdots text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above,
$$P(V_{(n)} > x) = n(1-x)^{n-1} - binom{n}{2} (1 - 2x)^{n-1} + cdots + (-1)^{k-1} binom{n}{k} (1 - kx)^{n-1} + cdots,$$
where the sum continues until $kx > 1$.
Therefore,
$$E[V_{(n)}] = int_0^{infty} P(V_{(n)} > x) dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} int_0^{1/k} (1 - kx)^{n-1} dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} frac{1}{nk} $$
$$= frac{1}{n} sum_{k=1}^n frac{binom{n}{k}}{k} (-1)^{k-1} = frac{H_n}{n},$$
where the last step applies a known binomial sum identity.
edited Apr 13 '17 at 12:19
Community♦
1
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
$endgroup$
1
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
add a comment |
$begingroup$
The answer to (B) is actually given in both Yuval Filmus' and my answers to the question about the average length of the shortest segment. It's $$frac{1}{n} H_n,$$ where $H_n = sum_{k=1}^n frac{1}{k},$ i.e., the $n$th harmonic number.
"Clever" is of course subjective, but here's an argument for (A) in the $n$-piece case. At least there's only one (single-variable) integration in it. :)
If $X_1, X_2, ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the pieces of rope.
The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, ldots, c_k$, respectively (where $sum_{i=1}^k c_i leq 1$), is $$(1-c_1-c_2-ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.
If $V_{(n)}$ denotes the largest piece of rope, then
$$P(V_{(n)} > x) = P(V_1 > x text{ or } V_2 > x text{ or } cdots text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above,
$$P(V_{(n)} > x) = n(1-x)^{n-1} - binom{n}{2} (1 - 2x)^{n-1} + cdots + (-1)^{k-1} binom{n}{k} (1 - kx)^{n-1} + cdots,$$
where the sum continues until $kx > 1$.
Therefore,
$$E[V_{(n)}] = int_0^{infty} P(V_{(n)} > x) dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} int_0^{1/k} (1 - kx)^{n-1} dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} frac{1}{nk} $$
$$= frac{1}{n} sum_{k=1}^n frac{binom{n}{k}}{k} (-1)^{k-1} = frac{H_n}{n},$$
where the last step applies a known binomial sum identity.
edited Apr 13 '17 at 12:19
Community♦
1
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
$endgroup$
1
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
add a comment |
$begingroup$
The answer to (B) is actually given in both Yuval Filmus' and my answers to the question about the average length of the shortest segment. It's $$frac{1}{n} H_n,$$ where $H_n = sum_{k=1}^n frac{1}{k},$ i.e., the $n$th harmonic number.
"Clever" is of course subjective, but here's an argument for (A) in the $n$-piece case. At least there's only one (single-variable) integration in it. :)
If $X_1, X_2, ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the pieces of rope.
The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, ldots, c_k$, respectively (where $sum_{i=1}^k c_i leq 1$), is $$(1-c_1-c_2-ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.
If $V_{(n)}$ denotes the largest piece of rope, then
$$P(V_{(n)} > x) = P(V_1 > x text{ or } V_2 > x text{ or } cdots text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above,
$$P(V_{(n)} > x) = n(1-x)^{n-1} - binom{n}{2} (1 - 2x)^{n-1} + cdots + (-1)^{k-1} binom{n}{k} (1 - kx)^{n-1} + cdots,$$
where the sum continues until $kx > 1$.
Therefore,
$$E[V_{(n)}] = int_0^{infty} P(V_{(n)} > x) dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} int_0^{1/k} (1 - kx)^{n-1} dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} frac{1}{nk} $$
$$= frac{1}{n} sum_{k=1}^n frac{binom{n}{k}}{k} (-1)^{k-1} = frac{H_n}{n},$$
where the last step applies a known binomial sum identity.
edited Apr 13 '17 at 12:19
Community♦
1
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
$endgroup$
The answer to (B) is actually given in both Yuval Filmus' and my answers to the question about the average length of the shortest segment. It's $$frac{1}{n} H_n,$$ where $H_n = sum_{k=1}^n frac{1}{k},$ i.e., the $n$th harmonic number.
"Clever" is of course subjective, but here's an argument for (A) in the $n$-piece case. At least there's only one (single-variable) integration in it. :)
If $X_1, X_2, ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the pieces of rope.
The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, ldots, c_k$, respectively (where $sum_{i=1}^k c_i leq 1$), is $$(1-c_1-c_2-ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.
If $V_{(n)}$ denotes the largest piece of rope, then
$$P(V_{(n)} > x) = P(V_1 > x text{ or } V_2 > x text{ or } cdots text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above,
$$P(V_{(n)} > x) = n(1-x)^{n-1} - binom{n}{2} (1 - 2x)^{n-1} + cdots + (-1)^{k-1} binom{n}{k} (1 - kx)^{n-1} + cdots,$$
where the sum continues until $kx > 1$.
Therefore,
$$E[V_{(n)}] = int_0^{infty} P(V_{(n)} > x) dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} int_0^{1/k} (1 - kx)^{n-1} dx = sum_{k=1}^n binom{n}{k} (-1)^{k-1} frac{1}{nk} $$
$$= frac{1}{n} sum_{k=1}^n frac{binom{n}{k}}{k} (-1)^{k-1} = frac{H_n}{n},$$
where the last step applies a known binomial sum identity.
edited Apr 13 '17 at 12:19
Community♦
1
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
edited Apr 13 '17 at 12:19
Community♦
1
edited Apr 13 '17 at 12:19
Community♦
1
edited Apr 13 '17 at 12:19
Community♦
1
1
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
answered Dec 13 '10 at 16:51
Mike SpiveyMike Spivey
43k8146236
43k8146236
1
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
add a comment |
1
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
1
1
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
$begingroup$
This is a long shot, but the harmonic number $H_n$ also appears in the classical coupon collector problem. Is there some deep combinatorial connection between the broken stick and the coupon collector problems?
$endgroup$
– Jack D'Aurizio
Mar 26 '17 at 2:23
add a comment |
$begingroup$
A more intuitive answer. Let's arrange the segments from smallest to largest. Let the three segments be $x$, $x+y$ and $x+y+z$.
${rm sum of segments}$ = 1
$implies 3x + 2y + z = 1$;
subject to the constraints: $xgeqslant 0,y geqslant 0,z geqslant 0$
$implies x leqslant 1/3 , y leqslant 1/2, z leqslant 1$.
Within these limits, we can assume $x$,$y$ and $z$ can take on any values as long as we renormalize the total length to be equal to 1, sort of building the larger string from its constituent parts. These relative limits are equivalent to the following:
Let $x$ be chosen randomly among a pool from $[0,2n]$, $y$ be chosen randomly from a pool $[0,3n]$ and $z$ from a pool $[0,6n]$ where $(x,y,z,n)$ $in$ $mathbb R$.
Expected value of $x = n$, expected value of $y = 1.5n$ and expected value of $z = 3n$.
Expected length of longest segment = $x+y+z = 5.5n$
Expected total length = $3x+2y+z = 9n$
Therefore the expected length of longest segment is
$(x+y+z)/(3x+2y+z)= 5.5/9= 11/18 $.
The expected length of the shortest segment is
$x/(3x+2y+z) = 1/9$.
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
$endgroup$
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
add a comment |
$begingroup$
A more intuitive answer. Let's arrange the segments from smallest to largest. Let the three segments be $x$, $x+y$ and $x+y+z$.
${rm sum of segments}$ = 1
$implies 3x + 2y + z = 1$;
subject to the constraints: $xgeqslant 0,y geqslant 0,z geqslant 0$
$implies x leqslant 1/3 , y leqslant 1/2, z leqslant 1$.
Within these limits, we can assume $x$,$y$ and $z$ can take on any values as long as we renormalize the total length to be equal to 1, sort of building the larger string from its constituent parts. These relative limits are equivalent to the following:
Let $x$ be chosen randomly among a pool from $[0,2n]$, $y$ be chosen randomly from a pool $[0,3n]$ and $z$ from a pool $[0,6n]$ where $(x,y,z,n)$ $in$ $mathbb R$.
Expected value of $x = n$, expected value of $y = 1.5n$ and expected value of $z = 3n$.
Expected length of longest segment = $x+y+z = 5.5n$
Expected total length = $3x+2y+z = 9n$
Therefore the expected length of longest segment is
$(x+y+z)/(3x+2y+z)= 5.5/9= 11/18 $.
The expected length of the shortest segment is
$x/(3x+2y+z) = 1/9$.
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
$endgroup$
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
add a comment |
$begingroup$
A more intuitive answer. Let's arrange the segments from smallest to largest. Let the three segments be $x$, $x+y$ and $x+y+z$.
${rm sum of segments}$ = 1
$implies 3x + 2y + z = 1$;
subject to the constraints: $xgeqslant 0,y geqslant 0,z geqslant 0$
$implies x leqslant 1/3 , y leqslant 1/2, z leqslant 1$.
Within these limits, we can assume $x$,$y$ and $z$ can take on any values as long as we renormalize the total length to be equal to 1, sort of building the larger string from its constituent parts. These relative limits are equivalent to the following:
Let $x$ be chosen randomly among a pool from $[0,2n]$, $y$ be chosen randomly from a pool $[0,3n]$ and $z$ from a pool $[0,6n]$ where $(x,y,z,n)$ $in$ $mathbb R$.
Expected value of $x = n$, expected value of $y = 1.5n$ and expected value of $z = 3n$.
Expected length of longest segment = $x+y+z = 5.5n$
Expected total length = $3x+2y+z = 9n$
Therefore the expected length of longest segment is
$(x+y+z)/(3x+2y+z)= 5.5/9= 11/18 $.
The expected length of the shortest segment is
$x/(3x+2y+z) = 1/9$.
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
$endgroup$
A more intuitive answer. Let's arrange the segments from smallest to largest. Let the three segments be $x$, $x+y$ and $x+y+z$.
${rm sum of segments}$ = 1
$implies 3x + 2y + z = 1$;
subject to the constraints: $xgeqslant 0,y geqslant 0,z geqslant 0$
$implies x leqslant 1/3 , y leqslant 1/2, z leqslant 1$.
Within these limits, we can assume $x$,$y$ and $z$ can take on any values as long as we renormalize the total length to be equal to 1, sort of building the larger string from its constituent parts. These relative limits are equivalent to the following:
Let $x$ be chosen randomly among a pool from $[0,2n]$, $y$ be chosen randomly from a pool $[0,3n]$ and $z$ from a pool $[0,6n]$ where $(x,y,z,n)$ $in$ $mathbb R$.
Expected value of $x = n$, expected value of $y = 1.5n$ and expected value of $z = 3n$.
Expected length of longest segment = $x+y+z = 5.5n$
Expected total length = $3x+2y+z = 9n$
Therefore the expected length of longest segment is
$(x+y+z)/(3x+2y+z)= 5.5/9= 11/18 $.
The expected length of the shortest segment is
$x/(3x+2y+z) = 1/9$.
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
edited Jul 22 '18 at 15:21
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
answered Apr 22 '17 at 15:47
Rahul MadhavanRahul Madhavan
6913
6913
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
add a comment |
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
How do you know that the expected length of the longest segment is x+y+z?
$endgroup$
– Ferdinando Randisi
Feb 25 '18 at 21:13
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
That is part of the formulation. The three segments are taken to be x, x+y and x + y + z. Given the expected values of x, y and z, the expected value of the longest segment, x + y + z, is 5.5n
$endgroup$
– Rahul Madhavan
Mar 5 '18 at 5:00
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
$begingroup$
I am wondering why is 3*E(x)+2*E(y)+E(z) != 6n (total length), can you please help me with an intuitive explanation?
$endgroup$
– Jaydev
Aug 2 '18 at 20:33
add a comment |
$begingroup$
Neat as it is, I don't think Rahul's answer can be correct. If we have $3x+2y+z=1$ and $3x+2y+z=9n$, then $n=1/9$, which means $x leq 2/9$, which can't be right, as one solution is all pieces being of length 1/3 (however unlikely this exact solution may be, $x$ can take values in $(2/9,1/3]$).
Stefan's answer is wrong because the probability of any given point on the stick being in the longest piece (when cut in 2) is not uniform. That can be seen by considering the point halfway along, which is always in the longest piece. You can find the probability density function for the likelihood of any given point being in the longer half, then integrate to get the answer below.
My preferred solution is to let the cuts be at $X, Y$, with $Y gt X$:
Image of cut positions
Then each piece is equally likely to be the longest, and the expected length of the longest piece doesn't depend on which piece we choose. Then we can calculate $mathop{mathbb{E}}(X|X text{ is the longest piece} )$.
We have the three inequalities:
$$X gt Y-X implies Y < 2X$$
$$X gt 1-Y implies Y > 1-X$$
and, from our setup,
$$Y gt X$$
These can be represented by the following diagram:
Diagram of inequalities
Then the area satisfying our inequalities is the two triangles A and B. So we wish to find the expected value of $X$ within this area.
The expected value of $X$ in A is $bar{X}_A = frac{1}{2}-frac{1}{3}(frac{1}{2}-frac{1}{3}) = frac{8}{18}$.
The expected value of $X$ in B is $bar{X}_B = frac{1}{2}+frac{1}{3}(frac{1}{2}) = frac{4}{6} = frac{12}{18}$
The area of A is $A_A = frac{1}{2} times frac{1}{2}times (frac{1}{2}-frac{1}{3}) = frac{1}{24}$.
The area of B is $A_B = frac{1}{2} times frac{1}{2}times frac{1}{2} = frac{1}{8} = frac{3}{24} = 3 A_A$.
So $mathop{mathbb{E}}(X|X text{ is the longest piece} ) = frac{tfrac{8}{18} + 3left(tfrac{12}{18}right)}{4} = frac{11}{18}$
(Apologies for the comments on other solutions and the links, but I haven't got a high enough reputation to comment or embed directly)
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
$endgroup$
add a comment |
$begingroup$
Neat as it is, I don't think Rahul's answer can be correct. If we have $3x+2y+z=1$ and $3x+2y+z=9n$, then $n=1/9$, which means $x leq 2/9$, which can't be right, as one solution is all pieces being of length 1/3 (however unlikely this exact solution may be, $x$ can take values in $(2/9,1/3]$).
Stefan's answer is wrong because the probability of any given point on the stick being in the longest piece (when cut in 2) is not uniform. That can be seen by considering the point halfway along, which is always in the longest piece. You can find the probability density function for the likelihood of any given point being in the longer half, then integrate to get the answer below.
My preferred solution is to let the cuts be at $X, Y$, with $Y gt X$:
Image of cut positions
Then each piece is equally likely to be the longest, and the expected length of the longest piece doesn't depend on which piece we choose. Then we can calculate $mathop{mathbb{E}}(X|X text{ is the longest piece} )$.
We have the three inequalities:
$$X gt Y-X implies Y < 2X$$
$$X gt 1-Y implies Y > 1-X$$
and, from our setup,
$$Y gt X$$
These can be represented by the following diagram:
Diagram of inequalities
Then the area satisfying our inequalities is the two triangles A and B. So we wish to find the expected value of $X$ within this area.
The expected value of $X$ in A is $bar{X}_A = frac{1}{2}-frac{1}{3}(frac{1}{2}-frac{1}{3}) = frac{8}{18}$.
The expected value of $X$ in B is $bar{X}_B = frac{1}{2}+frac{1}{3}(frac{1}{2}) = frac{4}{6} = frac{12}{18}$
The area of A is $A_A = frac{1}{2} times frac{1}{2}times (frac{1}{2}-frac{1}{3}) = frac{1}{24}$.
The area of B is $A_B = frac{1}{2} times frac{1}{2}times frac{1}{2} = frac{1}{8} = frac{3}{24} = 3 A_A$.
So $mathop{mathbb{E}}(X|X text{ is the longest piece} ) = frac{tfrac{8}{18} + 3left(tfrac{12}{18}right)}{4} = frac{11}{18}$
(Apologies for the comments on other solutions and the links, but I haven't got a high enough reputation to comment or embed directly)
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
$endgroup$
add a comment |
$begingroup$
Neat as it is, I don't think Rahul's answer can be correct. If we have $3x+2y+z=1$ and $3x+2y+z=9n$, then $n=1/9$, which means $x leq 2/9$, which can't be right, as one solution is all pieces being of length 1/3 (however unlikely this exact solution may be, $x$ can take values in $(2/9,1/3]$).
Stefan's answer is wrong because the probability of any given point on the stick being in the longest piece (when cut in 2) is not uniform. That can be seen by considering the point halfway along, which is always in the longest piece. You can find the probability density function for the likelihood of any given point being in the longer half, then integrate to get the answer below.
My preferred solution is to let the cuts be at $X, Y$, with $Y gt X$:
Image of cut positions
Then each piece is equally likely to be the longest, and the expected length of the longest piece doesn't depend on which piece we choose. Then we can calculate $mathop{mathbb{E}}(X|X text{ is the longest piece} )$.
We have the three inequalities:
$$X gt Y-X implies Y < 2X$$
$$X gt 1-Y implies Y > 1-X$$
and, from our setup,
$$Y gt X$$
These can be represented by the following diagram:
Diagram of inequalities
Then the area satisfying our inequalities is the two triangles A and B. So we wish to find the expected value of $X$ within this area.
The expected value of $X$ in A is $bar{X}_A = frac{1}{2}-frac{1}{3}(frac{1}{2}-frac{1}{3}) = frac{8}{18}$.
The expected value of $X$ in B is $bar{X}_B = frac{1}{2}+frac{1}{3}(frac{1}{2}) = frac{4}{6} = frac{12}{18}$
The area of A is $A_A = frac{1}{2} times frac{1}{2}times (frac{1}{2}-frac{1}{3}) = frac{1}{24}$.
The area of B is $A_B = frac{1}{2} times frac{1}{2}times frac{1}{2} = frac{1}{8} = frac{3}{24} = 3 A_A$.
So $mathop{mathbb{E}}(X|X text{ is the longest piece} ) = frac{tfrac{8}{18} + 3left(tfrac{12}{18}right)}{4} = frac{11}{18}$
(Apologies for the comments on other solutions and the links, but I haven't got a high enough reputation to comment or embed directly)
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
$endgroup$
Neat as it is, I don't think Rahul's answer can be correct. If we have $3x+2y+z=1$ and $3x+2y+z=9n$, then $n=1/9$, which means $x leq 2/9$, which can't be right, as one solution is all pieces being of length 1/3 (however unlikely this exact solution may be, $x$ can take values in $(2/9,1/3]$).
Stefan's answer is wrong because the probability of any given point on the stick being in the longest piece (when cut in 2) is not uniform. That can be seen by considering the point halfway along, which is always in the longest piece. You can find the probability density function for the likelihood of any given point being in the longer half, then integrate to get the answer below.
My preferred solution is to let the cuts be at $X, Y$, with $Y gt X$:
Image of cut positions
Then each piece is equally likely to be the longest, and the expected length of the longest piece doesn't depend on which piece we choose. Then we can calculate $mathop{mathbb{E}}(X|X text{ is the longest piece} )$.
We have the three inequalities:
$$X gt Y-X implies Y < 2X$$
$$X gt 1-Y implies Y > 1-X$$
and, from our setup,
$$Y gt X$$
These can be represented by the following diagram:
Diagram of inequalities
Then the area satisfying our inequalities is the two triangles A and B. So we wish to find the expected value of $X$ within this area.
The expected value of $X$ in A is $bar{X}_A = frac{1}{2}-frac{1}{3}(frac{1}{2}-frac{1}{3}) = frac{8}{18}$.
The expected value of $X$ in B is $bar{X}_B = frac{1}{2}+frac{1}{3}(frac{1}{2}) = frac{4}{6} = frac{12}{18}$
The area of A is $A_A = frac{1}{2} times frac{1}{2}times (frac{1}{2}-frac{1}{3}) = frac{1}{24}$.
The area of B is $A_B = frac{1}{2} times frac{1}{2}times frac{1}{2} = frac{1}{8} = frac{3}{24} = 3 A_A$.
So $mathop{mathbb{E}}(X|X text{ is the longest piece} ) = frac{tfrac{8}{18} + 3left(tfrac{12}{18}right)}{4} = frac{11}{18}$
(Apologies for the comments on other solutions and the links, but I haven't got a high enough reputation to comment or embed directly)
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
edited Jan 9 '18 at 19:11
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
answered Jan 9 '18 at 18:59
Ronnie268Ronnie268
6314
6314
add a comment |
add a comment |
$begingroup$
Why is this answer wrong?
Let the length of the longest segment created by the FIRST cut be $L_1$. Now consider the second cut. With probability $(1-L_1)$ it will be in the shorter segment made by the first cut, and the longest of the 3 segments will then have length $L_1$.
On the other hand, with probability $L_1$ the second cut will be in the longer first segment, and the longest of the 3 segments will then be the max of the longer segment made by the second cut, call it $L_2$, or the shorter segment made by the first cut, of length $(1-L_1)$.
This gives an expected length of the longest segment as:
$(1-L_1)L_1+L_1 max[L_2,(1-L_1)]$. If we now average this over cut positions, it is easy to reason that $L_1=3/4$, and $L_2=L_1^2=9/16$, giving the average length of the longest segment to be 39/64. This disagrees with 11/18, but only by 0.3%!
I assume there is a problem with performing the "averaging" over the $max$ function, but I don't understand why. Any feedback would be great! Thanks!!
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
$endgroup$
add a comment |
$begingroup$
Why is this answer wrong?
Let the length of the longest segment created by the FIRST cut be $L_1$. Now consider the second cut. With probability $(1-L_1)$ it will be in the shorter segment made by the first cut, and the longest of the 3 segments will then have length $L_1$.
On the other hand, with probability $L_1$ the second cut will be in the longer first segment, and the longest of the 3 segments will then be the max of the longer segment made by the second cut, call it $L_2$, or the shorter segment made by the first cut, of length $(1-L_1)$.
This gives an expected length of the longest segment as:
$(1-L_1)L_1+L_1 max[L_2,(1-L_1)]$. If we now average this over cut positions, it is easy to reason that $L_1=3/4$, and $L_2=L_1^2=9/16$, giving the average length of the longest segment to be 39/64. This disagrees with 11/18, but only by 0.3%!
I assume there is a problem with performing the "averaging" over the $max$ function, but I don't understand why. Any feedback would be great! Thanks!!
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
$endgroup$
add a comment |
$begingroup$
Why is this answer wrong?
Let the length of the longest segment created by the FIRST cut be $L_1$. Now consider the second cut. With probability $(1-L_1)$ it will be in the shorter segment made by the first cut, and the longest of the 3 segments will then have length $L_1$.
On the other hand, with probability $L_1$ the second cut will be in the longer first segment, and the longest of the 3 segments will then be the max of the longer segment made by the second cut, call it $L_2$, or the shorter segment made by the first cut, of length $(1-L_1)$.
This gives an expected length of the longest segment as:
$(1-L_1)L_1+L_1 max[L_2,(1-L_1)]$. If we now average this over cut positions, it is easy to reason that $L_1=3/4$, and $L_2=L_1^2=9/16$, giving the average length of the longest segment to be 39/64. This disagrees with 11/18, but only by 0.3%!
I assume there is a problem with performing the "averaging" over the $max$ function, but I don't understand why. Any feedback would be great! Thanks!!
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
$endgroup$
Why is this answer wrong?
Let the length of the longest segment created by the FIRST cut be $L_1$. Now consider the second cut. With probability $(1-L_1)$ it will be in the shorter segment made by the first cut, and the longest of the 3 segments will then have length $L_1$.
On the other hand, with probability $L_1$ the second cut will be in the longer first segment, and the longest of the 3 segments will then be the max of the longer segment made by the second cut, call it $L_2$, or the shorter segment made by the first cut, of length $(1-L_1)$.
This gives an expected length of the longest segment as:
$(1-L_1)L_1+L_1 max[L_2,(1-L_1)]$. If we now average this over cut positions, it is easy to reason that $L_1=3/4$, and $L_2=L_1^2=9/16$, giving the average length of the longest segment to be 39/64. This disagrees with 11/18, but only by 0.3%!
I assume there is a problem with performing the "averaging" over the $max$ function, but I don't understand why. Any feedback would be great! Thanks!!
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
answered Jul 29 '16 at 23:37
Stefan JaniszewskiStefan Janiszewski
311
311
add a comment |
add a comment |
$begingroup$
A similar, but a bit more complex problem, that highlights how important it is to understand the exact wording of a formulation:
cut a rope (or break a rod) at a random point. Set aside a piece. Cut (or break) the remaining piece at another random point.
Question is the same (expected length of the longest segment).
That's how I initially understood the problem..
Got stuck in algebra and closed-form anti-derivatives..
Same principle, heavier calculations.
I got an answer $2ln2 - ln3 + 3/8 approx 0.663$, that matches what a MatLab script gives for $1000$ tests.
edited Jan 16 at 21:27
dantopa
6,67442245
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
$endgroup$
add a comment |
$begingroup$
A similar, but a bit more complex problem, that highlights how important it is to understand the exact wording of a formulation:
cut a rope (or break a rod) at a random point. Set aside a piece. Cut (or break) the remaining piece at another random point.
Question is the same (expected length of the longest segment).
That's how I initially understood the problem..
Got stuck in algebra and closed-form anti-derivatives..
Same principle, heavier calculations.
I got an answer $2ln2 - ln3 + 3/8 approx 0.663$, that matches what a MatLab script gives for $1000$ tests.
edited Jan 16 at 21:27
dantopa
6,67442245
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
$endgroup$
add a comment |
$begingroup$
A similar, but a bit more complex problem, that highlights how important it is to understand the exact wording of a formulation:
cut a rope (or break a rod) at a random point. Set aside a piece. Cut (or break) the remaining piece at another random point.
Question is the same (expected length of the longest segment).
That's how I initially understood the problem..
Got stuck in algebra and closed-form anti-derivatives..
Same principle, heavier calculations.
I got an answer $2ln2 - ln3 + 3/8 approx 0.663$, that matches what a MatLab script gives for $1000$ tests.
edited Jan 16 at 21:27
dantopa
6,67442245
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
$endgroup$
A similar, but a bit more complex problem, that highlights how important it is to understand the exact wording of a formulation:
cut a rope (or break a rod) at a random point. Set aside a piece. Cut (or break) the remaining piece at another random point.
Question is the same (expected length of the longest segment).
That's how I initially understood the problem..
Got stuck in algebra and closed-form anti-derivatives..
Same principle, heavier calculations.
I got an answer $2ln2 - ln3 + 3/8 approx 0.663$, that matches what a MatLab script gives for $1000$ tests.
edited Jan 16 at 21:27
dantopa
6,67442245
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
edited Jan 16 at 21:27
dantopa
6,67442245
edited Jan 16 at 21:27
dantopa
6,67442245
edited Jan 16 at 21:27
dantopa
6,67442245
6,67442245
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
answered Oct 26 '16 at 17:30
OverInflatedWalrusOverInflatedWalrus
212
212
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f14190%2faverage-length-of-the-longest-segment%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n
$endgroup$
– Yudong Tang
Mar 23 '14 at 20:59