-1
$\begingroup$

I have stumbled upon this very interesting question. Given an additive LFG:

LFG(n) = LFG(n-k) + LFG(n-j) mod m, with LFG(0) ... LFG(k) given

What could be the maximum mean and variance? It seemed to me that this would evenly return numbers on both sides of the domain. Therefore the maximum mean would be at m/2. I've tried to find a configuration where this would not be the case, and I've found one. But I cannot see where I was wrong.

The data that gives more than m/2 is

k = 3, j = 1, m = 2 LFG(0) = 1, LFG(1) = 1, LFG(2) = 1

The resulting mean is 0.57, which comes from the fact that the generator returns a series of period equal to 7. The series: 0 1 0 0 1 1 1.

$\endgroup$
2
  • $\begingroup$ What is your choice of $m$ for your proposed counterexample, and what evidence do you have to support your belief that such a counterexample in fact does work? $\endgroup$
    – heropup
    Nov 23, 2015 at 22:34
  • $\begingroup$ updated by question with the issing info $\endgroup$ Nov 23, 2015 at 22:38

1 Answer 1

1
$\begingroup$

I am a bit confused. Your example with $m = 2$ does not support your claim that the mean of the sequence exceeds $m/2 = 1$, since $4/7 < 1$.

Furthermore, I should point out that under the assumption that the sequence is uniformly distributed, the mean would be $(m-1)/2$, not $m/2$, because no element of the sequence can attain $m$; all values are in $\{0, 1, \ldots, m-1\}$. So under this modification, yes, your counterexample does work.

Moreover, there are many less trivial counterexamples that are easily found, in both directions: that is to say, the mean can be quite a bit lower than $(m-1)/2$, as well as larger: if $m = 67$, then the period is only $P(m) = 33$, and the sequence consists of $$\{1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 21, 62, 55, 9, 4, 59, 1, 5, 64, 65, 3, 0, 65, 1, 1, 66, 0, 1, 0, 0 \}.$$ Its mean is $\frac{670}{33} \approx 20.303$ which is significantly smaller than $(67-1)/2 = 33$. In the other direction, $m = 159$ has a period of $P(m) = 936$ (its length is too much to include here in its entirety), with mean $\frac{12455}{156} \approx 79.8397$, exceeding $(159-1)/2 = 79$. On the basis of these small-$m$ examples, we have no reason to expect that this generator should be unbiased, let alone uniformly distributed on $\{0, \ldots, m-1\}$.

What would be interesting to try to answer, however, is whether the behavior of this generator is asymptotically unbiased for large $m$, in the sense that $$\limsup_{m} \left|\bar F_{m} - \frac{m - 1}{2}\right| = 0$$ where $\bar F_{m}$ represents the mean of the lagged Fibonacci generator (for your given choice of parameters) over its period? I am going to guess that it is not, based on the results of the following plot of $(m-1)/2 - \bar F_m$ for $m = 2, \ldots, 400$: enter image description here

$\endgroup$
1
  • $\begingroup$ Great answer, I am wondering though if there is any way to find the maximum mean through some more complicated math instead of testing all the possibilities $\endgroup$ Nov 24, 2015 at 15:43

Not the answer you're looking for? Browse other questions tagged .