- #1

- 2,797

- 21

Heres the basic problem definition.You have a list of n items indexed 1..n, and you can navigate through the list in two different ways. One in a linear fashion by stepping "previous" or "next" or alternatively in a random fashion where the next item is chosen as a uniformly distributed (1..n) random number. Now starting from some random position you need to get to position number one (top) of the list. If the starting point is not already close to position-one then you're best off to make random steps until you're somewhere close to the top and then switch to the linear stepping to finish off. So the question is, where exactly is the optimal point to change strategy. That is, how close item number-one should you attempt to get using "random" steps before it's optimal to change to linear steps.

BTW. Assume that the approach to unity is unidirectional. That is, that the list does not "wrap around".

This problem actually came up a fews days ago when I was lying on the lounge listening to mp3's on my stereo. I was listening at about song 700 in a huge playlist of about 1400 songs when I suddenly decided I wanted to seek to the top of the list (where I'd recently added some new stuff that I now wanted to listen to). Now here's the embarrassing part, I was too lazy to get up and use the keyboard/mouse so I decide to do it using just the remote controller, which can do only "prev", "next" or "random". I thought here's an interesting maths problem. :)

I've solved it but my solution is a little bit heuristic, meaning that I think it's probably near optimal but my derivation is not exactly rigorous enough to be sure it really is 100% optimal. I was wondering what solutions others might make of this. The solution should be in the form of a function (possibly implicit, as in the solution to a given equation) giving the optimal threshold (position in the list) at which to change strategy as a function of the list size n.

Any takers?

BTW. Assume that the approach to unity is unidirectional. That is, that the list does not "wrap around".

This problem actually came up a fews days ago when I was lying on the lounge listening to mp3's on my stereo. I was listening at about song 700 in a huge playlist of about 1400 songs when I suddenly decided I wanted to seek to the top of the list (where I'd recently added some new stuff that I now wanted to listen to). Now here's the embarrassing part, I was too lazy to get up and use the keyboard/mouse so I decide to do it using just the remote controller, which can do only "prev", "next" or "random". I thought here's an interesting maths problem. :)

I've solved it but my solution is a little bit heuristic, meaning that I think it's probably near optimal but my derivation is not exactly rigorous enough to be sure it really is 100% optimal. I was wondering what solutions others might make of this. The solution should be in the form of a function (possibly implicit, as in the solution to a given equation) giving the optimal threshold (position in the list) at which to change strategy as a function of the list size n.

Any takers?

Last edited: