How do I solve the implicit equation $G(z) = z \sum_{k=0}^\infty f_K(k) G(z)^k$ for $G$?

40 Views Asked by At

I have run into a probability problem that leads to an implicit equation for a function $G: \mathbb{C} \rightarrow \mathbb{C}$. Given a known probability mass function $f_K$ on the non-negative integers, the function $G$ is defined implicitly by the equation: $$G(z) = z \sum_{k=0}^\infty f_K(k) G(z)^k \quad \quad \quad \text{for all } |z| \leqslant 1.$$

Question: Is there a general explicit solution for $G$, and if so, what is it? Even if there is no explicit solution for this function, is there an effective way to compute it (or its derivatives) from the mass function $f_K$?

1

There are 1 best solutions below

1
On

With the ansatz $G(z)=a_0+a_1z+a_2z^2+\cdots$, we immediately get $$a_0=0$$ and observe that $a_{n+1}$ can be found once $a_1,\ldots,a_{n}$ are known because on the right hand side, only summands up to $k=n$ contribute to $a_{n+1}$. Expanding on this idea, we find $$\begin{align}a_n&=\sum_{k=0}^{n-1}f_K(k)\cdot(\text{coefficient of }x^{n-1}\text{ in }G(z)^k)\\ &=\sum_{k=0}^{n-1}f_K(k)\sum_{(i_1,\ldots,i_k)\atop i_1+\cdots+i_r=n-1}\,\prod_{j=1}^ka_{i_j}\end{align} $$ where we can strike out all cases where some $i_j=0$ right away. In particular, we find $$a_1=f_K(0)$$ $$ a_2=f_K(1)f_K(0)$$ $$ a_3=f_K(1)^2f_K(0)+f_K(2)f_K(0)^2$$ and we already see a bit of a pattern: $a_n$ is a sum of products, where each product has $n$ factors $f_K(\cdot)$ and the arguments to $f_K$ add up to $n-1$. This also follows readily by induction from the recursion formula above. Thereby, the summands correspond to partitions of $n-1$ into $n$ non-negative summands, but different to what the first few cases suggest, the coefficients per partition need not always be $=1$.

Note that $f_K(0)$ leads to $G(z)=0$. So assume $f_K(0)>0$. We can at least determine necessary conditions for $G$ to be entire: Let $m>0$. Then certainly $f_K(m)^rf_K(0)^{(m-1)r}$ occurs among the summands for $a_{rm}$. We conclude $$ \limsup_{n\to\infty} \sqrt[n]{a_n}\ge \limsup_{r\to\infty} \sqrt[mr]{a_{mr}}\ge\limsup_{r\to\infty}\sqrt[mr]{f_K(m)^rf_K(0)^{(m-1)r}}=\sqrt[m]{f_K(m)}f_K(0).$$ Hence $G$ can only be entire when $f_K(m)=0$ for all $m>0$.