Re: Walking on integers

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 11/02/04 

Date: Tue, 02 Nov 2004 18:10:50 +0100

David C. Ullrich wrote:
> <harrisq@tcs.inf.tu-dresden.de> wrote:
>>David C. Ullrich wrote:
>>>On Tue, 2 Nov 2004 11:11:02 -0000, "Glen Able"
>>>
>>>
>>>>Someone picks an integer, unbeknownst to you. You start at 0 and take steps
>>>>of +1 or -1 until you reach the chosen value. What strategy do you use to
>>>>mimimise the number of steps taken?
>>>
>>>Doesn't help, unless you tell us _how_ he chose the integer.
>>
>>hmm.. it seems that the question should be answerable if you assume
>>the pdf is symmetric about 0. Then a generic minimising "turn around"
>>strategy might work where the pdf is a parameter. e.g. for a uniform
>>distribution, turn around after an exponential # of steps, but for a
>>normal distribution a slower function.
>>
>>OK, uniform pdf over -all- integers seems problematic here.
>
> Huh? You say that assuming symmetry should give an answer, and
> then you give two examples of symmetric distributions (one of
> which doesn't exist, but never mind that for a second) for which
> you conjecture the answer is different. Not making much sense
> here... you seem to be contradicting me while agreeing with
> what I said, that the answer depends on the distribution.

I'm just brainstorming here, trying to help the OP along. I was just
trying to come up with the minimal extra assumptions necessary. Of
course, I agree with you that the answer depends on the pdf. As to a
uniform distribution: take limits? 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages
Quantcast