Baggage on a conveyor belt

[bonanova]

At a busy airport a conveyor belt stretches from the runway, where all the planes land, to the baggage claim area inside the terminal. At any given time it may contain hundreds of pieces of luggage, placed there at what we may consider to be random time intervals. Each bag has two neighbors, one of which is nearer to it than the other. Each segment of the belt is bounded by two bags, which may or may not be near neighbors (to each other.)

On average, what fraction of the conveyor belt is not bounded by near-neighbors?

Example:

----- belt segment bounded by near neighbors
===== belt segment not bounded by near neighbors

... --A-----B==========C---D--------E=============F---G-H---I-- ...

[plasmid]

Ah, the hospital's rule. Of course. I vaguely remember that from high school.

More importantly, I also found out that my memory of integration by parts was faulty, and that seems to have been the real issue. From the top:

Spoiler

If we’re dealing with a Poisson distribution where the probability of having an interval x between two bags is proportional to e^-x, then we need to re-calculate the probability of being a non-nearest neighbor segment. If you’re given a segment of length L, then the probability that it’s larger than an adjacent segment (or equivalently that an adjacent segment is smaller than L) is
Integral_{[x=0 to L]} e^-x / Integral_{[x=0 to infinity]} e^-x
_{[x=0 to L]} -e^-x / _{[x=0 to infinity]} -e^-x
(-e^-L + e⁰) / (-e^-infinity + e⁰)
(-e^-L + 1) / (0 + 1)
1 - e^-L
So the probability that both adjacent segments are smaller than L and therefore you have a non-nearest neighbor segment is the square of that, or
1 - 2e^-L + e^-2L

In my previous calculation, a segment would appear with uniform probability regardless of its length, but in this case the probability that you would observe a segment of length x is dependent on the value of x. To account for that, the ultimate value you want is the integral of [length of the segment] · [probability of seeing a segment of that length] · [probability that it’s a non-nearest neighbor segment] divided by the integral of [length of the segment] · [probability of seeing a segment of that length], which would be
Integral_{[x=0 to infinity]} x·e^-x·(1-2e^-x+e^-2x) / Integral_{[x=0 to infinity]} x·e^-x
Integral_{[x=0 to infinity]} xe^-x-2xe^-2x+xe^-3x / Integral_{[x=0 to infinity]} xe^-x
Split the terms in the numerator and use integration by parts to get
[-xe^-x – Integral(-e^-x) + xe^-2x – Integral(e^-2x) – 1/3 xe^-3x – Integral(-1/3 e^-3x)] / [-xe^-x – Integral(-e^-x)]
[-xe^-x – e^-x + xe^-2x – -1/2 e^-2x) – 1/3 xe^-3x – 1/9 e^-3x] / [-xe^-x – e^-x]
[-(x+1)e^-x + (x+1/2)e^-2x – (1/3 x + 1/9)e^-3x] / [-(x+1)e^-x]
When you evaluate the numerator and denominator over the range from x=0 to x=infinity, all of the terms at x=infinity go to zero because of the e^-x terms. So just take the negative of the x=0 value, and you get
[1e⁰ – 1/2 e⁰ + 1/9 e⁰] / [1e⁰]
[1 – 1/2 + 1/9] / 1
11/18

 

[Donald Cartmill]

Spoiler

 

Randomly placed is NOT sufficient info to establish the   % of unbounded belt on the in going (top side ) half of the belt . Also while implied there is no mention  of any belt length segment   Therefore the avg will b.e over 50%.  How much over 50%.  Assuming each piece of luggage as placed on belt was 2 ft wide.     2nd piece is 1 inch from 1st, and the 3rd is 2 inches away;  Then the  4th must be at least 3 inches away from the 3rd and becomes the 1st in the next segment of luggage . if this were to repeat on and on, then the % of unbound belt would be 3 inches divided by the total length of the segment.  i,e, (24 +1 + 24 + 2 + 24 +3 ) = 78;  Therefore 3 /78 =0.03845 or 3.8% for the top belt and in the scenario added to the 50% = 53.8 % This would be the lowest % using a full inch as a minimum unit.

