Probability & Mean - How many birds land on wall if none land <1ft from one another

Question

Suppose there is a wall 28ft in length.  Birds land on the wall one at a time but will not land within 1 foot on either side of another bird's center.  The birds land with a uniform distribution within the spaces available for landing.  Let X be the number of birds on the wall when no more birds can land.  What is E[X]? 

My first thought was to find the expected location of the leftmost bird (after no more can land) and make my way to the right.  This location will always be 0-1feet from the end, but my first thought, that this location will be uniformly distributed between 0-1, quickly seemed incorrect: whenever a bird lands 1-2ft from the end and has no bird to its left, the expected position of the leftmost bird (when no more can land) will be closer to 0 than to 1.

I considered trying  the expected distance between two birds, which will always be 1-2ft.  I have doubts that this distance will be uniformly distributed between 1-2 for similar reasons: that the sequence of landings plays a role which makes this distribution something other than uniform.  On the other hand, even if the distribution isn't uniform, there is still something intuitive about the idea that the mean distance is 1.5, with the exception of the last two birds at each end, which would tend to be less than 1.5.

That's what I have at this point.

Answer 1

I don't think there's a closed form solution.

Let $f(x)$ be the expected number of birds that land between two adjacent birds spaced $x$ feet apart. Note that the answer to your problem is given by $f(30)$, since two birds spaced 30 feet apart would allow birds to fill the 28 feet between them.

The function $f(x)$ can be expressed as a recursive integral. If $y\in(1,x-1)$ is the point where the next bird lands between birds at points 0 and $x$, we can write: $$f(x) = 1+\frac1{x-2}\left[\int_1^2 f(x-y)dy + \left(\int_2^{x-2}[f(y)+f(x-y)]\right)dy + \int_{x-2}^{x-1} f(y)dy\right]$$

On the RHS, the "$1+$" term represents our most recent arrival, and the next three terms account for, respectively, the expected number of additional birds landing to the right of a bird $y$ that is spaced too close to bird $0$ to allow any birds on its left, then the birds landing respectively to the left and right of a bird somewhere in the middle, and finally the birds landing to the left of a bird spaced to close to bird $x$ to allow any birds to its right.

Incredibly, this simplifies to the integral: $$f(x) = 1+\frac2{x-2}\int_2^{x-1}f(y)dy$$ and we can write it as what's called a "delay differential equation": $$(x-2)f'(x)+f(x)-1 = 2f(x-1)$$ This actually holds for $x>2$, since we have $f(x)=0, x\in[0,2]$.

These equations can be solved by piecewise differential equations. For example, for $x\in(2,3]$, the equation can be written: $$(x-2)f'(x) + f(x)-1=0$$ which gives solution (with starting condition $f(2)=0$) of: $$f(x) = 1,\quad x \in(2,3]$$ which is what we expect -- between two birds 2-3 feet apart, you can place exactly one bird. So, that's a good start, but for $x\in(3,4]$, the equation becomes: $$(x-2)f'(x)+f(x)-1=2$$ which has solution (with starting condition $f(3)=1$) of: $$f(x)=\frac{3x-8}{x-2}, \quad x \in(3,4]$$

This also makes sense, as the placement of the first bird between two birds four feet apart always allows exactly one additional bird to be placed, while two birds placed 3.5 feet apart always allow placement of the first bird, but then allow placement of a second bird only two-thirds of the time (so the expected number is $\tfrac13 1 + \frac23 2 = \tfrac53)$.

With solutions this simple, you'd think we'd have to fall into a pattern, but: $$f(x)=\frac{7x-4\log(x-3)-24}{x-2}, \quad x \in(4,5]$$ and the next interval has some nasty polylogarithmic function in it.

So, maybe someone who knows a lot more about these classes of equations can help, but I think you might be out of luck, unless you just want a numerical solution.

Update #1: Here's how we go from $(3,4]$ to $(4,5]$. Using the delay differential equation, for any $x\in(4,5]$, we can write: $$(x-2)f'(x)+f(x)-1 = 2\left[\frac{3(x-1)-8}{(x-1)-2}\right]$$ All I've done here is written out $f(x-1)$ using the known form of $f$ on the interval $(3,4]$. Plugging this into Wolfram Alpha, I get the differential equation solution: $$ f(x) = \frac{c_1}{2-x} + \frac{7x}{x-2} - \frac{21}{x-2} - \frac{4\log(x-2)}{x-2} $$ Solving for the constant $c_1$ that makes $f$ continuous at the point $x=4$ (i.e., $f(4) = 2$), I get the final form for $f(x)$ on the interval $(4,5]$.

Update #2: And here's how to calculate a numerical solution. The idea is to calculate $f$ sequentially at $f(3+\delta), f(3+2\delta), \dots$ using the numerical integration: $$f(x) = f(x-\delta) + \delta f'_{approx}$$ using an approximate derivative calculated from the delayed differential equation: $$f'_{approx} = \frac{2f(x-1)-f(x-\delta)+1}{x-2}$$

The following R program plots the theoretical curves up to $x=5$ in black and the numerical approximation up to $x=10$ in red.

max_x <- 10

f1 <- function(x) 0*x
f2 <- function(x) 1+0*x
f3 <- function(x) (3*x-8)/(x-2)
f4 <- function(x) (7*x-4*log(x-3)-24)/(x-2)

curve(f1(x), 0, 2, xlim=c(0,max_x), ylim=c(0,max_x))
curve(f2(x), 2, 3, add=TRUE)
curve(f3(x), 3, 4, add=TRUE)
curve(f4(x), 4, 5, add=TRUE)

along <- function(frac, a, b) {
    (1-frac)*a + frac*b
}

delta <- 1e-5
i <- function(x) floor((x-3)/delta)+1
f_store <- numeric(i(max_x))
f <- function(x) {
    if (x <= 2) {
        0
    } else if (x <= 3) {
        1
    } else {
        ix <- i(x)
        along(x-delta*ix, f_store[ix], f_store[ix+1])
    }
}
f_store[i(3)] <- 1
for (ix in (i(3)+1):i(max_x)) {
    x <- (ix-1)*delta+3
    df <- (2*f(x-1)-f_store[ix-1]+1)/(x-2)
    f_store[ix] <- f_store[ix-1]+delta*df
}
xs <- seq(0,20,length=1000)
ys <- sapply(xs, f)
lines(xs,ys, col="red")

The approximation looks pretty good:

Getting back to your original problem. The expected number of birds on a 28-foot line is $f(30)$, which using my numerical approximation is $f(30)=21.43$, a result I was able to verify independently with a direct simulation approach.