Re: Walking on integers

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 11/02/04 

Date: 02 Nov 2004 16:01:57 +0200

"Glen Able" <smDELETEecklers@hotmTHISail.com> writes:

> Not sure if this is a known problem, or something that mutated out of known
> problems in my head...
>
> Start with some integer and repeatedly choose steps of either +1 or -1.
> Stop when you reach some randomly chosen (and, obviously, unknown to you)
> integer. What strategy would minimise the no. steps taken?

It's impossible to answer unless we know with what distribution function
the target was chosen. However, I assume that it will be sign-symmetric
and some kind of bell-shaped curve.

With that in mind, I think you could do a lot worse than chosing a value
v (which will depend on the distribution, if it's a narrow bell curve,
then make v small, if it's a flat and broad bell curve, then make v
larger), and zig-zag as follows
0 -> v -> -2v -> 4v -> -8v ->16v -> -32v ...
To cover [-v, v] requires 3v steps.
To cover [-2v, 2v] requires 8v steps.
To cover [-4v, 4v] requires 18v steps.
To cover [-8v, 8v] requires 38v steps

For very flat distributions, then you probably want to reduce the quantity
of zig-zagging, and therefore could chose a path as follows
0 -> v -> -v^2 -> v^3 -> -v^4

Phil 

-- 
They no longer do my traditional winks tournament lunch - liver and bacon. 
It's just what you need during a winks tournament lunchtime to replace lost 
... liver.   -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'

Relevant Pages

  • Re: a little (very little,) data, extracted from my front-end feeding a conventional compressor
    ... You didn't read my post very closely -- I am getting a bell curve from ... ONE random data source, the client data itself -- no other information ... byte but unlike the input byte, which exhibited a flat distribution, ...
    (comp.compression)
  • Re: a little (very little,) data, extracted from my front-end feeding a conventional compressor
    ... You didn't read my post very closely -- I am getting a bell curve from ... the client data itself -- no other information ... byte but unlike the input byte, which exhibited a flat distribution, ... 'patterns' that documents possess,) as this is necessary to achieve ...
    (comp.compression)
  • Re: IQS OVER 200 FUGGETABOUTIT
    ... of that maxes out at 140. ... distribution of scores is wrong - or that Aussies are really bright - I ... is actually a superposition of one bell curve over two much smaller ones ... and those that might need extra help, on a general level. ...
    (rec.gambling.poker)
  • Re: Questions about probability functions
    ... a bell curve when there is equal likelihood that a random value will be ... If the distribution is uniform on the interval, in the sense that ... any continuous distribution all individual outcomes have probability 0. ...
    (sci.math)