[EM] Taylor or McLaurin polynomial for the complicated functions would reduce the numerical work.

[Michael Ossipoff]

On Sun, Jul 22, 2012 at 6:23 AM, Kristofer Munsterhjelm
<km_elmet at lavabit.com> wrote:
> On 07/21/2012 08:01 AM, Michael Ossipoff wrote:
>>
>> I spoke of using a polynomial approximation of G(q), the cumulative
>> state number,and differentiating it to get F(q), the
>> probability-density.
>>
>> I'd like to add that a Taylor or McLaurin polynomial approximation of
>> a complicated function could be used.  ...after you've determined, by
>> whatever method, exactly what the complicated function is to be, and
>> what its constants should be.
>
>
> For log-normal distributions, both the pdf and the cdf is defined and
> relatively simple. As would be expected of something related to the
> Gaussian, the cumulative distribution function involves the error function;
> but as long as you can calculate the error function, it's entirely possible
> to calculate the integral of the pdf (i.e. the cdf) directly without having
> to resort to numerical integration.

But it isn't the probability-density function that WBF needs an
integral of. It's (s(q)/q)*F(q), where F(q) is the probability-density
function.

>
> However, I don't think a divisor method making use of a log-normal
> approximation would retain the generality of Warren's exponential solution.

I wasn't trying to achieve anything relating to Warren's solution.
And, if the distribution is non-monotonic, has a peak, and, at the low
end, is an increasing function, then Warren's exponential assumption
can't be of any use for making an unbiased method. Not if there are
any states that could be in the region where it's an increasing
function.

As for Warren's solution: His main recommendation, a rounding-point
that, in the interval between integers n and n+1, is n+.495, results
in an allocation method whose bias is about the same as that of
Webster. Not really an improvement.

> So I guess we would have something between Warren's exact solution

Warren's exact solution for what? Certainly not for a rounding point
for an unbiased divisor method.


> and your
> numerical integration/root-finding situation:
>  the divisor formula would be
> something like f(x) = floor(x + g(x, a_1..a_n)) where a_1...a_n have to be
> found in an empirical manner, but where g(...) itself can be directly
> calculated instead of having to be found by numerical integration for each
> x.
>
> I could be wrong, though. It's been a while and I've been busy elsewhere, so
> perhaps I have missed something that would indicate that g would have to be
> numerically integrated every time, not just fitted.

Whether (s(q)/q)*F(q) is analytically antidifferentiable depends on
what F(q), the probability-density approximation-function is.

Is it analytically antidifferentiable if F is a log-normal function?
What about the more complicated distribution function that you
described?

And then, even if (s(q)/q)*F(q) is analytically antidifferentiable,
that antidiffentiation can, depending on F(q), result in an equation
which cannot be analytically solved for R, the rounding-point.

If F is log-normal, or the more complicated function that you
described, would there be an analytical solution for the
rounding-point R? It doesn't seem likely.

If F is approximated by a Taylor polynomial, then of course the
antidifferention is analytical. But it certainly looks to me, for the
reason that i gave earlier, that the resulting equation wouldn't be
analytically solvable for R, and would require the use of an iterative
equation-solving method.

One could choose a polynomial approximation for F(q) that would give
an analytical solution for R.

Mike Ossipoff