[bonanova]

Belt "segment" just refers to portions of belt between adjacent bags. Top or bottom is not an issue. Consider bags are randomly placed  points on a line if you like.  The fraction of length that is not a near-neighbor segment changes with time. To imply a limit, the OP asks "on average" over time.

[bonanova]

One approach is to

Spoiler

simulate the bags with a random number generator.

Then it would be helpful to know that the result is

Spoiler

a rational number.

 

[CaptainEd]

Ok I tried using random numbers, got a fraction...

.8237

Bonanova, Since you said rational, I’ll guess 5/6. I’ll bet you have a simple but deep proof. I’m eager to see it! I can see that it has to be more than 2/3, because a nearest neighbor gap is smaller than either adjacent gap, hence is less than 1/3.

[bonanova]

On 2/19/2018 at 12:06 AM, CaptainEd said:

Ok I tried using random numbers, got a fraction...

 

  Hide contents

 

.8237

Bonanova, Since you said rational, I’ll guess 5/6. I’ll bet you have a simple but deep proof. I’m eager to see it! I can see that it has to be more than 2/3, because a nearest neighbor gap is smaller than either adjacent gap, hence is less than 1/3.

 

 

Gah! Mine was not a useful clue. The denominator (greater than 6 but not huge) is too large for a simulation to tell you the fraction. Also I think your simulation value is high. But you're thinking in the right direction. Here may be more useful clues.

Spoiler

The intervals can be classified small if both neighboring intervals are larger, large if both neighboring intervals are smaller, and medium otherwise.

Spoiler

Every interval has an equal probability of being large, medium or small. i.e. for every interval P(small) = P(medium) = P(large) = 1/3.

Spoiler

The (Poisson) probability that any interval is smaller than say a distance x can be taken, with appropriate scaling, to be 1 - e^-x.

Spoiler

Part of what is needed is the expected size <large> of a large interval.

 

[CaptainEd]

Here’s my attempt at an analytical solution

Instead of a quasi infinite belt, I chose a belt of length 1, and instead of a Poisson distribution, I chose uniform distribution of segment lengths.

