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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 5, 2016 at 14:21

You must log in to answer this question.

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