Painting a wall
Nick Wedd
paint it. Each painter is a different height, and paints as high as she
can reach but no higher. Each painter uses a different colour of paint.
After N years, what is the expected value of the number of visible
colours of paint?
Nick
--
Nick Wedd ni...@maproom.co.uk
Patrick Hamlyn
>A wall is painted every year. Each year a different painter is hired to
>paint it. Each painter is a different height, and paints as high as she
>can reach but no higher. Each painter uses a different colour of paint.
>
>After N years, what is the expected value of the number of visible
>colours of paint?
I think it makes a difference how tall the wall is. If it's higher than the
tallest painter can reach, then we need to know if it started out painted, as
this could significantly affect the result.
Assume no paint on the wall to start with, and it's taller than any painter.
Assume a uniform distribution of painter-heights, arriving in random order.
n expected number
1 1
2 1.5
3
There it's almost done, somebody can take over.
I'm going to guess it tends to n/(e^pi) as n gets large :>
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms...@egroups.com)
Mike
path@multipro.N_OcomSP_AM.au says...
> Nick Wedd <ni...@maproom.co.uk> wrote:
>
> >A wall is painted every year. Each year a different painter is hired to
> >paint it. Each painter is a different height, and paints as high as she
> >can reach but no higher. Each painter uses a different colour of paint.
> >
> >After N years, what is the expected value of the number of visible
> >colours of paint?
> I'm going to guess it tends to n/(e^pi) as n gets large :>
My prediction is that it tends to scale as n^0.5 as n
gets large.
Richard Heathfield
> Nick Wedd <ni...@maproom.co.uk> wrote:
>
>>A wall is painted every year. Each year a different painter is hired to
>>paint it. Each painter is a different height, and paints as high as she
>>can reach but no higher. Each painter uses a different colour of paint.
>>
>>After N years, what is the expected value of the number of visible
>>colours of paint?
>
> I think it makes a difference how tall the wall is. If it's higher than
> the tallest painter can reach, then we need to know if it started out
> painted, as this could significantly affect the result.
>
> Assume no paint on the wall to start with, and it's taller than any
> painter.
I agree that both these assumptions are reasonable, but...
> Assume a uniform distribution of painter-heights, arriving in
> random order.
...wouldn't a normal distribution be more likely? (Bell curve.)
> n expected number
> 1 1
> 2 1.5
> 3
>
> There it's almost done, somebody can take over.
>
> I'm going to guess it tends to n/(e^pi) as n gets large :>
I'm going to guess that it depends very much on the distribution model.
--
Richard Heathfield : bin...@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
Mark Thornquist
> Patrick Hamlyn wrote:
>
>
>>Nick Wedd <ni...@maproom.co.uk> wrote:
>>
>>
>>>A wall is painted every year. Each year a different painter is hired to
>>>paint it. Each painter is a different height, and paints as high as she
>>>can reach but no higher. Each painter uses a different colour of paint.
>>>
>>>After N years, what is the expected value of the number of visible
>>>colours of paint?
>>
>>I think it makes a difference how tall the wall is. If it's higher than
>>the tallest painter can reach, then we need to know if it started out
>>painted, as this could significantly affect the result.
>>
>>Assume no paint on the wall to start with, and it's taller than any
>>painter.
>
>
> I agree that both these assumptions are reasonable, but...
>
>
>
>>Assume a uniform distribution of painter-heights, arriving in
>>random order.
>
>
> ...wouldn't a normal distribution be more likely? (Bell curve.)
>
>
>>n expected number
>>1 1
>>2 1.5
>>3
>>
>>There it's almost done, somebody can take over.
>>
>>I'm going to guess it tends to n/(e^pi) as n gets large :>
>
>
> I'm going to guess that it depends very much on the distribution model.
>
are the same height. Whether or not you can see the color from a
particular painter depends only on whether any of the painters
who followed her were taller, not by how much taller they were.
So without loss of generality the N painters had heights 1, 2,
..., N.
--
Mark Thornquist
David W. Cantrell
> On Tue, 17 Feb 2004, Nick Wedd wrote:
> >
> > A wall is painted every year. Each year a different painter is hired
> > to paint it. Each painter is a different height, and paints as high as
> > she can reach but no higher. Each painter uses a different colour of
> > paint.
> >
> > After N years, what is the expected value of the number of visible
> > colours of paint?
>
>
> N years C colors of paint
> 1 1
> 2 1.5
> 3 1.83333
> 4 2.08333
> 5 2.28333
> 6 2.45
> 7 2.59286
> 8 2.71786
> 9 2.82897
> 10 2.92897
> 11 3.01988
These are the harmonic numbers. See, for example,
<http://mathworld.wolfram.com/HarmonicNumber.html>.
> My TI-83 doesn't reveal any really compelling formula fitting
> those points, though. :) Something with logarithms looks likely,
Yes, that guess is correct asymptotically.
David
Phil Carmody
> Patrick Hamlyn wrote:
>
> > Nick Wedd <ni...@maproom.co.uk> wrote:
> >
> >>A wall is painted every year. Each year a different painter is hired to
> >>paint it. Each painter is a different height, and paints as high as she
> >>can reach but no higher. Each painter uses a different colour of paint.
> >>
> >>After N years, what is the expected value of the number of visible
> >>colours of paint?
> >
> > I think it makes a difference how tall the wall is. If it's higher than
> > the tallest painter can reach, then we need to know if it started out
> > painted, as this could significantly affect the result.
> >
> > Assume no paint on the wall to start with, and it's taller than any
> > painter.
> I'm going to guess that it depends very much on the distribution model.
Au contraire. As long as no painters are the same height (one of the
assumptions) then all that matters is that there's an ordering relation
between the painters, which may as well be an index over |N rather than
a height in |R.
Phil
--
Unpatched IE vulnerability: NavigateAndFind file proxy
Description: cross-domain scripting, cookie/data/identity theft, command execution
Reference: http://safecenter.net/liudieyu/NAFfileJPU/NAFfileJPU-Content.HTM
Exploit: http://safecenter.net/liudieyu/NAFfileJPU/NAFfileJPU-MyPage.htm
Phil Carmody
> On Tue, 17 Feb 2004, Nick Wedd wrote:
> >
> > A wall is painted every year. Each year a different painter is hired to
> > paint it. Each painter is a different height, and paints as high as she
> > can reach but no higher. Each painter uses a different colour of paint.
> >
> > After N years, what is the expected value of the number of visible
> > colours of paint?
>
> By brute force, I've computed these numbers:
>
> N years C colors of paint
[annotated]
> 1 1 = 1/1!
> 2 1.5 = 3/2!
> 3 1.83333 = 11/3!
> 4 2.08333 = 50/4!
> 5 2.28333 = 274/5!
http://www.research.att.com/~njas/sequences/
Matches (up to a limit of 30) found for 1 3 11 50 274 :
...
Name: Stirling numbers of first kind s(n,2): a(n+1)=(n+1)*a(n)+n!.
...
Also a(n) = n!*Sum 1/i, i=1..n = n!*H(n), H(n) = harmonic number
Phil
--
Unpatched IE vulnerability: Alexa Related Privacy Disclosure
Description: Unintended disclosure of private information when using the Related feature
Reference: http://www.secunia.com/advisories/8955/
Reference: http://www.imilly.com/alexa.htm
Risto Lankinen
"Nick Wedd" <ni...@maproom.co.uk> wrote in message
news:yfC$KBIvIp...@maproom.demon.co.uk...
> A wall is painted every year. Each year a different painter is hired to
> paint it. Each painter is a different height, and paints as high as she
> can reach but no higher. Each painter uses a different colour of paint.
>
> After N years, what is the expected value of the number of visible
> colours of paint?
Finding out how much fun it is to compete in high painting,
the painters go on to form Word High Painting Association
(WHPA) to promote and manage competitions in the fine
sport of high painting.
So comes the time to nominate the first World Champion
of High Painting. Just the pioneering painters of the wall
inciting the whole sport are given the honor of being able to
participate in the inaugural event. They gather to the only
venue worthy of culmination of this scale, the Great Wall
of China. After flags are flown and anthems sung, the race
is good to go.
It is agreed that all painters will have one go for the title and
that they will perform one at a time, but they will do so in the
reverse order from the original. The first competitor prepares
to choose her color. She carefully scans the sea of full paint
cans with her eyes, and finally homes in to... Mauve!
As the crowd is in suspense watching the paint of the first
competitor to dry, the announcer notifies them that since it is
a new sport anyway, this will be the new world record. After
a few oohs and aahs from the crowd, they start speculating
about how many times the competition will produce a new
world record.
After the lengthy and tiresome race is over, they are amazed
to realize that the new world record holders (though most of
them only momentarily) are exactly the same painters whose
efforts are perpetually recorded in the original Wall of Fame.
- - -
So, how many times did the world record change hands during
the race, on average?
1 competitor -> 1
2 competitors -> 1 + 1/2
3 competitors -> 1 + 1/2 + 1/3
...
N competitors -> 1 + 1/2 + 1/3 + ... + 1/N
Cheers!
- Risto -
Eric Farmer
> "Arthur J. O'Dwyer" <a...@nospam.andrew.cmu.edu> writes:
>
> > On Tue, 17 Feb 2004, Nick Wedd wrote:
> > >
> > > A wall is painted every year. Each year a different painter is hired to
> > > paint it. Each painter is a different height, and paints as high as she
> > > can reach but no higher. Each painter uses a different colour of paint.
> > >
> > > After N years, what is the expected value of the number of visible
> > > colours of paint?
> >
> > By brute force, I've computed these numbers:
> >
> > N years C colors of paint
> [annotated]
> > 1 1 = 1/1!
> > 2 1.5 = 3/2!
> > 3 1.83333 = 11/3!
> > 4 2.08333 = 50/4!
> > 5 2.28333 = 274/5!
>
> http://www.research.att.com/~njas/sequences/
>
> Matches (up to a limit of 30) found for 1 3 11 50 274 :
> ...
> Name: Stirling numbers of first kind s(n,2): a(n+1)=(n+1)*a(n)+n!.
> ...
> Also a(n) = n!*Sum 1/i, i=1..n = n!*H(n), H(n) = harmonic number
No one seems to have shown yet that this is indeed the solution
(hopefully I haven't missed it). Consider the n {0,1}-indicator
random variables X_k, 1<=k<=n, where X_k is 1 iff the k-th tallest
painter's color remains visible. The key observation is that X_k is
independent of when the shorter painters k+1 through n step up to the
wall, and is thus equal to 1 iff painters 1 through k-1 all paint
before painter k. This happens with probability 1/k, so the desired
expected value is
Sum[E[X_k], {k, 1, n}]
== Sum[P[X_k == 1], {k, 1, n}]
== Sum[1/k, {k, 1, n}]
== H[n]
Eric Farmer
Nick Wedd
<rlan...@hotmail.com> writes
Well done, this is excellent! Congratulations to Risto Lankinen!
It is much simpler and easier to understand than my solution. This
begins by proving the recurrence relation
e(N+1) = 1 + (mean over M=0..N) of ( e(M) )
and then proves the above answer by some tricky manipulation.
By the way - as N increases the answer tends towards ln(N) + 1/sqrt(3).
David W. Cantrell
> By the way - as N increases the answer tends towards ln(N) + 1/sqrt(3).
Not quite! The constant term is slightly smaller than the one you've given.
It is precisely the Euler-Mascheroni constant, usually denoted as gamma.
If interested, see
<http://mathworld.wolfram.com/Euler-MascheroniConstant.html>.
So, as N increases, the answer tends towards ln(N) + gamma.
David
Graeme Thomas
<ni...@maproom.co.uk> writes
>It is much simpler and easier to understand than my solution. This
>begins by proving the recurrence relation
> e(N+1) = 1 + (mean over M=0..N) of ( e(M) )
>and then proves the above answer by some tricky manipulation.
>
>By the way - as N increases the answer tends towards ln(N) + 1/sqrt(3).
Not quite. H(n) = ln n + \gamma + 1/2n - 1/12n^2 + 1/120n^4 + O(n^-6).
The constant \gamma (Euler's constant) is 0.577215665-, whereas
1/sqrt(3) is 0.577350269+.
(A more precise formula for H(n) is:
H(n) = ln n + \gamma + 1/2n - \sum{1, m, B(2k)/2kn^(2k) + R,
where B(n) are Bernoulli numbers, and R is given by
R = (\theta(m, n) * B(2m + 2))/(2m+2)n^(2m+2)
where \theta(m, n) is a constant between 0 and 1.
The Bernoulli numbers are
n 2 4 6 8 10 12
B(n) 1/6 -1/30 1/42 -1/30 5/66 -691/2730
)
--
Graeme Thomas
Eric Farmer
This is not quite true; the limit of the difference between H(n) and
ln n is 0.5772156649..., where 1/sqrt(3) = 0.57735... Search "Euler
gamma" or "Euler-Mascheroni".
Eric Farmer
Leroy Quet
Ah, harmonic numbers, we meet again...
For those who care...
Anyone doing a search for both "Leroy Quet" and "harmonic numbers" on
Google's sci.math will come up with a lot of hits, for I have posted
much regarding these over the last few years...
;)
thanks,
Leroy Quet