Algorithm question: I've got a finite, ordered set of labels at my disposal (A-Z, say). Now I've got a bunch of incoming ordered values, integers say (this is an online problem). The values are drawn from a known range, but with an unknown distribution. What strategy do I use to assign labels to these values, so that the order of label and value matches, and so that I don't run out of labels for as long as possible.

(Basically, if I've assigned M to the value 5 at some point, and N to the value 7 at some point, and now a 6 comes in, I've lost because there's no label left between M and N. This situation should be delayed for as long as possible.)

Is it even possible to do better than assume a uniform distribution for the subinterval I have to insert the value into?

And how does this change if a) I receive a small number of values at once or b) I don't know what range the inputs are drawn from (or I know that they are drawn from (-inf, inf).

This seems like it should be a well-studied problem, but I don't even know where to begin searching.

Are the incoming values with or without repetition?

Let's say with repetition, but I guess I'd be interested in both cases.

I guess a simpler way than talking about labels is that I've got a finite row of empty slots to begin with and I need to insert the values into slots so that they remain ordered.

Is the range rather large (-> continuous distributions) or rather small (-> discrete distribution)?

I really have no particular use case in mind, so I can't answer those questions and you can generally assume that all possible variants are equally interesting :P

the incoming values could also be real numbers, not integers (so you'd have a completely continuous distribution, not just approximately continuous)

Curiously I recently thought about a similar problam (almost "reverse") but without coming to a solution.

(What actually made me think of this was building new houses in streets and having to give them numbers so that the numbers still increase along the street, but the space is usually limited enough that this doesn't become a very challenging problem.)

Why don't you make a challenge out of this problem and let the community do the work for you? :D

Well yeah, my follow-up question would have been "can I turn this into a challenge", but for that to be viable I first need to figure out whether it's possible to do better than any naive approaches.

I think a problem here might be that you allow any distribution. If we knew the distribution of the allowed distributions we might say something.

(I think it might be the same problem as when people ask about a "random" integer, without specifying the distribution.)

I think if we know the distribution it becomes straightforward.

Because then you can always determine the probability of another sample lying right or left of the current one and so you know exactly where to insert it.

I was talking about the distribution of the available distributions.

(but yes, I agree)

Oh I see.

I guess you're right, if the distribution is completely arbitrary, you can't really gather any information from any number of samples. It could be a distribution with spikes along the values you already have. Maybe if you simply add a constraint of sufficient smoothness or something?

I mean if the most probable distributions have all their mass close to 0 (lets say our fixed input range is [0,1]) then we could probably do something differently than if we say that the most probable distrbutions all have their mass in the center.

@MartinEnder Well it would probably still be difficult, as there are a lot of distributions :)

Right, but if you then get a lot of samples in a certain region, you can infer that this general region has a higher probability in the distribution (including the values between those samples). Which you couldn't infer without smoothness.

@flawr But if that's all you can say then I think you'd just take the mean of the allowed distributions and assume that to be your fixed distribution?

@MartinEnder Well you'd need to take a weighted mean since not all distributiosn have the same probability, right?

@MartinEnder Ah I see, that makes sense!

@flawr Yes, the mean according to your distribution of distributions.

I just had following thought: If you know the distribution is continuous, you suggested using a piecewise uniform distribution to model the unknown distribution.

So you limit yourself to piecewise constant PDFs

But if you know that e.g. the original distribution is n-times differentiable, you could use n-th degree splines, and perhaps get better results than just using piecewise constant functions.

Can the distribution be time-dependent?

@feersum Hey stop, don't make it even more complicated XD

No I'm trying to make it easier!

We don't even know the distribution could depend on what you're thinking and always choose the most inconvenient.

@flawr Ohhh, that would help determining the distribution in one subinterval from samples in an adjacent one.

sorry, can't type

This should be deleted IMHO.

I mean the bounty provider and OP do not look that inexperienced that they would not have had the idea to plot it themselves.

</rant>

Were I a mod on Math.SE, I'd probably just convert it to a comment.

And all the other comments aren't really helpful either, just shows that they didn't put the slightest effort in answering such a question, but just stating the obvious.