3
$\begingroup$

I am assessing the probability distribution on a running time of some algorithm that we've developed. I am looking for a family of probability mass functions $f_n$ with the following recurrence: $$ f_{n}(k)=qf_{n-1}(k)+p\sum_{i=1}^{k-1}f_{n-1}(i)f_{n-1}(k-i), $$ with the starting term $$ f_{0}(k)=\begin{cases} 1; & k=1,\\ 0; & \mbox{otherwise.} \end{cases} $$

In terms of generating function $F_{n}(x)=\sum_{i=0}^{\infty}f_{n}(i)\,x^{i}$ this simplifies to $$ F_{n}(x)=qF_{n-1}(x)+pF_{n-1}(x)^{2}, $$ but (as Ser B. pointed out) it looks like $F_n(x)$ does not seem to admit closed-form expression. That said, finding a value of $\frac{\partial F_n}{\partial x}$ where $x=1$ would also help, as this should equal to the expected value of $k$ in the space with probability mass function $f_n$.

As you might expect, we have $q=1-p$ and $ p,q \in [0,1]$. I have asked this question on M.SE, but received no response; I hope it is appropriate to post it here.

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you looking for a closed-form expression for the generating function, as a function of $x$ and $p$, or would a closed form expression for $f_n(k)$ be satisfactory? for $\endgroup$
    – Mark Fischler
    Feb 29, 2016 at 23:26
  • $\begingroup$ As is written, I am initially looking for $f_n(k)$. The generating function approach was just one way of representing problem with in a simpler form (or so I thought). As you pointed out in your answer it looks that this is not the case. $\endgroup$
    – Matjaž Krnc
    Mar 4, 2016 at 13:24
  • 2
    $\begingroup$ $F_n$ ``counts'' the no. $Z_n$ of individuals in the $n-$th generation of a Galton-Watson process with reproduction function $F(s)=qs+ps^2$. Thus (look up the literature) $\mathbb{E} Z_n=m^n$, $\mathrm{Var}(Z_n)=\sigma^2 m^{n-1}{m^n-1 \over m-1}$ where $m=\mathbb{E}(Z_1)=1+p, \sigma^2={\mathrm{Var}}(Z_1)=pq$. Further $${Z_n \over m}\longrightarrow W\;\;\mbox{a.s.}$$ where $W$ is positive on $\{Z_n\longrightarrow \infty\}$, and the Laplace transform $\ell$ of $W$ is characterized by the the equation $\ell(mt)=q\ell(t)+p\ell(t)^2$, and right derivative $-\ell^\prime(0)=1$ in $0$. $\endgroup$
    – esg
    Mar 4, 2016 at 18:24
  • $\begingroup$ Thanks guys! The connection of my problem with Galton-Watson process, as well as with Mandelbrot fractal is most appreciated! I will make sure to study G-W process in detail; and close this question. $\endgroup$
    – Matjaž Krnc
    Mar 5, 2016 at 22:39
  • $\begingroup$ Please note the obvious typo, should be ${Z_n \over m^n}$ instead of ${Z_n \over m}$ above. $\endgroup$
    – esg
    Mar 9, 2016 at 20:01

1 Answer 1

Reset to default
2
$\begingroup$

I do not think it is possible to get a closed-form of either $f_n$ or $F_n$.

For brevity, let's rewrite your recurrence equation for the generating function $a_n:=F_n(x)$ as $a_n = q a_{n-1} + p a_{n-1}^2$ with the initial condition $a_0=x$. Then, change of variables $b_n = p a_n + \frac{q}{2}$ will reduce this equation to $b_n = \frac{(1+p)q}{4} + b_{n-1}^2$ with $b_0 = p x + \frac{q}{2}$, which is known as a quadratic map generating the Mandelbrot set and is not generally closed-form solvable. See [1], which gives more info on possible solutions; however, it will only get you so far that you can find $F_n(x)$ for some specific points $x$. I guess this is of little interest in your situation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for a productive answer! I edited the question accordingly. As we are dealing with a generating function, we are usually never interested in $F_n(x)$ for specific points $x$, but rather for individual coefficients. That said, I would be also interested in a value of $\frac{\partial F_n}{\partial x}$ where $x=1$, which should be the same as the expected value of $k$ in the space with probability mass function $f_n$. Anyway; do you think that your answer implies that also $f_n(k)$ do not admit a closed-form representation? $\endgroup$
    – Matjaž Krnc
    Mar 4, 2016 at 13:42
  • $\begingroup$ Yes, I'm pretty sure that $f_n(k)$ does not admit any nice representation. If you had one, you'd be able to put it into the sum which defines $F_n(x)$ and get a closed-form expression for the latter. As to the moments, you can get all of them in a subsequent manner. However, again you can't get a closed-form solution for all the moments at once. Esg mentioned one way to look at it, the only thing I can add is you can use more direct calculations. Just taking derivatives of $F_n(x)=qF_{n-1}(x)+pF^2_{n-1}(x)$ at x=1 will lead you to linear equations, that can be solved effectively. $\endgroup$
    – SM2
    Mar 5, 2016 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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