When writing out some mathematical equation like we see on the picture here I got the problem of writing out all terms. I know what recursion means and have done recursion for example for the Fibonacci sequence as we see here:
f[0] = 0;
f[1] = 1;
f[n_] := f[n] = f[n - 1] + f[n - 2]
But obviously it is harder in my problem. So first of all I defined the generating function (in the paper this is $\phi_p (z)$.):
A[z_,p_] = ((1-p) + pz)^2;
which results in (In the paper this is $G_n(z)$):
G[n_,z_,p_] = A[z,p]^(2^n - 1) G[n-1, A[z,p] / A[z,1-p] ,p]
as we can see in the image below.
The problem is to compute this until $n=0$, I need to substitute at each step. For example if I want to go to $n-2$ i will set u = A[z,p] / A[z,1-p], where in the paper $u = s_{n-1} (z)$, futhermore note that $q_1 = 1-q_{-1}$ then we get:
G[n_,z_,p_] = A[z,p]^(2^(n - 1)) G[n-1,u,p]
$G_n(z) = \phi_{q{-1}}^{2^{n-1}}(z) G_{n-1}(s_{n-1}(z))$
G[n_,z_,p_] = A[z,p]^(2^(n - 1)) A[u,p]^(2^(n - 2)) G[n-2,u,p]
$G_n(z) = \phi_{q{-1}}^{2^{n-1}}(z) \phi_{q{-1}}^{2^{n-2}}(u) G_{n-2}(s_{n-2}(z))$
Thus it is some recursion with a substitution in each step. My main question is
How should I perform the substitution on each step so in the end i get some closed form dependent on only the variable $z$?
If one can do this one just needs to calculate the derivatives to get an analytical solution for the probabilities:
https://en.wikipedia.org/wiki/Probability-generating_function
Suppose we want to do this for $n = 2$ then we get after some calculation:
G[p_, z_] = A[1 - p, z]^2*A[1 - p, A[p, z]/A[1 - p, z]] *(0.5 + 0.5* A[p, A[p, z]/A[1 - p]]/A[1 - p, A[p, z]/A[1 - p]]).
I think that if i would write a programm it becomes like this:
u = z
for i in range n:
if i = n:
u2 = A[u,n,q] / A[u,n,1-q]
G(n-i,u,q) = 0.5*(1+ u2)
else:
u2 = A[u,n,q] / A[u,n,1-q]
G(n-i,u,q) = A[u,i,1-q]^(2^i-1) * G(i-2,u,q)
u = u2
However using this algorithm does not transform al substituted u's back to a formula that is only dependent of the variable $q$ and $z$. After some experimention i gained the following expressions which seem to work
:
When implementing this i noticed that the code is very slow. Are there any tricks/tips that can make my code faster than it is right now?
