# You pass X people and Y people pass you: how relatively fast are you?

This question occurs to me every time I go jogging. I suspect every runner probabilist in the world must have thought of it (though I'm no probabilist), but I could not specifically find it online. I hope some MO readers will find it worth thinking about. Here's the basic set up:

Assume all runners go along a loop of length $L$ in the same direction. Assume that the distances $D_i$ ($i$ denoting a given individual) of the runners' runs are i.i.d. with distribution $P_d$, the runners' speeds $S_i$ are i.i.d. with distribution $P_s$, the starting point of each runner is uniform over the loop and the starting gaps between starting times has distribution $P_t$. Given your pace, the total distance of your run and the # of times you were passed and that you passed others, what can you say about $P_s$?

Specifically, what can you infer about where your pace lies wrt the population of runners on the loop? Are you in the top 5%? Are you above average? Etc.

Of course, you'd need to make assumptions about many of these things, fixing $P_d$ for instance. And as a modeling exercise there are several interesting elaborations, such as letting the random variables $D_i$ and $S_i$ be correlated.

There obviously isn't one right answer, hence the 'soft' tag. But I'm interested in hearing if others have thought about it, how they might set up the problem and what sorts of assumptions would make the conclusions most interesting. As you take $L$ smaller and smaller so that you have to contend with the possibility of lapping people and getting lapped, things become harder, and in different ways depending on whether or not we allow registering getting passed by the same person. We could also let people go around clockwise or counterclockwise with some probability.

It seems so obvious that this information imparts qualitative information about your relative fitness, but quantifying it isn't straight forward. The data is well defined, the question is pretty easy to ask, but the modeling part leaves a lot of flexibility. I'm interested in hearing how the creative brains here at MO would set up the problem to interpret the evidence (or if there is a fun paper on this sort of problem somewhere).

-
+1 I really like this question! –  Robby McKilliam Oct 3 '10 at 8:02
Nice thing, running with some math in the head! The total number of runners is unknown, I suppose; which makes the analysis more difficult. –  Pietro Majer Oct 3 '10 at 8:15
What matters, however, is the distribution of speed. If your speed is median (half runners run faster) then the ration $X/Y$ will be very different in the following extreme situation : 1) those who run faster run just a little faster than you ; those who run less fast run really slowly 2) those who run faster run really very fast ; the other ones run at most as fast as tyou. –  Hugh J Oct 3 '10 at 9:38
@R Hahn : I was thinking about a Poisson point process (not any point process). I think that with this (natural I think) assumption, you can get a formula involving the density of runners, the distribution of speed of runners, your speed and the time you run. But if you only have the ratio... –  Hugh J Oct 3 '10 at 16:46
I've heard a simple form of this question phrased thusly: if you're driving on the highway at such a speed that you pass the same number of cars that pass you, then you're traveling at the mean speed (not the median speed). See, for instance: jstor.org/stable/2687465 –  Ricky Liu Oct 4 '10 at 19:20

We know what happens if you are slowest or fastest. If you are dead center then you would not have a reason (would you?) to expect one event to happen more often then the other. Not complicating things without cause, I wonder: have you ruled out the (too?) obvious answer a that if you have passed j people and been passed by k then the best estimate (absent other information) is that you are faster than $\frac{j}{j+k}$ of the other runners and slower than $\frac{k}{j+k}$. With assumptions on the distributions maybe one could say more.

Under some assumptions you could infer things by how long it has been since any passings happened, or by how quickly the relative frequency converges, but I'll assume that you run blindfolded and at some stage are stopped and told "over the course of you run you passed j and were passed by k.

I wonder if it helps conceptually to renormalize relative to your speed and say that you are a stationary observer next to a track, people have been scattered on it in random positions, some go clockwise and some counterclockwise according to some distribution which maybe be biased in one direction (and maybe with various speeds).Given that you observe j going counterclockwise and k going clockwise...

