Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Average length of random 1-expansions
Replies: 9   Last Post: Nov 20, 2000 4:55 AM

 Messages: [ Previous | Next ]
 r3769 Posts: 30 Registered: 12/12/04
Re: Average length of random 1-expansions
Posted: Nov 17, 2000 11:54 PM

Hugo van der Sanden wrote :
>rich_burge@my-deja.com wrote:
>>
>> Hugo van der Sanden wrote:

>> > r3769 wrote:
>> > >
>> > > Hugo van der Sanden wrote:

>> > > >r3769 wrote:
>> > > >>
>> > > >> Given an initial value x[0] with 0<x[0]<1, define a random

1-expansion of
>> > > >> x[0] recursively as follows:
>> > > >>
>> > > >> Choose [the integer] a[i] (randomly) subject to

floor(a[i]*x[i])=1,
>> > > >> and then set x[i+1]=a[i]*x[i]-1.
>> > > >>
>> > > >> The length of a random 1-expansion of x[0] is n where x[n]=0.
>> > > >>
>> > > >> What is the average length of all the random 1-expansions of 1/7?

>>
>> > > >.. and solving gives a = 67, as required.
>> > >
>> > > If p is prime and 1<n<p, is f(1/p)>f(1/n)?

>> >
>> > I thought it would be, but no: f(1/13) = 16178/93 > 173, but f(1/17) =
>> > 2942345/20304 < 145. It does seem likely that the converse it true, ie
>> > that each new maximum will be a prime.

>>
>> Curiously, the same situation occurs if we modify
>> the definition just slightly:
>>
>> Instead of selecting a[i] randomly from
>> [amin..amax], flip a coin and set a[i]=amin if
>> the result is heads otherwise set a[i]=amax.
>> Here amin is the smallest integer s.t. floor(x[i]
>> *amin)=1 and amax is the largest such integer.
>>
>> Unless I have made an error, f(1/13)=18 and f
>> (1/17)=7.8 so my original conjecture is still
>> false. I wonder if each new maximum is prime in
>> this case?
>>
>> Just curious,

>
>Note that f(1/(2^k n)) = n/2 + f(1/n).

I think you wanted to write f(1/2^k n))=k/2 + f(1/n), no?

>
>I may have screwed up, but I get f(1/13) = 19 and f(1/17) = 8.8; perhaps
>I haven't quite got the same definition as you.

>
>In any case, by the definition I am using the answer is no: f(1/23) =
>71, f(1/46) = 71.5, and f(1/k) < 71 for all other k < 46.
>

I figured it was to good to be true, thanks.

It is kind of interesting to note that the "coin-flip 1-expansion" defined
above can be generalized:

Given any integer b>0, let amin be the smallest integer s.t.
floor(x[i]*amin)=b and amax the largest such integer.

Now let f(b,x)=the average length of all the coin-flip b-expansions of x.

For example f(1,1/11)=16, f(2,1/11)=6, f(4,1/11)=4, f(11,1/11)=51, and
f(113,1/11)=18.

I suppose it's not too difficult to show the sequence <f(b,1/11)> is
bounded, so what is it's sup?

Just curious,

R. Burge

Date Subject Author
10/30/00 r3769
10/30/00 Hugo van der Sanden
11/4/00 r3769
11/5/00 Hugo van der Sanden
11/9/00 rich_burge@my-deja.com
11/11/00 Hugo van der Sanden
11/17/00 r3769
11/20/00 Hugo van der Sanden
10/30/00 Gerry Myerson
10/30/00 r3769