4
$\begingroup$

I am reading a paper on privacy that says we can model something as an arbitrary probabilistic function from $X^M \to X^M$. I'm trying to figure out what exactly that means. I saw another paper that defined a probabilistic function as a function $\mathcal{F}:X \times Y \to [0, 1]$ that satisfied the condition $$\forall x \in X: \sum_{y \in Y} \mathcal{F}(x, y) \leq 1.$$ But that definition doesn't seem to make sense if the function can take on values in the space $X^M$ where $X$ is an arbitrary set of objects. So what exactly are probabilistic functions?

Thanks so much!

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Can you provide a little bit more context or an example? Possibly it means a function on random variables? $\endgroup$ – Joe Bebel Mar 18 '15 at 3:28
  • $\begingroup$ I imagine it's either a probability distributions over functions from $X^M$ to $X^M$, or (more or less equivalently) a function $F:X^M \times \{0,1\}^r \to X^M$. The interpretation of the latter is that for each choice of $b \in \{0,1\}^r$, $F(\cdot, b)$ is function from $X^M$ to $X^M$, and when we pick $b$ uniformly at random, we get a probability distribution over such functions. But as Joe said, please give context, ideally a link to the paper. $\endgroup$ – Sasho Nikolov Mar 18 '15 at 4:46
  • $\begingroup$ Thanks @JoeBebel and @SashoNikolov! It's this paper, "Robust Deanonymization of Large Datasets": myspew.com/gallery/1/… I'm looking at page 4, and the arbitrary probabilistic function Aux. $\endgroup$ – Kristin Mar 18 '15 at 18:26
4
$\begingroup$

The definition you give is essentially the one you need. A probabilistic function from $X$ to $Y$ assigns to each $x\in X$ a subdistribution of elements of $Y$ (rather than a single $y\in Y$). Such a subdistribution is a function $\delta:Y\to[0,1]$ such that

$\sum_{y\in Y}\delta(y)\leq 1$.

In other words, a probabilistic function $X\to Y$ is a function $f:X\to(Y\to [0,1])$, i.e. $f:X\times Y\to [0,1]$, such that for all $x\in X,$

$\sum_{y\in Y}f(x,y)\leq 1$.

In your case, both domain and codomain are $X^M$; a probabilistic function from $X^M$ to $X^M$ then is a function $f:X^M\times X^M\to [0,1]$ such that for all $x\in X^M$,

$\sum_{y\in X^M} f(x,y)\leq 1$.

The intended meaning of this is that the function still returns a single point when given some input, but this point is chosen randomly according to the relevant distribution. For example, if $M=2$, and $f(1,2) = \{(1,1)\mapsto 0.5,(2,2)\mapsto 0.5\}$ (all others being $0$), then when you call $f(1,2)$, you will get $(1,1)$ or $(2,2)$ each with probability $0.5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Cool, that is interesting. I thought it would output a point in $X^M$, but I guess it actually outputs a function from $X^M$ to $[0, 1]$. Thanks for the clarification! $\endgroup$ – Kristin Mar 18 '15 at 18:24
  • $\begingroup$ Actually strictly speaking it will output a point, but randomly chosen according to the distribution associated with $x$. I'll update the answer. $\endgroup$ – Klaus Draeger Mar 18 '15 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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