Re: "Central term" (median) for a very very large set of numbers

Snipped because the ordering was severely messed up.

On Aug 17, 11:12 am, pamela fluente <pamelaflue...@xxxxxxxxx> wrote:
On 16 Ago, 15:45, Randy Poe <poespam-t...@xxxxxxxxx> wrote:
1. Suppose your current estimate q is the correct
median. Then the expectation value of the next
step is: 0.5*(-delta) + 0.5*(+delta) = 0. On
average, the median estimate is stable when it is
correct.

Actually, here I am failing to see how this would
lead to a consistent estimate of the median (?).

When the estimator is too low, it is more likely
to increase in the next step. When it is too high,
it is more likely to decrease in the next step.

Could you make some example with actual numbers
to show how your algorithm works?

Here is a very simple-minded demonstration based
on 200 random samples in Matlab.

Here are the samples:
24, 6, 15, 12, 22, 19, 11, 0, 21, 11, 15, 20, 23, 18,
4, 10, 23, 23, 10, 22, 1, 9, 20, 0, 3, 5, 5, 15, 7, 5,
0, 19, 11, 23, 12, 10, 21, 13, 5, 17, 21, 0, 17, 9, 21,
13, 18, 11, 8, 5, 5, 17, 8, 14, 4, 17, 9, 22, 21, 15,
12, 22, 21, 16, 20, 17, 9, 7, 9, 13, 18, 8, 21, 14, 9,
18, 14, 11, 17, 16, 20, 24, 13, 22, 4, 24, 7, 6, 22, 18,
3, 0, 22, 5, 7, 17, 7, 12, 2, 25, 15, 11, 13, 8, 11, 6,
14, 19, 13, 16, 5, 9, 20, 17, 12, 14, 20, 1, 15, 1, 10,
8, 22, 0, 19, 24, 25, 20, 11, 12, 5, 16, 8, 24, 18, 10,
19, 7, 11, 23, 17, 5, 21, 16, 3, 5, 15, 16, 9, 14, 11,
1, 1, 8, 0, 10, 17, 2, 1, 15, 15, 0, 0, 5, 15, 1, 9, 16,
18, 17, 2, 11, 11, 9, 4, 17, 17, 18, 12, 14, 3, 11, 18,
22, 7, 6, 22, 6, 20, 23, 6, 6, 1, 2, 16, 5, 21, 4, 4, 25

The median of this data according to Matlab is 12.

With mest = median estimator and delta = step size, the
algorithm is:

if (x > mest)
mest = mest + delta;
elseif (x < mest)
mest = mest - delta;
end

With a starting estimate of mest = 0 and a delta of 0.2,
here is the result of iterating over that data sample:
i=1,x=24,median(est)=0.2
i=2,x=6,median(est)=0.4
i=3,x=15,median(est)=0.6
i=4,x=12,median(est)=0.8
i=5,x=22,median(est)=1.0
i=6,x=19,median(est)=1.2
i=7,x=11,median(est)=1.4
i=8,x=0,median(est)=1.2
i=9,x=21,median(est)=1.4

. . .

i=95,x=7,median(est)=10.6
i=96,x=17,median(est)=10.8
i=97,x=7,median(est)=10.6
i=98,x=12,median(est)=10.8
i=99,x=2,median(est)=10.6
i=100,x=25,median(est)=10.8
i=101,x=15,median(est)=11.0
i=102,x=11,median(est)=11.2
i=103,x=13,median(est)=11.4
i=104,x=8,median(est)=11.2
i=105,x=11,median(est)=11.0

. . .

i=197,x=21,median(est)=11.0
i=198,x=4,median(est)=10.8
i=199,x=4,median(est)=10.6
i=200,x=25,median(est)=10.8

Now, as a really crude way of simulating how
it would work with a longer sample and a
"cooling" schedule, let's run it starting with
this estimate, with the same input data and
delta reduced to 0.1:
....
i=193,x=1,median(est)=11.7
i=194,x=2,median(est)=11.6
i=195,x=16,median(est)=11.7
i=196,x=5,median(est)=11.6
i=197,x=21,median(est)=11.7
i=198,x=4,median(est)=11.6
i=199,x=4,median(est)=11.5
i=200,x=25,median(est)=11.6

And another 200 samples with delta = 0.05:
.. . .
i=190,x=23,median(est)=12.1
i=191,x=6,median(est)=12.0
i=192,x=6,median(est)=12.0
i=193,x=1,median(est)=11.9
i=194,x=2,median(est)=11.9
i=195,x=16,median(est)=11.9
i=196,x=5,median(est)=11.9
i=197,x=21,median(est)=11.9
i=198,x=4,median(est)=11.9
i=199,x=4,median(est)=11.8
i=200,x=25,median(est)=11.9

- Randy

.

Quantcast