Consider a segment of length x in (0,1). The probability of its left neighbor being larger is (1-x), the probability of it being smaller is x. 
A segment is non-nearest if at least one of its neighbors is smaller, so the Probability of a segment being non nearest is
P(only first neighbor is smaller) + p(only second neighbor is smaller
+ p( both neighbors are smaller

Pnn(x) = 2x*(1-x)+x^2

= 2x -2x^2 + x^2 = 2x - x^2
Integrate for x =0,1
2x^2/2 - x^3/3
2/2-1/3
1-1/3 =2/3

[bonanova]

4 hours ago, CaptainEd said:

Here’s my attempt at an analytical solution

  Hide contents

A segment is non-nearest if at least one of its neighbors is smaller,

 

Spoiler

Consider segment D--------E in the OP

 

[CaptainEd]

I see, I didn’t pay attention. I really want to count only segments that are surrounded by shorter segments. 

[bonanova]

On 2/23/2018 at 10:44 AM, CaptainEd said:

I see, I didn’t pay attention. I really want to count only segments that are surrounded by shorter segments. 

Yup. And a bit of possibly helpful thinking:

Spoiler

While (see previous post for definitions) small, medium and large intervals (segments) are equal in (expected) number, their combined lengths of course will not be equal: the expected length of the large intervals is clearly greater than 1/3. But it's not intuitively clear whether it reaches 2/3.

Edit: The math gets a little demanding here. Integrals and stuff.

[plasmid]

Spoiler

Suppose you have one guy that’s responsible for putting the bags on the conveyor belt, and the amount of time it takes him to put each subsequent bag on the belt is randomly drawn from a uniform distribution from 0 to 1 second. Also say the conveyor belt is moving at 1 meter per second to make the math easier. So you can work with a string of distances: x₁, x₂, x₃, … and we’re looking for the ratio of (the sum of all terms x_n where x_n > x_n-1 and x_n > x_n+1) divided by (the sum of all terms x_n regardless of whether it's a non-nearest neighbor segment).

For any given value of x_n, the probability that x_n > x_n-1 is simply the value of x_n (since we’re dealing with a uniform distribution of values over a range from 0 to 1), and similarly the probability that x_n > x_n+1 is x_n (since these numbers are randomly generated independently of each other). So the probability that x_n is a non-nearest neighbor segment is the product of those two, or x_n².

Since the length of each segment is generated from a uniform distribution from 0 to 1, we can do an easy integral. To calculate the fraction of the conveyor belt that’s covered by non-nearest neighbor segments, I think we would want to take the integral of [length of the segment] · [probability that it’s a non-nearest neighbor segment] (which is x · x² = x³) and divide that by the integral of [length of the segment].
Int_{[x=0 to 1]} (x³ dx) / Int_{[x=0 to 1]} (x dx)
_{[x=0 to 1]} (x⁴/4) / _{[x=0 to 1]} (x²/2)
(1/4) / (1/2) = 1/2

That answer would very likely change if you used a different method to generate random distances between suitcases on the conveyor belt.

 

[bonanova]

On 3/3/2018 at 10:52 AM, plasmid said:

  Hide contents

Suppose you have one guy that’s responsible for putting the bags on the conveyor belt, and the amount of time it takes him to put each subsequent bag on the belt is randomly drawn from a uniform distribution from 0 to 1 second. Also say the conveyor belt is moving at 1 meter per second to make the math easier. So you can work with a string of distances: x₁, x₂, x₃, … and we’re looking for the ratio of (the sum of all terms x_n where x_n > x_n-1 and x_n > x_n+1) divided by (the sum of all terms x_n regardless of whether it's a non-nearest neighbor segment).

For any given value of x_n, the probability that x_n > x_n-1 is simply the value of x_n (since we’re dealing with a uniform distribution of values over a range from 0 to 1), and similarly the probability that x_n > x_n+1 is x_n (since these numbers are randomly generated independently of each other). So the probability that x_n is a non-nearest neighbor segment is the product of those two, or x_n².

Since the length of each segment is generated from a uniform distribution from 0 to 1, we can do an easy integral. To calculate the fraction of the conveyor belt that’s covered by non-nearest neighbor segments, I think we would want to take the integral of [length of the segment] · [probability that it’s a non-nearest neighbor segment] (which is x · x² = x³) and divide that by the integral of [length of the segment].
Int_{[x=0 to 1]} (x³ dx) / Int_{[x=0 to 1]} (x dx)
_{[x=0 to 1]} (x⁴/4) / _{[x=0 to 1]} (x²/2)
(1/4) / (1/2) = 1/2

That answer would very likely change if you used a different method to generate random distances between suitcases on the conveyor belt.

 

The answer probably does change with the nature of the distances.

Spoiler

Your answer seems lower than expected.

Spoiler

I wonder what you'd calculate assuming a Poisson distribution, where the probability that any interval is smaller than say a distance x can be taken, with appropriate scaling, to be 1 - e^-x. Equivalently, the probability density function for an interval of distance x would just be e^-x.

 

 

[plasmid]

Does not compute when I try a Poisson distribution. I might be doing something wrong.

Spoiler

If we’re dealing with a Poisson distribution where the probability of having an interval x between two bags is proportional to e^-x, then we need to re-calculate the probability of being a non-nearest neighbor segment. If you’re given a segment of length L, then the probability that it’s larger than an adjacent segment (or equivalently that an adjacent segment is smaller than L) is
Integral_{[x=0 to L]} e^-x / Integral_{[x=0 to infinity]} e^-x
_{[x=0 to L]} -e^-x / _{[x=0 to infinity]} -e^-x
(-e^-L + e⁰) / (-e^-infinity + e⁰)
(-e^-L + 1) / (0 + 1)
1 - e^-L
So the probability that both adjacent segments are smaller than L and therefore you have a non-nearest neighbor segment is the square of that, or
1 - 2e^-L + e^-2L

In my previous calculation, a segment would appear with uniform probability regardless of its length, but in this case the probability that you would observe a segment of length x is dependent on the value of x. To account for that, the ultimate value you want is the integral of [length of the segment] · [probability of seeing a segment of that length] · [probability that it’s a non-nearest neighbor segment] divided by the integral of [length of the segment] · [probability of seeing a segment of that length], which would be
Integral_{[x=0 to infinity]} x·e^-x·(1-2e^-x+e^-2x) / Integral_{[x=0 to infinity]} x·e^-x
Integral_{[x=0 to infinity]} xe^-x-2xe^-2x+xe^-3x / Integral_{[x=0 to infinity]} xe^-x
Split the terms in the numerator and use integration by parts to get
(-xe^-x Integral -e^-x +  xe^-2x Integral e^-2x – (x/3)e^-3x Integral (-1/3)e^-3x) / (-xe^-x Integral -e^-x)
(-xe^-x e^-x +  xe^-2x (-1/2)e^-2x – (x/3)e^-3x (1/9)e^-3x) / (-xe^-x e^-x)
(-xe^-2x - (x/2)e^-4x – (x/27)e^-6x) / (-xe^-2x)
Taking that integral from 0 to infinity then makes all of the e^-nx terms be one at x=0 and zero at x=infinity. But then at x=infinity, you end up with terms that are infinity times zero :/

 

Edited March 10, 2018 by plasmid

[plasmid]

On 3/10/2018 at 6:53 AM, plasmid said:

Does not compute when I try a Poisson distribution. I might be doing something wrong.

  Hide contents

If we’re dealing with a Poisson distribution where the probability of having an interval x between two bags is proportional to e^-x, then we need to re-calculate the probability of being a non-nearest neighbor segment. If you’re given a segment of length L, then the probability that it’s larger than an adjacent segment (or equivalently that an adjacent segment is smaller than L) is
Integral_{[x=0 to L]} e^-x / Integral_{[x=0 to infinity]} e^-x
_{[x=0 to L]} -e^-x / _{[x=0 to infinity]} -e^-x
(-e^-L + e⁰) / (-e^-infinity + e⁰)
(-e^-L + 1) / (0 + 1)
1 - e^-L
So the probability that both adjacent segments are smaller than L and therefore you have a non-nearest neighbor segment is the square of that, or
1 - 2e^-L + e^-2L

In my previous calculation, a segment would appear with uniform probability regardless of its length, but in this case the probability that you would observe a segment of length x is dependent on the value of x. To account for that, the ultimate value you want is the integral of [length of the segment] · [probability of seeing a segment of that length] · [probability that it’s a non-nearest neighbor segment] divided by the integral of [length of the segment] · [probability of seeing a segment of that length], which would be
Integral_{[x=0 to infinity]} x·e^-x·(1-2e^-x+e^-2x) / Integral_{[x=0 to infinity]} x·e^-x
Integral_{[x=0 to infinity]} xe^-x-2xe^-2x+xe^-3x / Integral_{[x=0 to infinity]} xe^-x
Split the terms in the numerator and use integration by parts to get
(-xe^-x Integral -e^-x +  xe^-2x Integral e^-2x – (x/3)e^-3x Integral (-1/3)e^-3x) / (-xe^-x Integral -e^-x)
(-xe^-x e^-x +  xe^-2x (-1/2)e^-2x – (x/3)e^-3x (1/9)e^-3x) / (-xe^-x e^-x)
(-xe^-2x - (x/2)e^-4x – (x/27)e^-6x) / (-xe^-2x)
Taking that integral from 0 to infinity then makes all of the e^-nx terms be one at x=0 and zero at x=infinity. But then at x=infinity, you end up with terms that are infinity times zero :/

 

SMH, continuing from that last line of formula...

Spoiler

(-xe^-2x - (x/2)e^-4x – (x/27)e^-6x) / (-xe^-2x)
1 + (1/2)e^-2x + (1/27)e^-4x
And getting the value of that integral over the range 0 to infinity is easy. [Infinity value] – [zero value] is
[1 + 0 + 0] – [1 + (1/2) + (1/27)] = -29/54

I must have gotten positive/negative signs flipped somewhere, but I can’t find where.

Edit: Nevermind, I think you have to calculate the value over the range of integration for the numerator and denominator separately, I don't think you can just divide through like that. And after looking it up, those limits go to zero so I've got an indeterminate 0/0 still.

Edited March 11, 2018 by plasmid

[bonanova]

On 3/11/2018 at 12:44 PM, plasmid said:

SMH, continuing from that last line of formula...

  Reveal hidden contents

(-xe^-2x - (x/2)e^-4x – (x/27)e^-6x) / (-xe^-2x)
1 + (1/2)e^-2x + (1/27)e^-4x
And getting the value of that integral over the range 0 to infinity is easy. [Infinity value] – [zero value] is
[1 + 0 + 0] – [1 + (1/2) + (1/27)] = -29/54

I must have gotten positive/negative signs flipped somewhere, but I can’t find where.

Edit: Nevermind, I think you have to calculate the value over the range of integration for the numerator and denominator separately, I don't think you can just divide through like that. And after looking it up, those limits go to zero so I've got an indeterminate 0/0 still.

Spoiler

For Poisson, appropriately scaled, cumulative prob for (L<x) is F(x) = (1 - e^-x) and the pdf for (L=x) is f(x) = F'(x) = e^-x. So f(x) says our interval is x, and F(x), for each neighbor, says that's longer than they are. So a large interval's expected length is int (0,inf) {x f(x) F(x) F(x) } dx. (The same integral without the x gives the probability that an interval is large. Turns out it's 1/3.)  Integrate by parts using u=x and dv= { f F² dx } = (1/3) d( F³ - 1 ). Then the (uv) term {x (F³ -1) } is zero at both 0 and inf, leaving just int (0, inf) ( 1 - F³ ) dx = int (0, inf) { 3e^-x - 3e^-2x + e^-3x } dx. Was your inf involved with the (uv) term?

 

[plasmid]

On 3/12/2018 at 1:53 PM, bonanova said:

  Hide contents

For Poisson, appropriately scaled, cumulative prob for (L<x) is F(x) = (1 - e^-x) and the pdf for (L=x) is f(x) = F'(x) = e^-x. So f(x) says our interval is x, and F(x), for each neighbor, says that's longer than they are. So a large interval's expected length is int (0,inf) {x f(x) F(x) F(x) } dx. (The same integral without the x gives the probability that an interval is large. Turns out it's 1/3.)  Integrate by parts using u=x and dv= { f F² dx } = (1/3) d( F³ - 1 ). Then the (uv) term {x (F³ -1) } is zero at both 0 and inf, leaving just int (0, inf) ( 1 - F³ ) dx = int (0, inf) { 3e^-x - 3e^-2x + e^-3x } dx. Was your inf involved with the (uv) term?

 

If you do that and the (uv) term is x(F³-1), then at x=infinity wouldn't you end up with infinity times zero?

If there's a rule about the limit of multiplication between x and functions with e^-x as x goes to infinity, then maybe I could use that in the route I was taking.

[bonanova]

On 3/26/2018 at 10:33 PM, plasmid said:

If you do that and the (uv) term is x(F³-1), then at x=infinity wouldn't you end up with infinity times zero?

If there's a rule about the limit of multiplication between x and functions with e^-x as x goes to infinity, then maybe I could use that in the route I was taking.

Yes there is a rule, L'Hopital's rule. Basically you can just replace functions by their derivatives to resolve indeterminate values. Or, you can just evaluate expressions and see how they behave:

Spoiler

Here's a plot of  uv  =  x (F³ -1)   =   x { - 3e^-x + 3e^-2x - e^-3x }  vs x for x in [ 0, 10 (scaled x10) ]

 

It's intuitive that the exponential dominates for large x if you think of say x / e^3x, instead of  x  e^-3x.

[bonanova]

@plasmid Nice solve. The puzzle itself was more a math exercise than a puzzle -- that part was thinking it through and setting up the calculation. I thought is was interesting in that you can sort of envision the setup and know that it had to be e.g. greater than 1/3, but maybe not as great as 2/3, so the question was would it be greater than 1/2?