[EM] IRV ballot pile count (proof of closed form)

[robert bristow-johnson]

On Feb 2, 2010, at 2:28 PM, robert bristow-johnson wrote:

>
> Warren tells me that
>
>     C-1
>     SUM{ C!/n! }
>     n=1
>
> has a closed form, but didn't tell me what it is.  does someone  
> have the closed form for it?  i fiddled with it a little, and i can  
> certainly see an asymptotic limit of
>
>     (e-1)(C!)
>
> as C gets large, but i don't see an exact closed form for it.  if  
> someone has such a closed form, would you mind sharing it?

Okay, I spent a little time working on this and figgered it out.  The  
fact that the number of distinct piles needed to represent all  
possible manners of *relatively* ranking C candidates (no ties except  
unranked candidates are tied for lowest rank) is

     C-1
     SUM{ C!/n! }  =  floor( (e-1) C! ) - 1
     n=1

I was at first unconvinced that the right hand side is an exact  
closed form for the left, but now accept that it is.

The proof requires as given:

     inf
     SUM{ 1/n! }  =  e  ~=  2.718281828...
     n=0


The floor(a) function which returns the only integer such that

     a-1  <  floor(a)  <=  a

and, if n is an integer, then

    floor(a + n) = floor(a) + n      for any a.


It also requires knowledge that if C and n are integers and C >= n, then

    C!/n!  = C(C-1)(C-2)(C-3)...(n+1) = integer

 From that

              inf                     C-1                        inf
     C! e  =  SUM{ C!/n! }  =  C!  +  SUM{ C!/n! }  +  C!/C!  +  SUM 
{ C!/n! }
              n=0                     n=1                       n=C+1

or

                     C-1                    inf
     C! e  =  C!  +  SUM{ C!/n! }  +  1  +  SUM{ C!/n! }
                     n=1                   n=C+1


The first three terms on the RH are integers.  The last term

     inf
     SUM{ C!/n! }  =  1/(C+1) + 1/[(C+1)(C+2)] + 1/[(C+1)(C+2)(C+3)]  
+ ...
    n=C+1

is less than

     inf
     SUM{ C!/n! }  <  1/C + 1/C^2 + 1/C^3 + ...
    n=C+1

which is

     inf                    inf
     SUM{ C!/n! }  <  (1/C) SUM{ (1/C)^j }   =  (1/C)/[1 - (1/C)]  =   
1/(C-1)
    n=C+1                   j=0

which is less than 1 for any C > 2.  So we know that the last term in


                     C-1                    inf
     C! e  =  C!  +  SUM{ C!/n! }  +  1  +  SUM{ C!/n! }
                     n=1                   n=C+1

is less than 1.


Then applying the floor() function to both sides yields

                                   C-1                    inf
     floor(C! e)  =  floor( C!  +  SUM{ C!/n! }  +  1  +  SUM{ C!/n! } )
                                   n=1                   n=C+1

which is

                            C-1                           inf
     floor(C! e)  =  C!  +  SUM{ C!/n! }  +  1  +  floor( SUM{ C!/n! } )
                            n=1                          n=C+1


Since the argument of the floor() function on the right is less than  
1, the returned value of the floor() function is known to be zero.


                            C-1
     floor(C! e)  =  C!  +  SUM{ C!/n! }  +  1
                            n=1

Resulting in


     C-1
     SUM{ C!/n! }  =  floor( (e-1) C! ) - 1
     n=1

at least for any integer C greater than 2.



I do this kinda thing all the time at comp.dsp or the music-dsp  
mailing list, but haven't done this before outside of those two  
technical contexts.    It was kinda fun.

Thanks Warren, for the hint.

--

r b-j                  rbj at audioimagination.com

"Imagination is more important than knowledge."