<p>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</p>

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

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

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

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

<p>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</p>

<p>$$(g \circ f)^{-1}\ =\ f^{-1} \circ g^{-1}$$</p>

<p>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</p>

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

<p>for all $B_1' \subseteq B_1$ and $B_2' \subseteq B_2$.</p>

<p>For addition... well, there might be something for your specific problem.</p>

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

CC BY-SA 3.0
2014-02-05T02:57:52.653Z
Thanks for your response and explanation. It makes my question more clear. By the way, this is a reformulation of the question, in a more clear mathematical way than mine. I wonder how can we find this distribution, either using a computer program or a bunch of analytical chores ...
Ali Shakiba
CC BY-SA 3.0
2014-02-03T19:57:08.857Z
2014-02-03T19:57:08.857Z
Neil Toronto
<p>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$.</p>

<p>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.</p>

<p>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.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2014-02-02T20:53:34.097Z
Hmm, if you could prove "hardness", wouldn't you have a one-way function? And by distribution, of the relation, do you mean the distribution over outputs when your inputs $n$ and $m$ are chosen uniformly at random from $F$?
usul
CC BY-SA 3.0
2014-02-03T18:20:28.223Z
Yes, that's all I want! I want to see its distribution is close to uniform or not when input elements are uniformly chosen.
Ali Shakiba
<cc.complexity-theory>
How can I find the distribution of a recursive relation with two parameters?
Ali Shakiba
# How can I find the distribution of a recursive relation with two parameters?

(Asked by: username_0 on 2014-01-31)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Hmm, if you could prove "hardness", wouldn't you have a one-way function? And by distribution, of the relation, do you mean the distribution over outputs when your inputs $n$ and $m$ are chosen uniformly at random from $F$?  
> **username_0**: Yes, that's all I want! I want to see its distribution is close to uniform or not when input elements are uniformly chosen.  

---

## 1 answers

### Answer by username_2 on 2014-02-03. Score: 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$.

> **Comments:**
> **username_0**: Thanks for your response and explanation. It makes my question more clear. By the way, this is a reformulation of the question, in a more clear mathematical way than mine. I wonder how can we find this distribution, either using a computer program or a bunch of analytical chores ...  

---

