Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16109 > unrolled thread

Re: Another little puzzle

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-21 13:17 -0800
    Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-22 04:10 +0000
      Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-24 06:21 -0800
        Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-24 16:53 +0000
          Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-24 17:14 +0000
          Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-24 22:30 +0000
            Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-25 00:02 +0000
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:30 +0000
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:55 +0000
          Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 00:37 -0800
        Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 00:41 +0000
          Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 01:05 -0800
            Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 09:30 -0800
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 21:44 +0000
              Re: Another little puzzle Richard Damon <Richard@Damon-Family.org> - 2022-12-25 17:59 -0500
                Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:39 -0800
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:18 +0000
              Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:35 -0800
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:49 +0000

#16109 — Re: Another little puzzle

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>
>> Given n times of the 24-hour day, print their average.
>> For example, the average of "eight o'clock" and
>> "ten o'clock" (n=2) would be "nine o'clock".
>> (You can choose any representation, for example "HH:MM"
>> or "seconds since midnight".)
>
>   Thanks for all replies!
>
>   I waited a few days before answering to allow
>   sufficient time to think about the problem.
>
>   There were not enough tests written and run.  As a result,
>   the puzzle has not yet been solved (unless I have overlooked
>   a contribution or misworded expectations).
>
>   So, here are two possible test cases.
>
> average( 23.5,  1.5 )==  0.5
> average( 11.5, 13.5 )== 12.5
>
>   (I use hours as units, so "0.5" means, "half past midnight".)
>
>   I hope that these test cases encode sensible expectations
>   for an average of two times on a 24-hour clock in the spirit
>   of the example given in the OP, which was, "the average of
>   eight o'clock and ten o'clock would be nine o'clock", since
>   these test cases just have rotated that example by 3.5 and
>   15.5 hours.
>
>   I believe that I have not seen an algorithm so far in this
>   thread that would pass these tests.

As before, the problem is underspecified.

What is average( 0700, 1900 ), where the times indicate 24-hour
military times?

What is average( 1900, 0700 )?

What is average( 0100, 0700, 1300, 1900 )?
What is average( 0700, 1300, 1900, 0100 )?
What is average( 1300, 1900, 0100, 0700 )?
What is average( 1900, 0100, 0700, 1300 )?

and similarly for all other permutations of
the four arguments?

Stop giving just examples;  instead give a statement
of the problem that gives correct answers for all
inputs.  Giving just examples is a waste of everyone's
time.

[toc] | [next] | [standalone]

#16114

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>
>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>
>>> Given n times of the 24-hour day, print their average.
>>> For example, the average of "eight o'clock" and
>>> "ten o'clock" (n=2) would be "nine o'clock".
>>> (You can choose any representation, for example "HH:MM"
>>> or "seconds since midnight".)
>>
>>   Thanks for all replies!
>>
>>   I waited a few days before answering to allow
>>   sufficient time to think about the problem.
>>
>>   There were not enough tests written and run.  As a result,
>>   the puzzle has not yet been solved (unless I have overlooked
>>   a contribution or misworded expectations).
>>
>>   So, here are two possible test cases.
>>
>> average( 23.5,  1.5 )==  0.5
>> average( 11.5, 13.5 )== 12.5
>>
>>   (I use hours as units, so "0.5" means, "half past midnight".)
>>
>>   I hope that these test cases encode sensible expectations
>>   for an average of two times on a 24-hour clock in the spirit
>>   of the example given in the OP, which was, "the average of
>>   eight o'clock and ten o'clock would be nine o'clock", since
>>   these test cases just have rotated that example by 3.5 and
>>   15.5 hours.
>>
>>   I believe that I have not seen an algorithm so far in this
>>   thread that would pass these tests.
>
> As before, the problem is underspecified.

Some remarks not specifically in reply to you, Tim...

The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
average should be a number, A, in [0, 24) that minimises

  Sum_{i=1,n} distance(A, t(i))

(or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms of
variance).  So far, this is just what an average is.  The key point is
what is the distance (or difference) whose sum (or sum of squares) we
want to minimise?  For times, I would say it is the length of the
shorter arc round an imaginary 24-hour clock face.

The problem has a natural interpretation in terms of angles.  Whatever
the circular quantity is, convert the values to unit vectors round a
circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The average
is then just the direction of the average vector, converted back to a
time of day.

Sometimes that vector has zero length, and the average is undefined, but
otherwise the length of the vector gives an indication of the
variability of the data.

Why do I consider this a reasonable interpretation of the problem?
Well, given a list of times of day when a train is observed to pass some
station, the circular 24-hour-time average should be our best estimate
of the scheduled time.

Obviously there are other possible readings of the problem, but I was
not able to justify any of them as useful for any real-world
applications.  This is a case where I hope I am wrong and there /are/
other circular averages with practical interpretations.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16134

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>
>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>
>>>> Given n times of the 24-hour day, print their average.
>>>> For example, the average of "eight o'clock" and
>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>> (You can choose any representation, for example "HH:MM"
>>>> or "seconds since midnight".)
>>>
>>>   Thanks for all replies!
>>>
>>>   I waited a few days before answering to allow
>>>   sufficient time to think about the problem.
>>>
>>>   There were not enough tests written and run.  As a result,
>>>   the puzzle has not yet been solved (unless I have overlooked
>>>   a contribution or misworded expectations).
>>>
>>>   So, here are two possible test cases.
>>>
>>> average( 23.5,  1.5 )==  0.5
>>> average( 11.5, 13.5 )== 12.5
>>>
>>>   (I use hours as units, so "0.5" means, "half past midnight".)
>>>
>>>   I hope that these test cases encode sensible expectations
>>>   for an average of two times on a 24-hour clock in the spirit
>>>   of the example given in the OP, which was, "the average of
>>>   eight o'clock and ten o'clock would be nine o'clock", since
>>>   these test cases just have rotated that example by 3.5 and
>>>   15.5 hours.
>>>
>>>   I believe that I have not seen an algorithm so far in this
>>>   thread that would pass these tests.
>>
>> As before, the problem is underspecified.
>
> Some remarks not specifically in reply to you, Tim...

I didn't really say very much.  Your comments are a lot more
interesting.

> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
> average should be a number, A, in [0, 24) that minimises
>
>   Sum_{i=1,n} distance(A, t(i))
>
> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
> of variance).  So far, this is just what an average is.  The key point
> is what is the distance (or difference) whose sum (or sum of squares)
> we want to minimise?  For times, I would say it is the length of the
> shorter arc round an imaginary 24-hour clock face.

Minimizing the square of the distance (aka length of the shorter arc)
is one metric, and I think a reasonable one.  (Minimizing the absolute
value of the distance gives a result more like the median than the
mean, IIANM.)

