# Randomized recursive function

I recently came across the following recursion relation for a function $n(x)$:

$$n(x) = \begin{cases} 1 + \sum_{i=1}^m n(r_i x) ~,~ x>x_c \\ 0 ~, ~ x\leq x_c\end{cases}$$

here the $r_i\in[0,1]$'s have joint density function $\eta_m(r_1,r_2,\dots r_m)$ with the property that the marginal distribution of any of the $r_i$ is independent of $i$ and denoted $\eta_1(r)$.

Is it possible to understand the distribution of $n(x)$ for fixed $x_c$ and given $\eta_m$ ? Say for the case $\eta_m(r_1,r_2,\dots,r_m) = 1$? What about the average or variance of $n(x)$? How would I tackle this problem? How would I formally treat this problem? I think I am having a problem in looking at the problem in the right way and understanding what the probability space is...

EDIT: An example to clarify the problem. Suppose we choose $x_c=0.5$ and $m=2$:

• $x=1, r_1=0.8, r_2 = 0.2$ hence $n(1) = 1+ n(0.8) + n(0.2)$ now $n(0.2)=0$ because $0.2<0.5$.
• Hence we have to evaluate $n(0.8)$. Let $r_1$ and $r_2$ be such that $0.8r_1=0.7$ and $0.8r_2=0.1$. In this case: $n(0.8) = 1+n(0.7) + n(0.1)$. Again $n(0.1) = 0$ and we are left with $n(0.7)$.
• Let the random numbers in this case be such that $0.7r_1=0.3$ and $0.7r_2=0.4$ so we get $n(0.7) = 1 + n(0.4) + n(0.3)$. Because both 0.3 and 0.4 are less than $x_c=0.5$ we eventually have

$n(1) = 1 + 1 + 1 = 3$.

The thing is next time $n(1)$ can evaluate to something else. The recursive expansion happens based on the random numbers.

Below Python code that defines the function for the case $m=2$ and $\eta_2(r_1,r_2)$ uniform on all $(r_1,r_2)$ with $r_1+r_2=1$:

 from numpy.random import uniform def func(x,xc=.5): if x>xc: r = uniform() return 1+ func(r*x) + func((1-r)*x) else: return 0 

• It is not clear for me where is the recursion here - we have the same function $n(x)$ and same $x$ at the both sides. Could you clarify please? – Alexander Vigodner Jun 16 '14 at 22:42
• @AlexanderVigodner, $n(x)$ can be expressed as a sum of terms, each is the function $n(.)$ evaluated at a point $rx$, plus a constant term. It is similar to the recursive definition of the factorial, i.e. for $n\in \mathbb{N}$: $f(n) = nf(n-1)$ if $n> 0$ otherwise $f(n) = 1$ – antarcticfox Jun 17 '14 at 7:45
• yes, no if $r$ can be 1 then you have $n(x)$ at the both sides. – Alexander Vigodner Jun 17 '14 at 13:01
• Yes but if for example each $r$ is uniform in $[0,1]$ this event has measure zero. – antarcticfox Jun 17 '14 at 13:04
• I am still confused by your example. $n(x)$ is not deterministic. It's random via $r$ on the right hand side. So you cannot just evaluate $n(0.8)$ it changes. – Alexander Vigodner Jun 17 '14 at 13:27