How can I find the distribution of a recursive relation with two parameters?

Question

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also $G: \mathbb{Z}_p \times \mathbb{Z}_p \rightarrow F$. There are enough initial points such that $G(n,m)$ terminates finitely for finite $m$ and $n$.

I want to compute the distribution of this relation over the field $F$ and then compare it to some other distribution, e.g. uniform or Gaussian distribution. The question is how can I do that? I have searched a lot, but could not find an answer. Even search terms are appreciated.

The reason I want to do this is proving hardness of the problem whose solution is finding $n$ and $m$ when $F(n,m)$ is given.

Thanks in advance.

Answer 1

I've never done an exact solution for a "change of variable" problem with a recursive function, but I can give you a formula that might help. If $p : \mathbb{Z}_p \times \mathbb{Z}_p \to [0,1]$ is a probability mass function (i.e. sums to one over its domain), then the probability of any specific output for $G$ is

$$\mathrm{Pr}[x]\ =\ \sum_{(n,m) \in G^{-1}(\{x\})} p(n,m)$$

where $G^{-1} : \mathcal{P}(F) \to \mathbb{Z}_p \times \mathbb{Z}_p$ computes preimages under $G$ by

$$G^{-1}(A)\ =\ \{(n,m) \in \mathbb{Z}_p \times \mathbb{Z}_p\ \lvert\ G(n,m) \in A\}$$

In other words, it's the sum of the probabilities of the pairs $(n,m)$ for which $G(n,m) = x$.

Despite the size of the formula, there are advantages to having it in terms of preimages. Unlike inverses, they always exist. They are often compositional, meaning that preimages under a function can often be defined in terms of preimages under its defining subexpressions, which is often necessary when dealing with recursion. For example, if $f : A \to B$ and $g : B \to C$, then

$$(g \circ f)^{-1}\ =\ f^{-1} \circ g^{-1}$$

Another: if $f_1 : A \to B_1$, $f_2 : A \to B_2$, and $f : A \to B_1 \times B_2$ is defined by $f(x) = (f_1(x),f_2(x))$, then

$$f^{-1}(B_1' \times B_2')\ =\ f_1^{-1}(B_1') \cap f_2^{-1}(B_2')$$

for all $B_1' \subseteq B_1$ and $B_2' \subseteq B_2$.

For addition... well, there might be something for your specific problem.

At the very least, it leads to a nice way to factor a program that enumerates the probabilities of each $x \in F$.