> The problem has a natural interpretation in terms of angles.  Whatever
> the circular quantity is, convert the values to unit vectors round a
> circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The
> average is then just the direction of the average vector, converted
> back to a time of day.

Averaging the "time unit vectors" is another plausible metric.

> Sometimes that vector has zero length, and the average is undefined,
> but otherwise the length of the vector gives an indication of the
> variability of the data.
>
> Why do I consider this a reasonable interpretation of the problem?
> Well, given a list of times of day when a train is observed to pass
> some station, the circular 24-hour-time average should be our best
> estimate of the scheduled time.
>
> Obviously there are other possible readings of the problem, but I was
> not able to justify any of them as useful for any real-world
> applications.  This is a case where I hope I am wrong and there /are/
> other circular averages with practical interpretations.

A nice analysis.

Some observations (all of which I believe are correct, but no
guarantees are offered).

The "vector average" metric is easier to calculate and gives an
explicit indication when the data produces a degenerate result.

Considering only cases that do not produce a degenerate result:

(1) the "conventional average" metric and the "vector average"
metric can produce different results when there are more than two
data points.  (For one or two data points I think they are always
the same.)

(2) the "vector average" metric can be calculated in O(n).  The
"conventional average" metric can be calculated in O(n*n).

(3) when the times are all reasonably close together, the
"conventional average" metric seems more likely to produce a result
corresponding to what most people expect.  Another way to say this
is that the "vector average" metric will sometimes surprise people.

Incidentally, I had implemented a method that is isomorphic to
the "vector average" metric (at least I think it is), and I was
surprised to discover that it gave different results than the
"conventional average" metric in some cases.

[toc] | [prev] | [next] | [standalone]

#16135

On 24/12/2022 14:21, Tim Rentsch wrote:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> Given n times of the 24-hour day, print their average.
>>>>> For example, the average of "eight o'clock" and
>>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>>> (You can choose any representation, for example "HH:MM"
>>>>> or "seconds since midnight".)
>>>>
>>>>    Thanks for all replies!
>>>>
>>>>    I waited a few days before answering to allow
>>>>    sufficient time to think about the problem.
>>>>
>>>>    There were not enough tests written and run.  As a result,
>>>>    the puzzle has not yet been solved (unless I have overlooked
>>>>    a contribution or misworded expectations).
>>>>
>>>>    So, here are two possible test cases.
>>>>
>>>> average( 23.5,  1.5 )==  0.5
>>>> average( 11.5, 13.5 )== 12.5
>>>>
>>>>    (I use hours as units, so "0.5" means, "half past midnight".)
>>>>
>>>>    I hope that these test cases encode sensible expectations
>>>>    for an average of two times on a 24-hour clock in the spirit
>>>>    of the example given in the OP, which was, "the average of
>>>>    eight o'clock and ten o'clock would be nine o'clock", since
>>>>    these test cases just have rotated that example by 3.5 and
>>>>    15.5 hours.
>>>>
>>>>    I believe that I have not seen an algorithm so far in this
>>>>    thread that would pass these tests.
>>>
>>> As before, the problem is underspecified.
>>
>> Some remarks not specifically in reply to you, Tim...
> 
> I didn't really say very much.  Your comments are a lot more
> interesting.
> 
>> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
>> average should be a number, A, in [0, 24) that minimises
>>
>>    Sum_{i=1,n} distance(A, t(i))
>>
>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
>> of variance).  So far, this is just what an average is.  The key point
>> is what is the distance (or difference) whose sum (or sum of squares)
>> we want to minimise?  For times, I would say it is the length of the
>> shorter arc round an imaginary 24-hour clock face.
> 
> Minimizing the square of the distance (aka length of the shorter arc)
> is one metric, and I think a reasonable one.  (Minimizing the absolute
> value of the distance gives a result more like the median than the
> mean, IIANM.)

Yes - perhaps Ben was thinking of making

    Sum_{i=1,n} signed_distance(A, t(i))  =  0

rather than minimising the (absolute) distance.  That would match up with minimising the sum of 
squares of the distance (mean).  Or he just meant the median as you say, which is different from the 
mean.  Both have plausible "average" properties, and meet my "minimal" criteria for what I think 
anyone would require of an "average" applying to a modular arithmetic:

-   if all x_i are within 5 minutes of each other [ALLOWING FOR WRAPPING
     AROUND THE END OF THE MODULO LOOP] then the "average" will be within
     those same 5 minutes.   NOT e.g. 12 hours or 4 hours or whatever away.

-   if all x_i are translated by a fixed offset like 1 hour, the average
     will translate by the same offset, i.e. it maintains the same "modulo"
     relation with the translated x_i.

hmm, thinking now I'll add the similar:

-   if all x_i are "reflected" about a chosen time, then the new average
     will be the reflected time of the original average.

(those aren't intended to be a definition of a "modular average", just to exclude suggestions that 
blatently lack the right symmetry for such an average.)

> 
>> The problem has a natural interpretation in terms of angles.  Whatever
>> the circular quantity is, convert the values to unit vectors round a
>> circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The
>> average is then just the direction of the average vector, converted
>> back to a time of day.
> 
> Averaging the "time unit vectors" is another plausible metric.

