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

<p>$\sum_{y\in Y}\delta(y)\leq 1$.</p>

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

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

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

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

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

CC BY-SA 3.0
2015-03-18T18:24:32.707Z
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!
Kristin
CC BY-SA 3.0
2015-03-18T19:14:09.563Z
Actually strictly speaking it will output a point, but randomly chosen according to the distribution associated with $x$. I'll update the answer.
Klaus Draeger
CC BY-SA 3.0
2015-03-18T12:19:17.077Z
2015-03-18T19:17:53.747Z
2015-03-18T19:17:53.747Z
Klaus Draeger
<p>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?</p>

<p>Thanks so much!</p>

CC BY-SA 3.0
2015-03-18T03:28:31.050Z
Can you provide a little bit more context or an example? Possibly it means a function on random variables?
Joe Bebel
CC BY-SA 3.0
2015-03-18T04:46:34.090Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-03-18T18:26:39.563Z
Thanks @JoeBebel and @SashoNikolov!  It's this paper, "Robust Deanonymization of Large Datasets": http://myspew.com/gallery/1/Robust%20De-anonymization%20of%20Large%20Datasets.pdf I'm looking at page 4, and the arbitrary probabilistic function Aux.
Kristin
<privacy>
What is a probabilistic function and where can I learn more about them?
Kristin
# What is a probabilistic function and where can I learn more about them?

(Asked by: username_0 on 2015-03-18)

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!

**Tags:** privacy

> **Comments:**
> **username_1**: Can you provide a little bit more context or an example? Possibly it means a function on random variables?  
> **username_2**: 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.  
> **username_0**: Thanks @JoeBebel and @SashoNikolov!  It's this paper, "Robust Deanonymization of Large Datasets": http://myspew.com/gallery/1/Robust%20De-anonymization%20of%20Large%20Datasets.pdf I'm looking at page 4, and the arbitrary probabilistic function Aux.  

---

## 1 answers

### Answer by username_3 on 2015-03-18. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: 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!  
> **username_3**: Actually strictly speaking it will output a point, but randomly chosen according to the distribution associated with $x$. I'll update the answer.  

---

