Let me explain what I mean:

  • The width of the average person varies, perhaps with a normal distribution.
  • Given a specific variance, how many people (on average) can sit side-by-side on a bench of a given length?

What would the graph of this look like? If Length is the x-axis, and Average Number of People is the y-axis, then I would imagine that the graph would start out looking like a very rough floor function, but as the length increases the function would approach linearity. In other words, at short lengths the average number of people would increase in almost discreet steps. At longer lengths, the variance in widths would cause the growth to even out. Is this correct? Is there a mathematical way of expressing this? Thank you very much for your help.

  • 2
    $\begingroup$ This site is not meant for homework help or casual questions. It is intended for research mathematics. The answer to your question lies, simply, with linearity of expectation. $\endgroup$ – fkenter Apr 12 '13 at 22:54
  • 3
    $\begingroup$ No, this is not simply a matter of linearity of expectation. The question is how much overshoot there is. I think the distribution of the overshoot is sometimes called the ladder height distribution. $\endgroup$ – Douglas Zare Apr 12 '13 at 23:50
  • 2
    $\begingroup$ Also, this hasn't got anything to do with graph theory. $\endgroup$ – nvcleemp Apr 13 '13 at 5:53
  • 1
    $\begingroup$ Keyword to search for: online bin packing, next fit. $\endgroup$ – Zsbán Ambrus Apr 15 '13 at 19:20

Assume that the process stops when someone can't fit.

I believe the distribution of the amount of overshoot is known as a ladder height distribution, and that this is in Feller's classic text, but I don't have that handy.

Let $f(x)$ be the expected number of people up to and including the first who is turned away because there is no room. Let $\mu$ be the expected value of the distribution of widths. Let $m_2$ be the second moment which we'll assume is finite. If you rule out lattice distributions, so that the probability of $n$ people exactly fitting goes to $0$, then $$\begin{eqnarray} f(x) & = & \frac{x}{\mu} + \frac{m_2}{2\mu^2} + o(1) \newline & = & \frac{x}{\mu} + \frac{\sigma^2}{2\mu^2} + \frac{1}{2} + o(1). \end{eqnarray}$$

The number of people before the last is one lower, of course. I think when the second moment is infinite, the difference between $f(x)$ and $x/\mu$ is unbounded, and if the mean doesn't exist, then $f(x)$ is sublinear.

I posted a sketch of a proof assuming the distribution is continuous on a poker site. A more intuitive heuristic is to ask what happens if you choose the finish line randomly. How much does a width $w$ which occurs with probability $p$ contribute to the average overshoot? The chance that the finish line is within this width is $pw/\mu$, and when a width $w$ causes the overshoot, the average overshoot is $w/2$. So, the contribution to the average overshoot is $pw^2 / (2 \mu)$. Integrating over all widths gives an average overshoot of $\frac{m_2}{2\mu}$. The extra factor of $\mu$ in the denominator occurs because an overshoot of $y$ means you take an extra $y/\mu$ samples.

A related problem asks for the expected number of straws it takes to break a camel's back, if the straws have weights which are uniformly distributed on $[0,1]$, and the camel can hold a weight of $x$. If $x=1$, the probability that $n$ straws have weight less than $1$ is $1/n!$, so the expected number of straws is $\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!}+... = e$. Asymptotically, it takes an average of about $2x+2/3 = \frac{x}{1/2} + \frac{1/3}{2*1/2^2}$.

  • $\begingroup$ +1.. the camel example reminds me of that joke about spherical chickens :) $\endgroup$ – Ollie Apr 15 '13 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.