Yes I think this one would work best in most situations, given that the OP didn't have a precise 
mathematical requirement for his solution - probably he wants something that just works reasonably 
as expected.  (It's my favourite answer.)

Another way of thinking of this approach is "balancing" the 24-hour modular circle, where we've put 
unit weights at each of the times x_i.  E.g. we look for a balancing line through the centre of the 
circle.  [Note times on the circle go from 1-24, not 1-12 like a normal clock.]  Also, thinking like 
this, it's equivalent to (conventional) averaging of the sin of the angular differences from the 
average (balancing) point, since the sin will give the perpendicular distance of the weight from the 
balancing line.  So it still fits with the general scheme of minimising distance(x_i, v)^2, but with 
a slightly different metric (distance function) in use.

As sin(x) is close to x when x is small, the vector average solution would match closely with the 
mean (by arc length) solution when the times are close together, but diverge more noticeably when 
the times are spread out...


Mike.

[toc] | [prev] | [next] | [standalone]

#16136

On 24/12/2022 4:53 pm, Mike Terry wrote:
> On 24/12/2022 14:21, Tim Rentsch wrote:
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> 
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>> 
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>> 
>>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>> 
>>>>>> Given n times of the 24-hour day, print their
>>>>>> average. For example, the average of "eight o'clock"
>>>>>> and "ten o'clock" (n=2) would be "nine o'clock". 
>>>>>> (You can choose any representation, for example
>>>>>> "HH:MM" or "seconds since midnight".)
>>>>> 
>>>>> Thanks for all replies!
>>>>> 
>>>>> I waited a few days before answering to allow 
>>>>> sufficient time to think about the problem.
>>>>> 
>>>>> There were not enough tests written and run.  As a
>>>>> result, the puzzle has not yet been solved (unless I
>>>>> have overlooked a contribution or misworded
>>>>> expectations).
>>>>> 
>>>>> So, here are two possible test cases.
>>>>> 
>>>>> average( 23.5,  1.5 )==  0.5 average( 11.5, 13.5 )==
>>>>> 12.5
>>>>> 
>>>>> (I use hours as units, so "0.5" means, "half past 
>>>>> midnight".)
>>>>> 
>>>>> I hope that these test cases encode sensible
>>>>> expectations for an average of two times on a 24-hour
>>>>> clock in the spirit of the example given in the OP,
>>>>> which was, "the average of eight o'clock and ten
>>>>> o'clock would be nine o'clock", since these test cases
>>>>> just have rotated that example by 3.5 and 15.5 hours.
>>>>> 
>>>>> I believe that I have not seen an algorithm so far in
>>>>> this thread that would pass these tests.
>>>> 
>>>> As before, the problem is underspecified.
>>> 
>>> Some remarks not specifically in reply to you, Tim...
>> 
>> I didn't really say very much.  Your comments are a lot
>> more interesting.
>> 
>>> The input is a collection, t(n), of n > 1 numbers in [0,
>>> 24). The average should be a number, A, in [0, 24) that
>>> minimises
>>> 
>>> Sum_{i=1,n} distance(A, t(i))
>>> 
>>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to
>>> think in terms of variance).  So far, this is just what an
>>> average is.  The key point is what is the distance (or
>>> difference) whose sum (or sum of squares) we want to
>>> minimise?  For times, I would say it is the length of the 
>>> shorter arc round an imaginary 24-hour clock face.
>> 
>> Minimizing the square of the distance (aka length of the 
>> shorter arc) is one metric, and I think a reasonable one.
>> (Minimizing the absolute value of the distance gives a
>> result more like the median than the mean, IIANM.)
> 
> Yes - perhaps Ben was thinking of making
> 
> Sum_{i=1,n} signed_distance(A, t(i))  =  0
> 
> rather than minimising the (absolute) distance.

And so perhaps you are closer to what Ben was thinking of, but as
far as we know you are no closer to knowing what Stefan was
thinking of.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16144

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 24/12/2022 14:21, Tim Rentsch wrote:
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> 
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>>
>>>>>> Given n times of the 24-hour day, print their average.
>>>>>> For example, the average of "eight o'clock" and
>>>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>>>> (You can choose any representation, for example "HH:MM"
>>>>>> or "seconds since midnight".)
>>>>>
>>>>>    Thanks for all replies!
>>>>>
>>>>>    I waited a few days before answering to allow
>>>>>    sufficient time to think about the problem.
>>>>>
>>>>>    There were not enough tests written and run.  As a result,
>>>>>    the puzzle has not yet been solved (unless I have overlooked
>>>>>    a contribution or misworded expectations).
>>>>>
>>>>>    So, here are two possible test cases.
>>>>>
>>>>> average( 23.5,  1.5 )==  0.5
>>>>> average( 11.5, 13.5 )== 12.5
>>>>>
>>>>>    (I use hours as units, so "0.5" means, "half past midnight".)
>>>>>
>>>>>    I hope that these test cases encode sensible expectations
>>>>>    for an average of two times on a 24-hour clock in the spirit
>>>>>    of the example given in the OP, which was, "the average of
>>>>>    eight o'clock and ten o'clock would be nine o'clock", since
>>>>>    these test cases just have rotated that example by 3.5 and
>>>>>    15.5 hours.
>>>>>
>>>>>    I believe that I have not seen an algorithm so far in this
>>>>>    thread that would pass these tests.
>>>>
>>>> As before, the problem is underspecified.
>>>
>>> Some remarks not specifically in reply to you, Tim...
>> I didn't really say very much.  Your comments are a lot more
>> interesting.
>> 
>>> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
>>> average should be a number, A, in [0, 24) that minimises
>>>
>>>    Sum_{i=1,n} distance(A, t(i))
>>>
>>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
>>> of variance).  So far, this is just what an average is.  The key point
>>> is what is the distance (or difference) whose sum (or sum of squares)
>>> we want to minimise?  For times, I would say it is the length of the
>>> shorter arc round an imaginary 24-hour clock face.
>> Minimizing the square of the distance (aka length of the shorter arc)
>> is one metric, and I think a reasonable one.  (Minimizing the absolute
>> value of the distance gives a result more like the median than the
>> mean, IIANM.)
>
> Yes - perhaps Ben was thinking of aking
>
>    Sum_{i=1,n} signed_distance(A, t(i))  =  0
>
> rather than minimising the (absolute) distance.  That would match up
> with minimising the sum of squares of the distance (mean).  Or he just
> meant the median as you say, which is different from the mean.  Both
> have plausible "average" properties,

Well, I was trying to be deliberately vague (hence my talking about "an
average" rather than mean, median or whatever) but I was no vague enough
with the formula.

I wasn't thinking of a zero net distance because some metrics (though
probably not applicable in this situation) don't always allow for a zero
sum.  I should have referred to minimising some kind distance sum, be it
the absolute value of a signed sum or, as in the solution I was
proposing, the sum of directional differences (i.e. full vectors).

> and meet my "minimal" criteria
> for what I think anyone would require of an "average" applying to a
> modular arithmetic:
>
> -   if all x_i are within 5 minutes of each other [ALLOWING FOR WRAPPING
>     AROUND THE END OF THE MODULO LOOP] then the "average" will be within
>     those same 5 minutes.   NOT e.g. 12 hours or 4 hours or whatever away.

And when the x_i are widely spaced the average might be considered
nearly meaningless.  If you have {0, 8, 16} hours then what is the
"average"?  Are there cases where every set of circular values has a
meaningful "average"?  If not, you really need more than a single number
answer.

(These are not questions to you, specifically, I'm interested to know of
interpretations that go beyond the way I see things.)

