12

So my buddy claims that if I split a chocolate bar at random into two pieces, then the expected size of the larger piece is $\frac{3}{4}$ of the bar. I can't figure out how he came up with this value...

Can someone explain this? If you can, can you provide some kind of a proof?

p.s. it would be helpful to think of this chocolate bar as a 1D array :)

UPDATE

Imagine the candy bar is a world-famous chocolate bar, the ones that are broken into chunks. However, this special chocolate bar has n chunks. If we broke the chocolate bar randomly along these chunks, what would the expected size of the larger chunk be? My buddy claims it to be $\leq{\frac{3}{4}}$.

Hristo
  • 617

2 Answers2

18

The larger piece is always between 1/2 and 1. If the break is uniformly distributed along the bar, the larger piece is uniformly distributed between 1/2 and 1. This gives the expected value of 3/4.

Added when we have break lines: If there are $n$ pieces, there are $n-1$ break lines, all equally probable. If $(n-1)$ is even, the size of the largest piece has chance $\frac{2}{n-1}$ of being any step between $\frac{n+1}{2n}$ and $\frac{n-1}{n}$, so the expectation is $\frac{3n-1}{4n}$. If $(n-1)$ is odd there is $\frac{1}{n-1}$ chance the "larger" piece is $\frac{1}{2}$ and $\frac{2}{n-1}$ for each value between $\frac{n+1}{2n}$ and $\frac{n-1}{n}$, giving $\frac{3n-4}{4n-4}$ as the expected value. As stated in other answers, this is always below $\frac{3}{4}$, but approaches that as $n \to \infty$

Ross Millikan
  • 374,822
  • 2
    Chocolate bars are often segmented and, reading between the lines of the question, it is assumed that the break is in between segments (from the comment about thinking of it as a 1D array). So, it won't be uniformly distributed, and the expected size of the largest piece is strictly less than 3/4 of the bar. So, the buddy was wrong. – George Lowther Mar 27 '11 at 22:57
  • @George... you're right! Check out my update up above... – Hristo Mar 27 '11 at 22:59
  • @Ross... thank you for that detailed explanation. I need to look through it a little more detail to understand what's going on, but on a basic level I think I understand what's going. Thanks! – Hristo Mar 28 '11 at 03:05
  • I had a small error in my calculation for $n$ even, and agree with Shai Covo. Corrected. In essence, you break at the middle with probability $\frac{1}{n-1}$ and get $\frac{1}{2}$ or you don't break in the middle with probability $\frac{n-2}{n-1}$ and get on average $\frac{3}{4}$, again by symmetry. – Ross Millikan Mar 29 '11 at 17:23
10

Define $Y = \max \{ U,1 - U\} $, where $U$ is a uniform$(0,1)$ random variable. Then, by the law of total probability (conditioning on $U$), $$ {\rm E}(Y) = \int_0^1 {{\rm E}(Y|U = u)du} = \int_0^{0.5} {(1 - u)du} + \int_{0.5}^1 {udu} = \frac{3}{4} $$

EDIT. The discrete case is even more elementary, but involves more calculations.

If $n$ (the number of chunks) is odd (and greater than $1$), then the ratio is equal to $k/n$, $k=n-1,n-2,\ldots,(n+1)/2$, with probability $2/(n-1)$ (by symmetry). Hence, its expectation is equal to $$ \sum\limits_{k = (n + 1)/2}^{n - 1} {\frac{k}{n}} \frac{2}{{n - 1}} = \frac{{3n - 1}}{{4n}} < \frac{3}{4}. $$ If $n$ is even, then the ratio is equal to $k/n$, $k=n-1,n-2,\ldots,n/2+1$, with probability $2/(n-1)$ (again, by symmetry), and to $(n/2)/n = 1/2$ with probability $1/(n-1)$. Hence, its expectation is equal to $$ \sum\limits_{k = n/2 + 1}^{n - 1} {\frac{k}{n}} \frac{2}{{n - 1}} + \frac{1}{{2(n - 1)}} = \frac{{3n - 4}}{{4n - 4}} < \frac{3}{4}. $$ It is interesting to note that $$ \frac{{3n - 4}}{{4n - 4}} = \frac{{3(n - 1) - 1}}{{4(n - 1)}}. $$ Thus, the expectations for $n$ and $n-1$ are equal for $n > 2$ even.

Shai Covo
  • 24,077
  • @Shai... I understand your solution and I understand it relates to a non-chunky chocolate bar. Do you know how to solve this in relation to an array-like chocolate bar? – Hristo Mar 27 '11 at 23:06
  • @Shai... actually, I think you're still correct because when n is very large, this would still evaluate to ~3/4 right? Maybe not exact, but I'm looking for $\leq{3/4}$. – Hristo Mar 27 '11 at 23:08
  • 2
    @Hristo: yes, for large $n$ that should evaluate to approximately $3/4$. – Shai Covo Mar 27 '11 at 23:13
  • I can't comment on Shai's so I'm posting this. First of all, your friend is very wise.

    Onto the question.

    The continuous distribution that Shai Covo used is essentially the case where the number of chunks is infinity. This is in fact the worst case, which emphasizes that the expected size is $\leq{3/4}$ for all n.

     – user8765 Mar 27 '11 at 23:13
  • That rather depends on whether an $n$-chunk bar has $n-1$ places to break it or $n+1$, i.e. whether or not the largest piece can be the whole bar and whether or not the smallest can be nothing. – Henry Mar 27 '11 at 23:54
  • @Henry: I don't think the end can be a breakpoint, and my answer is in that spirit. I believe that if you allow breaks at the end, it will be always $\ge 3/4$, again going to 3/4 as $n\to \infty$. – Ross Millikan Mar 28 '11 at 00:07
  • @Ross Millikan: I recognise that, which is why I commented here rather than on you answer. Sadly, I do know people who "share" their chocolate bars so extremely ungenerously. – Henry Mar 28 '11 at 00:17
  • @Henry: LOL. If you come visit, I promise you at least 1/n of my chocolate bar. – Ross Millikan Mar 28 '11 at 00:21
  • @Henry & @Ross... do you guys know each other...? – Hristo Mar 28 '11 at 03:00
  • @Hristo: For the finite case, consider $\sum\limits_{k = 1}^{n - 1} {\frac{{\max { k,n - k} }}{n}\frac{1}{{n - 1}}}$. – Shai Covo Mar 28 '11 at 06:46
  • @Hristo: As I will show later on today, the answer for the finite case is $(3n-1)/(4n)$ for $n$ odd, and $(3n-4)/(4n-4)$ for $n$ even (which can be written as $[3(n-1)-1]/[4(n-1)]$, thus similar to the odd case). – Shai Covo Mar 29 '11 at 10:33