2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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$? $\endgroup$
    – usul
    Feb 2, 2014 at 20:53
  • $\begingroup$ Yes, that's all I want! I want to see its distribution is close to uniform or not when input elements are uniformly chosen. $\endgroup$ Feb 3, 2014 at 18:20

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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 ... $\endgroup$ Feb 5, 2014 at 2:57

Your Answer

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

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