> -   if all x_i are translated by a fixed offset like 1 hour, the average
>     will translate by the same offset, i.e. it maintains the same "modulo"
>     relation with the translated x_i.
>
> hmm, thinking now I'll add the similar:
>
> -   if all x_i are "reflected" about a chosen time, then the new average
>     will be the reflected time of the original average.
>
> (those aren't intended to be a definition of a "modular average", just
> to exclude suggestions that blatently lack the right symmetry for such
> an average.)
>
>>> The problem has a natural interpretation in terms of angles.  Whatever
>>> the circular quantity is, convert the values to unit vectors round a
>>> circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The
>>> average is then just the direction of the average vector, converted
>>> back to a time of day.
>> Averaging the "time unit vectors" is another plausible metric.
>
> Yes I think this one would work best in most situations, given that
> the OP didn't have a precise mathematical requirement for his solution
> - probably he wants something that just works reasonably as expected.
> (It's my favourite answer.)
>
> Another way of thinking of this approach is "balancing" the 24-hour
> modular circle, where we've put unit weights at each of the times x_i.
> E.g. we look for a balancing line through the centre of the circle.

Is that the same?  For {0, 8, 16} any of the three lines through 0, 8 or
16 balances, but the vector sum interpretation is undefined.  And for
{0, 6, 12, 18} there are two balance lines, neither of which seems to be
a natural answer for the average.

(Also, every balance line gives two answers, so how do you pick?)

> [Note times on the circle go from 1-24, not 1-12 like a normal clock.]
> Also, thinking like this, it's equivalent to (conventional) averaging
> of the sin of the angular differences from the average (balancing)
> point, since the sin will give the perpendicular distance of the
> weight from the balancing line.  So it still fits with the general
> scheme of minimising distance(x_i, v)^2, but with a slightly different
> metric (distance function) in use.
>
> As sin(x) is close to x when x is small, the vector average solution
> would match closely with the mean (by arc length) solution when the
> times are close together, but diverge more noticeably when the times
> are spread out...

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16145

On 24/12/2022 22:30, Ben Bacarisse wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
> 
>> On 24/12/2022 14:21, Tim Rentsch wrote:
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>>
>>>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>>>
>>>>>>> Given n times of the 24-hour day, print their average.
>>>>>>> For example, the average of "eight o'clock" and
>>>>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>>>>> (You can choose any representation, for example "HH:MM"
>>>>>>> or "seconds since midnight".)
>>>>>>
>>>>>>     Thanks for all replies!
>>>>>>
>>>>>>     I waited a few days before answering to allow
>>>>>>     sufficient time to think about the problem.
>>>>>>
>>>>>>     There were not enough tests written and run.  As a result,
>>>>>>     the puzzle has not yet been solved (unless I have overlooked
>>>>>>     a contribution or misworded expectations).
>>>>>>
>>>>>>     So, here are two possible test cases.
>>>>>>
>>>>>> average( 23.5,  1.5 )==  0.5
>>>>>> average( 11.5, 13.5 )== 12.5
>>>>>>
>>>>>>     (I use hours as units, so "0.5" means, "half past midnight".)
>>>>>>
>>>>>>     I hope that these test cases encode sensible expectations
>>>>>>     for an average of two times on a 24-hour clock in the spirit
>>>>>>     of the example given in the OP, which was, "the average of
>>>>>>     eight o'clock and ten o'clock would be nine o'clock", since
>>>>>>     these test cases just have rotated that example by 3.5 and
>>>>>>     15.5 hours.
>>>>>>
>>>>>>     I believe that I have not seen an algorithm so far in this
>>>>>>     thread that would pass these tests.
>>>>>
>>>>> As before, the problem is underspecified.
>>>>
>>>> Some remarks not specifically in reply to you, Tim...
>>> I didn't really say very much.  Your comments are a lot more
>>> interesting.
>>>
>>>> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
>>>> average should be a number, A, in [0, 24) that minimises
>>>>
>>>>     Sum_{i=1,n} distance(A, t(i))
>>>>
>>>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
>>>> of variance).  So far, this is just what an average is.  The key point
>>>> is what is the distance (or difference) whose sum (or sum of squares)
>>>> we want to minimise?  For times, I would say it is the length of the
>>>> shorter arc round an imaginary 24-hour clock face.
>>> Minimizing the square of the distance (aka length of the shorter arc)
>>> is one metric, and I think a reasonable one.  (Minimizing the absolute
>>> value of the distance gives a result more like the median than the
>>> mean, IIANM.)
>>
>> Yes - perhaps Ben was thinking of aking
>>
>>     Sum_{i=1,n} signed_distance(A, t(i))  =  0
>>
>> rather than minimising the (absolute) distance.  That would match up
>> with minimising the sum of squares of the distance (mean).  Or he just
>> meant the median as you say, which is different from the mean.  Both
>> have plausible "average" properties,
> 
> Well, I was trying to be deliberately vague (hence my talking about "an
> average" rather than mean, median or whatever) but I was no vague enough
> with the formula.
> 
> I wasn't thinking of a zero net distance because some metrics (though
> probably not applicable in this situation) don't always allow for a zero
> sum.  I should have referred to minimising some kind distance sum, be it
> the absolute value of a signed sum or, as in the solution I was
> proposing, the sum of directional differences (i.e. full vectors).
> 
>> and meet my "minimal" criteria
>> for what I think anyone would require of an "average" applying to a
>> modular arithmetic:
>>
>> -   if all x_i are within 5 minutes of each other [ALLOWING FOR WRAPPING
>>      AROUND THE END OF THE MODULO LOOP] then the "average" will be within
>>      those same 5 minutes.   NOT e.g. 12 hours or 4 hours or whatever away.
> 
> And when the x_i are widely spaced the average might be considered
> nearly meaningless.  If you have {0, 8, 16} hours then what is the
> "average"?  Are there cases where every set of circular values has a
> meaningful "average"?  If not, you really need more than a single number
> answer.
> 
> (These are not questions to you, specifically, I'm interested to know of
> interpretations that go beyond the way I see things.)
> 
>> -   if all x_i are translated by a fixed offset like 1 hour, the average
>>      will translate by the same offset, i.e. it maintains the same "modulo"
>>      relation with the translated x_i.
>>
>> hmm, thinking now I'll add the similar:
>>
>> -   if all x_i are "reflected" about a chosen time, then the new average
>>      will be the reflected time of the original average.
>>
>> (those aren't intended to be a definition of a "modular average", just
>> to exclude suggestions that blatently lack the right symmetry for such
>> an average.)
>>
>>>> The problem has a natural interpretation in terms of angles.  Whatever
>>>> the circular quantity is, convert the values to unit vectors round a
>>>> circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The
>>>> average is then just the direction of the average vector, converted
>>>> back to a time of day.
>>> Averaging the "time unit vectors" is another plausible metric.
>>
>> Yes I think this one would work best in most situations, given that
>> the OP didn't have a precise mathematical requirement for his solution
>> - probably he wants something that just works reasonably as expected.
>> (It's my favourite answer.)
>>
>> Another way of thinking of this approach is "balancing" the 24-hour
>> modular circle, where we've put unit weights at each of the times x_i.
>> E.g. we look for a balancing line through the centre of the circle.
> 
> Is that the same?  For {0, 8, 16} any of the three lines through 0, 8 or
> 16 balances, but the vector sum interpretation is undefined.  And for
> {0, 6, 12, 18} there are two balance lines, neither of which seems to be
> a natural answer for the average.

Yes, it's logically the same, in so far as WHEN the x_i aren't already balanced [aka they /have/ a 
meaningful average] we get the same average both ways.  (Adding vectors is effectively a way of 
calculating moments of the weights in the balancing view of things.)

With modular arithmetic there is a scenario where everything is already balanced, and so it isn't 
clear what an average would represent, if anything.  Both {0, 8, 16} and {0, 6, 12, 18} are already 
perfectly balanced - ANY line through the origin would balance for either example.  That is just a 
feature of modular balancing/averaging I guess.  I agree there's no natural "average", so I'll just 
suggest we say "this distribution doesn't have an average" or something.  Adding vectors gives a 
zero result and so doesn't work either...

Of course, we might apply some definition that we're working with and just see how it goes!  E.g. we 
might say "we're minimising XXXXXX error function" - but then we just find the function is constant 
on the whole circle - so it doesn't give us anything useful other than that there's no useful 
average.  Or we could say "every point meets the average criteria", but those are just words and no 
more help.  This is what happens with the minimising functions that have been mentioned in the 
thread, for your two "already balanced" examples.  [E.g. if we're minimising

     error(A) = Sum_{x=0,8,16} sin (angle of least arc from A to x)^2

it's going to zero on the whole circle - no (unique) minimum.  :(

You're right that a balancing line has two ends, so which to take?  We would take the end bearing 
most weight!  But actually the balancing line idea wasn't my proper thinking - that was that we 
"counter-balanced" the circle by adding a new weight somewhere on the circle.  There is a unique 
such place where such a weight can go, and a unique weight that works.  The "average" for the x_i is 
then directly OPPOSITE the counter weight.  This is all assuming we don't start with an exactly 
balancing sample!  The mass of the counter-weight is the magnitude of your vector sum, indicating 
the "strength" of the average...

[I thought someone would ask the annoying question "why is the counter-balancing point on the circle 
/opposite/ to the average point?" so by turning it into a balancing line which went through the 
average-point I could save a response...  And of course once we're considering a balancing line 
passing through the counter-weight and average-point, we could then remove the counter-weight and 
things would still balance]

Anyhow, I just said it all as another way of thinking about the vector average method.  In a program 
we're going to compute x and y components of vectors and add them like you said.

> 
> (Also, every balance line gives two answers, so how do you pick?)

The "heaviest end" of the circle!  But really, maybe forget the balancing line and think of the 
counter-balancing weight idea.


Mike.

[toc] | [prev] | [next] | [standalone]

#16147

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 24/12/2022 22:30, Ben Bacarisse wrote:
>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

>>> Another way of thinking of this approach is "balancing" the 24-hour
>>> modular circle, where we've put unit weights at each of the times x_i.
>>> E.g. we look for a balancing line through the centre of the circle.
>>
>> Is that the same?  For {0, 8, 16} any of the three lines through 0, 8 or
>> 16 balances, but the vector sum interpretation is undefined.  And for
>> {0, 6, 12, 18} there are two balance lines, neither of which seems to be
>> a natural answer for the average.
>
> Yes, it's logically the same, in so far as WHEN the x_i aren't already
> balanced [aka they /have/ a meaningful average] we get the same
> average both ways.  (Adding vectors is effectively a way of
> calculating moments of the weights in the balancing view of things.)

Oh, yes, I see what you mean.  Sorry.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16148

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> ... But actually the balancing line idea wasn't my proper thinking -
> that was that we "counter-balanced" the circle by adding a new weight
> somewhere on the circle.  There is a unique such place where such a
> weight can go, and a unique weight that works.

Or just find the point in the (weightless) disc where it balances.
That's the vector average.

> The "average" for the
> x_i is then directly OPPOSITE the counter weight.  This is all
> assuming we don't start with an exactly balancing sample!
> The mass of
> the counter-weight is the magnitude of your vector sum, indicating the
> "strength" of the average...

The distance from the centre is then a measure of the strength of the
average.

I like the physical metaphor of a balanced disc, but I prefer the idea
of finding the balance point directly rather than the mass and location
(on the circumference) of a counterweight.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16151

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 24/12/2022 14:21, Tim Rentsch wrote:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>>
>>>>>> Given n times of the 24-hour day, print their average.
>>>>>> For example, the average of "eight o'clock" and
>>>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>>>> (You can choose any representation, for example "HH:MM"
>>>>>> or "seconds since midnight".)

[...]

>>> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
>>> average should be a number, A, in [0, 24) that minimises
>>>
>>>    Sum_{i=1,n} distance(A, t(i))
>>>
>>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
>>> of variance).  So far, this is just what an average is.  The key point
>>> is what is the distance (or difference) whose sum (or sum of squares)
>>> we want to minimise?  For times, I would say it is the length of the
>>> shorter arc round an imaginary 24-hour clock face.
>>
>> Minimizing the square of the distance (aka length of the shorter
>> arc) is one metric, and I think a reasonable one.  [...]
>
> Yes - perhaps Ben was thinking of making
>
>    Sum_{i=1,n} signed_distance(A, t(i))  =  0
>
> rather than minimising the (absolute) distance. [...]

I think Ben meant what he said, but I will let him speak for
himself.

>>> The problem has a natural interpretation in terms of angles.
>>> Whatever the circular quantity is, convert the values to unit
>>> vectors round a circle.  For times of day, just scale [0, 24) to
>>> [0, 2*pi).  The average is then just the direction of the average
>>> vector, converted back to a time of day.
>>
>> Averaging the "time unit vectors" is another plausible metric.
>
> Yes I think this one would work best in most situations, [...]

It gives results in many cases, including many easy cases, that I
think would surprise most people.

> Another way of thinking of this approach is "balancing" the 24-hour
> modular circle, where we've put unit weights at each of the times
> x_i.  E.g. we look for a balancing line through the centre of the
> circle.  [Note times on the circle go from 1-24, not 1-12 like a
> normal clock.]

To me this way of thinking about the problem seems not very
useful.

> Also, thinking like this, it's equivalent to (conventional)
> averaging of the sin of the angular differences from the average
> (balancing) point, since the sin will give the perpendicular
> distance of the weight from the balancing line. [...]

I think this statement is nonsensical.  We are taking the
conventional average of "something", but the "something" has
been chosen so that its conventional average is zero.  It's
like saying, Once you get to where you're going, you know that
where you're going is where you are.  There is no information
about how to solve the problem, and so it cannot be equivalent
to any method that provides an actual answer.

[toc] | [prev] | [next] | [standalone]

#16146

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> Given n times of the 24-hour day, print their average.
>>>>> For example, the average of "eight o'clock" and
>>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>>> (You can choose any representation, for example "HH:MM"
>>>>> or "seconds since midnight".)
>>>>
>>>>   Thanks for all replies!
>>>>
>>>>   I waited a few days before answering to allow
>>>>   sufficient time to think about the problem.
>>>>
>>>>   There were not enough tests written and run.  As a result,
>>>>   the puzzle has not yet been solved (unless I have overlooked
>>>>   a contribution or misworded expectations).
>>>>
>>>>   So, here are two possible test cases.
>>>>
>>>> average( 23.5,  1.5 )==  0.5
>>>> average( 11.5, 13.5 )== 12.5
>>>>
>>>>   (I use hours as units, so "0.5" means, "half past midnight".)
>>>>
>>>>   I hope that these test cases encode sensible expectations
>>>>   for an average of two times on a 24-hour clock in the spirit
>>>>   of the example given in the OP, which was, "the average of
>>>>   eight o'clock and ten o'clock would be nine o'clock", since
>>>>   these test cases just have rotated that example by 3.5 and
>>>>   15.5 hours.
>>>>
>>>>   I believe that I have not seen an algorithm so far in this
>>>>   thread that would pass these tests.
>>>
>>> As before, the problem is underspecified.
>>
>> Some remarks not specifically in reply to you, Tim...
>
> I didn't really say very much.  Your comments are a lot more
> interesting.
>
>> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
>> average should be a number, A, in [0, 24) that minimises
>>
>>   Sum_{i=1,n} distance(A, t(i))
>>
>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
>> of variance).  So far, this is just what an average is.  The key point
>> is what is the distance (or difference) whose sum (or sum of squares)
>> we want to minimise?  For times, I would say it is the length of the
>> shorter arc round an imaginary 24-hour clock face.
>
> Minimizing the square of the distance (aka length of the shorter arc)
> is one metric, and I think a reasonable one.  (Minimizing the absolute
> value of the distance gives a result more like the median than the
> mean, IIANM.)
>
>> The problem has a natural interpretation in terms of angles.  Whatever
>> the circular quantity is, convert the values to unit vectors round a
>> circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The
>> average is then just the direction of the average vector, converted
>> back to a time of day.
>
> Averaging the "time unit vectors" is another plausible metric.
>
>> Sometimes that vector has zero length, and the average is undefined,
>> but otherwise the length of the vector gives an indication of the
>> variability of the data.
>>
>> Why do I consider this a reasonable interpretation of the problem?
>> Well, given a list of times of day when a train is observed to pass
>> some station, the circular 24-hour-time average should be our best
>> estimate of the scheduled time.
>>
>> Obviously there are other possible readings of the problem, but I was
>> not able to justify any of them as useful for any real-world
>> applications.  This is a case where I hope I am wrong and there /are/
>> other circular averages with practical interpretations.
>
> A nice analysis.