-
+1 for the static observer formulation! Hugh J comments that $X/Y$ is sensitive to the shape of the speed distribution. In the static observer language: assume, on average, equal numbers of runners to the left and right, equally far from you (the uniform starting position assumption). Then $X/Y$ depends on the relative average speeds of these two groups, regardless of your speed. This may be the story: the passing data measures how much slower than you are the slower runners relative to how much faster than you are the faster runners, regardless of the number of runners in each group. –  R Hahn Oct 4 '10 at 7:02

# A much simplified model

Assume there are $k$ runners whose speed is independently uniformly distributed on $[0,1]$, where 1 means one loop per hour. They all start at the same place at the same time and run for $n$ hours. Their speeds are $p_1<\cdots < p_k.$ If I have speed $p_j$ then after $n$ hours I will have been passed about $$(p_{j+1}+\cdots+p_k-(k-j)p_j)n$$ times. Now $p_t$ is a beta$(t$,$k+1-t$) random variable hence $\mathbb E(p_t)= t / (k+1)$. Therefore the expected rate of people passing me per hour is $$\left(\sum_{t=j+1}^k \frac{t}{k+1}\right) - \frac{(k-j)j}{k+1}$$ $$= \frac{(k-j)(k+1-j)}{2(k+1)}.$$ If I measure this rate as being $\alpha$, know $k$, and assume $\alpha$ exactly realizes the expected value, then I can solve for $j$.

If $\alpha=1$ and $k=9$ then $j=5$. So if 1 person is passing me per hour, I may be in the middle of the pack. If $\alpha=2$ and $k=13$, then $j=6$, i.e., being passed by 2 out of 13 per hour is slightly below the median.

-
Thanks for your answer! If I know $P_s$ -- here, uniform on $[0,1]$ in laps per hour -- can't I just place my time (which I assume I know) on that distribution and read off my quantile? I would be more interested myself about the population inference, what can I learn about $P_s$, but maybe this is too hard. Your formulation answers a question about where I rank among a group of $k$ other runners, drawn from an assumed population, sort of like figuring my probable ranking in a race among random contestants. Anyway, I hope others will venture suggestions like you have. –  R Hahn Oct 3 '10 at 16:34

I've thought about this driving on the freeway. If n times more people pass you than you pass, what can you say about your speed relative to the mean? This ignores start points (I think OK). The number of cars that pass you is the integral from your speed to inf of (v-your v)*P(v), while the number you pass is integral from 0 to your speed of (your v-v)*P(v). So you need to make some assumption of P(v).

Even more important, if n<1 how many people are going faster than you-if you assume that only people in the top x% are at risk of a ticket, what is the relationship between n and x?

-

you can't say anything about your speed relative to the mean. You can only infer information about your speed relative to the median or about the percentile. The mean and the median can only coincide when the distribution is normal and the population includes one element whose value is exactly equal to the mean and is also the median.

If $n$ people pass you, and you pass $n$ people, you can say that you are in the middle $1/(2n+1)$ of the pack. If $x$ people pass you, and you pass $y$ people, you can say that your percentile is $100 (y)/(x+y)$. You can be more certain about your relative velocity with more knowledge acquired: by passing more people, or letting more people pass you. Or if not "more certain", you have more precision in the knowledge of your relative velocities percentile as the number of observations increases.

• If $(x+y)=0$, you have no knowledge of your relative velocity in the population.

• If $(x+y)=m$, then you know your percentile in the velocity distribution to the nearest $(m+1)$-th partile, or nearest $1/(m+1)$ fraction. If $m=4$, you can only know your quintile (which definitely is a word), since $m+1=5$.

If you don't know the underlying distribution of the velocities of the population, you can't infer a lot about your own absolute velocity. If you don't pass or get passed by many people, you can't know much about your relative velocity.

I have to admit to using this when I run to keep pace. I get spurred to run faster if I start getting passed by more people than I myself am running past. Of course, being passed by a muscular athletic jogger is more of an incentive. So adding more factors about the athletic prowess of each individual relative to you could also tell you more. But if the only collection acquired about your relative speed are the two integers, then only your percentile in the unknown velocity distribution can be inferred.

