3
$\begingroup$

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.

$\endgroup$
4
  • 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, 2013 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$ Apr 12, 2013 at 23:50
  • 2
    $\begingroup$ Also, this hasn't got anything to do with graph theory. $\endgroup$
    – nvcleemp
    Apr 13, 2013 at 5:53
  • 1
    $\begingroup$ Keyword to search for: online bin packing, next fit. $\endgroup$ Apr 15, 2013 at 19:20

1 Answer 1

7
$\begingroup$

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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