A generous appraisal, thanks.  I was trying to be vague enough not to
put my foot in it, by was too specific with the formula.

> Some observations (all of which I believe are correct, but no
> guarantees are offered).
>
> The "vector average" metric is easier to calculate and gives an
> explicit indication when the data produces a degenerate result.
>
> Considering only cases that do not produce a degenerate result:
>
> (1) the "conventional average" metric and the "vector average"
> metric can produce different results when there are more than two
> data points.  (For one or two data points I think they are always
> the same.)
>
> (2) the "vector average" metric can be calculated in O(n).  The
> "conventional average" metric can be calculated in O(n*n).

By which I presume you mean and /not/ in O(n).  (Big O is just an upper
bound.)

> (3) when the times are all reasonably close together, the
> "conventional average" metric seems more likely to produce a result
> corresponding to what most people expect.  Another way to say this
> is that the "vector average" metric will sometimes surprise people.

I'm sorry to be obtuse, but what is the "conventional average"?  The
name makes it sound trivial, but the quadratic time makes me certain
that is isn't.

My "conventional average" algorithm (which is not well thought out) was
to (a) rotate the data set to avoid the 23/0 boundary (not always
possible), (b) take the arithmetic mean, and then (c) rotate the result
back.  E.g. [23,0,1] -> [0,1,2] by adding one, and the average is
mean[0,1,2] - 1 = 0.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16152

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>>
>>>>>> Given n times of the 24-hour day, print their average.
>>>>>> For example, the average of "eight o'clock" and
>>>>>> "ten o'clock" (n=2) would be "nine o'clock".
>>>>>> (You can choose any representation, for example "HH:MM"
>>>>>> or "seconds since midnight".)
>>>>>
>>>>>   Thanks for all replies!
>>>>>
>>>>>   I waited a few days before answering to allow
>>>>>   sufficient time to think about the problem.
>>>>>
>>>>>   There were not enough tests written and run.  As a result,
>>>>>   the puzzle has not yet been solved (unless I have overlooked
>>>>>   a contribution or misworded expectations).
>>>>>
>>>>>   So, here are two possible test cases.
>>>>>
>>>>> average( 23.5,  1.5 )==  0.5
>>>>> average( 11.5, 13.5 )== 12.5
>>>>>
>>>>>   (I use hours as units, so "0.5" means, "half past midnight".)
>>>>>
>>>>>   I hope that these test cases encode sensible expectations
>>>>>   for an average of two times on a 24-hour clock in the spirit
>>>>>   of the example given in the OP, which was, "the average of
>>>>>   eight o'clock and ten o'clock would be nine o'clock", since
>>>>>   these test cases just have rotated that example by 3.5 and
>>>>>   15.5 hours.
>>>>>
>>>>>   I believe that I have not seen an algorithm so far in this
>>>>>   thread that would pass these tests.
>>>>
>>>> As before, the problem is underspecified.
>>>
>>> Some remarks not specifically in reply to you, Tim...
>>
>> I didn't really say very much.  Your comments are a lot more
>> interesting.
>>
>>> The input is a collection, t(n), of n > 1 numbers in [0, 24).  The
>>> average should be a number, A, in [0, 24) that minimises
>>>
>>>   Sum_{i=1,n} distance(A, t(i))
>>>
>>> (or Sum_{i=1,n} difference(A, t(i))^2 if you prefer to think in terms
>>> of variance).  So far, this is just what an average is.  The key point
>>> is what is the distance (or difference) whose sum (or sum of squares)
>>> we want to minimise?  For times, I would say it is the length of the
>>> shorter arc round an imaginary 24-hour clock face.
>>
>> Minimizing the square of the distance (aka length of the shorter arc)
>> is one metric, and I think a reasonable one.  (Minimizing the absolute
>> value of the distance gives a result more like the median than the
>> mean, IIANM.)
>>
>>> The problem has a natural interpretation in terms of angles.  Whatever
>>> the circular quantity is, convert the values to unit vectors round a
>>> circle.  For times of day, just scale [0, 24) to [0, 2*pi).  The
>>> average is then just the direction of the average vector, converted
>>> back to a time of day.
>>
>> Averaging the "time unit vectors" is another plausible metric.
>>
>>> Sometimes that vector has zero length, and the average is undefined,
>>> but otherwise the length of the vector gives an indication of the
>>> variability of the data.
>>>
>>> Why do I consider this a reasonable interpretation of the problem?
>>> Well, given a list of times of day when a train is observed to pass
>>> some station, the circular 24-hour-time average should be our best
>>> estimate of the scheduled time.
>>>
>>> Obviously there are other possible readings of the problem, but I was
>>> not able to justify any of them as useful for any real-world
>>> applications.  This is a case where I hope I am wrong and there /are/
>>> other circular averages with practical interpretations.
>>
>> A nice analysis.
>
> A generous appraisal, thanks.  I was trying to be vague enough not to
> put my foot in it, by was too specific with the formula.
>
>> Some observations (all of which I believe are correct, but no
>> guarantees are offered).
>>
>> The "vector average" metric is easier to calculate and gives an
>> explicit indication when the data produces a degenerate result.
>>
>> Considering only cases that do not produce a degenerate result:
>>
>> (1) the "conventional average" metric and the "vector average"
>> metric can produce different results when there are more than two
>> data points.  (For one or two data points I think they are always
>> the same.)
>>
>> (2) the "vector average" metric can be calculated in O(n).  The
>> "conventional average" metric can be calculated in O(n*n).
>
> By which I presume you mean and /not/ in O(n).  (Big O is just an
> upper bound.)

