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