3
$\begingroup$

hypothesis: for any finite sequence of random positive integers exists a generating function.

If the hypothesis is true, is there a structured way of finding a generating function for a finite sequence of random positive integers?

Here is what I understand from the past 2 days of reading:

A generating function for Fibonacci numbers - eventhough it doesn't have much to do with my question - is: \begin{eqnarray*} \frac{1}{1− (x + x ^ 2)} \end{eqnarray*} where: \begin{eqnarray*} \frac{1}{1− (x + x ^ 2)} =1 + x + 2 x ^ 2 + 3 x ^ 3 + 5 x ^ 4 + 8 x ^ 5+ \cdots \end{eqnarray*} The coefficients are Fibonacci numbers, i.e. the sequence {1,1,2,3,5,8,13,21, ...}.

But if I have a finite sequence of random numbers, for example {4,5,0,9,1,5} Is there a method of finding its generating function?

| cite | improve this question | |
$\endgroup$
  • 4
    $\begingroup$ Cf. finite impulse response (FIR) filter. $\endgroup$ – copper.hat Apr 7 at 22:11
  • 5
    $\begingroup$ Generating functions are defined for infinite sequences. Should we assume that your finite sequence continues with "0,0,0,..."? Or should we assume that there are further elements after the ones you have specified but they are unknown? $\endgroup$ – Federico Poloni Apr 8 at 9:29
  • 10
    $\begingroup$ I'd recommend saying arbitrary instead of random if you don't talk about random processes at all. And if you do really mean random processes, be precise about distributions. Often people will say that a (perfect) die is "random", but a faked die with 30%-70% chances for head-tail is not random -- which is wrong! It's no longer uniformly random, that's true. $\endgroup$ – ComFreek Apr 8 at 12:09
  • 1
    $\begingroup$ Reply to @FedericoPoloni: I always thought of a finite series as an infinite series that continues with "0,0,0,..." (as it relates to my problem). Would that still be possible if I gave you this information? $\endgroup$ – knowledge_seeker Apr 8 at 12:25
  • 2
    $\begingroup$ Yes, @RobPratt's answer below is correct assuming that your (finite) sequence is padded with zeros. That is a reasonable convention in this context. $\endgroup$ – Federico Poloni Apr 8 at 12:36
23
$\begingroup$

For a sequence with finitely many nonzero values, the corresponding generating function is just a polynomial. Your example has generating function $4+5x+9x^3+x^4+5x^5$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Why is there a non-zero constraint? If the whole finite sequence is just zeros, wouldn't that be a constant function? Constant functions are polynomials. What's your perspective on this? $\endgroup$ – Galen Apr 8 at 16:13
  • 4
    $\begingroup$ @Galen: It's the opposite of infinitely many nonzero values. The zero polynomial is fine, it has no nonzero terms, and that's finitely many. $\endgroup$ – Hans Lundmark Apr 8 at 16:35
  • $\begingroup$ I follow that. Thanks! $\endgroup$ – Galen Apr 8 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.