What I mean is I have an algorithm that runs in time proportional
to n*n.  I suspect that there is an algorithm with better big-O
behavior (probably O( n * log n )), but I don't actually have one
to show, so I simply gave the best big-O result that I knew.

>> (3) when the times are all reasonably close together, the
>> "conventional average" metric seems more likely to produce a result
>> corresponding to what most people expect.  Another way to say this
>> is that the "vector average" metric will sometimes surprise people.
>
> I'm sorry to be obtuse, but what is the "conventional average"?  The
> name makes it sound trivial, but the quadratic time makes me certain
> that is isn't.

Sorry, I meant to refer to your formulation of average 

    A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }

where 'difference' means the shorter arc length.  This formula
matches the result for 'mean' on real numbers.

> My "conventional average" algorithm (which is not well thought out) was
> to (a) rotate the data set to avoid the 23/0 boundary (not always
> possible), (b) take the arithmetic mean, and then (c) rotate the result
> back.  E.g. [23,0,1] -> [0,1,2] by adding one, and the average is
> mean[0,1,2] - 1 = 0.

Yes, if you know where to split the cycle then the answer can be
found in O(n) time.  But how can we figure out where to split the
cycle?  (Incidentally I got that part wrong the first way I tried
to do it.)

[toc] | [prev] | [next] | [standalone]