As to Aaron Meyerowitz about the static observor, there is a problem with changing the frame of reference of the observer if you do not take into account the absolute velocity in the frame of reference of the ground. Some runners may actually be running facing in the other direction, and converting to the static observer does not account for that,

Example: you are in a car driving west on a highway. You can infer your velocity rank or percentile relative to the west-bound vehicles by keeping track of how many west-bound vehicles pass you and how many of them you pass. If you accidentally include the east-bound vehicles on the other side of the road, you will come to the erroneous conclusion that you are going very fast indeed, as you are "passing" many vehicles oriented and bound in the eastern direction.

But, when you change the frame of reference to a static observer on the track, you have to look at what direction the runner is facing in order to make sure that you are only counting the runners facing the same direction and running in the same direction as you.

Strangely enough, I once saw someone walking backwards on a sidewalk, though not on the oval-track at the local junior high school.

-
I typed this as an answer because I couldn't figure out how to comment underneath Ross millikan's answer. I can't comment under the question either, but I can comment here... strange... –  Sam Daighe Oct 4 '10 at 12:53
You don't have enough "reputation points" yet. See mathoverflow.net/faq#reputation But don't worry, you'll be there soon. –  Willie Wong Oct 4 '10 at 13:16

I think that some of the other answers have ignored the fact that the difference in speed will affect how often you cross other runners. Therefore, you can count how many times you overtake or are overtaken, but this is not an unbiased estimator of your position in the rankings. Ross-millikan's answer has this right, I think, though there may be another weighting factor hiding in P(v), as I'll explain below.

Also, the presence of a loop (so that some runners can overtake others multiple times during a long run) is a source of trouble for me, so I'm going to consider the freeway.

First, suppose I have speed U, and a stream of other runners is (and always has been) setting off at speed v from a position far behind me. If the other runners set off regularly with frequency n per unit time, then their spacing is (v/n). My rate of crossing these runners is abs(U-v)*(n/v).

OK, so now instead consider n(v), a statistical distribution of frequency of runners setting off with speeds v. So, Ross-millikan's P(v) is the same as my n(v)/v. (We keep talking about the median or the mean of "the distribution" of runners -- if this was going to be precise, we would need to specify the weighting of this distribution. Are you comparing yourself to all the runners currently running, or all the runners that have run today, or what? Fast runners might run different distances or times, so there are several valid choices and the answers will generally be different. My n(v) is at least well defined, but I've dodged several questions, including the possibility of stopping.)

Anyway, in my world of a never-ending supply of never-ending runners, the rate that I overtake others is

$R_{overtaking}=\int_0^U ({U \over v}-1) n(v) dv$

The rate of me being overtaken is

$R_{overtaken}=\int_U^{\infty} (1-{U \over v}) n(v) dv$

I can consider the ratio of these, which gets round the issue of how many runners there are in total. However, as Hugh J pointed out, this is not enough. For example, consider the case where I really am the median runner, because half of the other runners setting off have speed vslow and half have speed vfast, with vslow<U<vfast. Even though I am the median runner, the ratio can vary:

${{R_{overtaking}} / {R_{overtaken}}}={{(U-v_{slow})v_{fast}} / [{(v_{fast}-U)v_{slow}}}]$

So, to get a true indication, you need to weight your observed frequencies by the reciprocal of the velocity differences. The good news is that you can pay little attention to the youngsters who zap past you in a flash. Conversely, you shouldn't give yourself too much credit for overtaking walkers with Zimmer frames. It will take a long time to get statistically significant information about the runners of similar standard to your own, because you meet them so infrequently.

-
All good points, some of which were covered in my comment to Aaron Meyerowitz answer. I'm thinking about simulating some statistics for different underlying distributions to illustrate this point the the relative speeds of the slower and faster runners is what determines the passing statistics, as opposed to one's quantile location in the distribution of speeds. I'll post pictures if I do, but first, actual work... –  R Hahn Oct 4 '10 at 17:59