#16153

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

[pulled up from further on in the responded-to posting]

> [By "conventional average" I mean a time/direction A such that]
>
>     A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>
> where 'difference' means the shorter arc length.

[...]

>>> The "conventional average" metric can be calculated in O(n*n).
>>
>> By which I presume you mean and /not/ in O(n).  (Big O is just an
>> upper bound.)
>
> What I mean is I have an algorithm that runs in time proportional
> to n*n.  I suspect that there is an algorithm with better big-O
> behavior (probably O( n * log n )), but I don't actually have one
> to show, so I simply gave the best big-O result that I knew.

After some further thought I have convinced myself that there is
indeed an algorithm that is O( n * log n ).  The idea isn't that
complicated, but it's tedious, so I haven't actually implemented
it.  Perhaps someone will be interested to take that as a challenge
problem.

And who knows, maybe there is an algorithm with even better big-O
performance.  At least for now that's above my pay grade.

(and of course, Merry Christmas...)

[toc] | [prev] | [next] | [standalone]

#16155

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>> I'm sorry to be obtuse, but what is the "conventional average"?  The
>> name makes it sound trivial, but the quadratic time makes me certain
>> that is isn't.
>
> Sorry, I meant to refer to your formulation of average 
>
>     A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>
> where 'difference' means the shorter arc length.  This formula
> matches the result for 'mean' on real numbers.
>
>> My "conventional average" algorithm (which is not well thought out) was
>> to (a) rotate the data set to avoid the 23/0 boundary (not always
>> possible), (b) take the arithmetic mean, and then (c) rotate the result
>> back.  E.g. [23,0,1] -> [0,1,2] by adding one, and the average is
>> mean[0,1,2] - 1 = 0.
>
> Yes, if you know where to split the cycle then the answer can be
> found in O(n) time.  But how can we figure out where to split the
> cycle?

Well I handily stopped considering this at the stage where I assumed
there must be a simple way to spot the optimal rotation, so I never
thought it might have to be quadratic.  Presumably your algorithm tries
all the offsets and minimises the result.

Looking at it a bit more I can't see a better way (but that might be the
Ratafia de Champagne).  It feels as if there /should/ be one.  In fact
it feels as if it should be linear.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16156

On 12/25/22 4:44 PM, Ben Bacarisse wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> 
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
>>> I'm sorry to be obtuse, but what is the "conventional average"?  The
>>> name makes it sound trivial, but the quadratic time makes me certain
>>> that is isn't.
>>
>> Sorry, I meant to refer to your formulation of average
>>
>>      A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>>
>> where 'difference' means the shorter arc length.  This formula
>> matches the result for 'mean' on real numbers.
>>
>>> My "conventional average" algorithm (which is not well thought out) was
>>> to (a) rotate the data set to avoid the 23/0 boundary (not always
>>> possible), (b) take the arithmetic mean, and then (c) rotate the result
>>> back.  E.g. [23,0,1] -> [0,1,2] by adding one, and the average is
>>> mean[0,1,2] - 1 = 0.
>>
>> Yes, if you know where to split the cycle then the answer can be
>> found in O(n) time.  But how can we figure out where to split the
>> cycle?
> 
> Well I handily stopped considering this at the stage where I assumed
> there must be a simple way to spot the optimal rotation, so I never
> thought it might have to be quadratic.  Presumably your algorithm tries
> all the offsets and minimises the result.
> 
> Looking at it a bit more I can't see a better way (but that might be the
> Ratafia de Champagne).  It feels as if there /should/ be one.  In fact
> it feels as if it should be linear.
> 

I may have lost track of the problem, but wouldn't the addition of the 
points in two-dimensions and finding the center of gravity let you find 
the answer in O(N) time?

[toc] | [prev] | [next] | [standalone]

#16160

Richard Damon <Richard@Damon-Family.org> writes:

> On 12/25/22 4:44 PM, Ben Bacarisse wrote:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> I'm sorry to be obtuse, but what is the "conventional average"?  The
>>>> name makes it sound trivial, but the quadratic time makes me certain
>>>> that is isn't.
>>>
>>> Sorry, I meant to refer to your formulation of average
>>>
>>>      A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>>>
>>> where 'difference' means the shorter arc length.  This formula
>>> matches the result for 'mean' on real numbers.
>>>
>>>> My "conventional average" algorithm (which is not well thought
>>>> out) was to (a) rotate the data set to avoid the 23/0 boundary
>>>> (not always possible), (b) take the arithmetic mean, and then (c)
>>>> rotate the result back.  E.g. [23,0,1] -> [0,1,2] by adding one,
>>>> and the average is mean[0,1,2] - 1 = 0.
>>>
>>> Yes, if you know where to split the cycle then the answer can be
>>> found in O(n) time.  But how can we figure out where to split the
>>> cycle?
>>
>> Well I handily stopped considering this at the stage where I
>> assumed there must be a simple way to spot the optimal rotation, so
>> I never thought it might have to be quadratic.  Presumably your
>> algorithm tries all the offsets and minimises the result.
>>
>> Looking at it a bit more I can't see a better way (but that might
>> be the Ratafia de Champagne).  It feels as if there /should/ be
>> one.  In fact it feels as if it should be linear.
>
> I may have lost track of the problem, but wouldn't the addition of
> the points in two-dimensions and finding the center of gravity let
> you find the answer in O(N) time?

Finding the center of mass does give an answer in O(N) time, but
the answer it gives doesn't match the metric of minimizing the
squares of shorter arc lengths.  The results of the two metrics
can be, and usually are, different.

[toc] | [prev] | [next] | [standalone]

#16161

Richard Damon <Richard@Damon-Family.org> writes:

> On 12/25/22 4:44 PM, Ben Bacarisse wrote:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> 
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> 
>>>> I'm sorry to be obtuse, but what is the "conventional average"?  The
>>>> name makes it sound trivial, but the quadratic time makes me certain
>>>> that is isn't.
>>>
>>> Sorry, I meant to refer to your formulation of average
>>>
>>>      A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>>>
>>> where 'difference' means the shorter arc length.  This formula
>>> matches the result for 'mean' on real numbers.
>>>
>>>> My "conventional average" algorithm (which is not well thought out) was
>>>> to (a) rotate the data set to avoid the 23/0 boundary (not always
>>>> possible), (b) take the arithmetic mean, and then (c) rotate the result
>>>> back.  E.g. [23,0,1] -> [0,1,2] by adding one, and the average is
>>>> mean[0,1,2] - 1 = 0.
>>>
>>> Yes, if you know where to split the cycle then the answer can be
>>> found in O(n) time.  But how can we figure out where to split the
>>> cycle?
>> Well I handily stopped considering this at the stage where I assumed
>> there must be a simple way to spot the optimal rotation, so I never
>> thought it might have to be quadratic.  Presumably your algorithm tries
>> all the offsets and minimises the result.
>> Looking at it a bit more I can't see a better way (but that might be the
>> Ratafia de Champagne).  It feels as if there /should/ be one.  In fact
>> it feels as if it should be linear.
>
> I may have lost track of the problem, but wouldn't the addition of the
> points in two-dimensions and finding the center of gravity let you
> find the answer in O(N) time?

Yes.  It's been generally agreed that the vector average is the simplest
way to go.  Not only is it simple, it gives an answer to the question
when there is no meaningful average (the zero vector), and an indication
when the average is "unreliable" (a very short vector).

But there is another, one dimensional, average that minimises the sum of
the squares of the short-arc distances to all the data points.  It has
been argued that this average might be less surprising to users, but
it's tricky to calculate -- at least my first thoughts were way too
optimistic.  Tim has an algorithm for it but I don't know what his
method is.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16159

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> I'm sorry to be obtuse, but what is the "conventional average"?  The
>>> name makes it sound trivial, but the quadratic time makes me certain
>>> that is isn't.
>>
>> Sorry, I meant to refer to your formulation of average
>>
>>     A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>>
>> where 'difference' means the shorter arc length.  This formula
>> matches the result for 'mean' on real numbers.
>>
>>> My "conventional average" algorithm (which is not well thought
>>> out) was to (a) rotate the data set to avoid the 23/0 boundary
>>> (not always possible), (b) take the arithmetic mean, and then (c)
>>> rotate the result back.  E.g. [23,0,1] -> [0,1,2] by adding one,
>>> and the average is mean[0,1,2] - 1 = 0.
>>
>> Yes, if you know where to split the cycle then the answer can be
>> found in O(n) time.  But how can we figure out where to split the
>> cycle?
>
> Well I handily stopped considering this at the stage where I assumed
> there must be a simple way to spot the optimal rotation, so I never
> thought it might have to be quadratic.  Presumably your algorithm
> tries all the offsets and minimises the result.

Right.

> Looking at it a bit more I can't see a better way (but that might be
> the Ratafia de Champagne).  It feels as if there /should/ be one.
> In fact it feels as if it should be linear.

My best so far is only O( n * log n ).  Probably that isn't
optimal.  I don't see how to make it linear though.  Do you have
any ideas?

[toc] | [prev] | [next] | [standalone]

#16162

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> I'm sorry to be obtuse, but what is the "conventional average"?  The
>>>> name makes it sound trivial, but the quadratic time makes me certain
>>>> that is isn't.
>>>
>>> Sorry, I meant to refer to your formulation of average
>>>
>>>     A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }
>>>
>>> where 'difference' means the shorter arc length.  This formula
>>> matches the result for 'mean' on real numbers.
>>>
>>>> My "conventional average" algorithm (which is not well thought
>>>> out) was to (a) rotate the data set to avoid the 23/0 boundary
>>>> (not always possible), (b) take the arithmetic mean, and then (c)
>>>> rotate the result back.  E.g. [23,0,1] -> [0,1,2] by adding one,
>>>> and the average is mean[0,1,2] - 1 = 0.
>>>
>>> Yes, if you know where to split the cycle then the answer can be
>>> found in O(n) time.  But how can we figure out where to split the
>>> cycle?
>>
>> Well I handily stopped considering this at the stage where I assumed
>> there must be a simple way to spot the optimal rotation, so I never
>> thought it might have to be quadratic.  Presumably your algorithm
>> tries all the offsets and minimises the result.
>
> Right.
>
>> Looking at it a bit more I can't see a better way (but that might be
>> the Ratafia de Champagne).  It feels as if there /should/ be one.
>> In fact it feels as if it should be linear.
>
> My best so far is only O( n * log n ).  Probably that isn't
> optimal.  I don't see how to make it linear though.  Do you have
> any ideas?

No.  I should try with a clear head.

-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web