Let $X$ be a set of cardinality $n$ and let $R$ be the set of all relations over $X$. Consider the probability space $(R,P)$ with uniform distribution, that is, $P[\{R_1\}]] = P[\{R_2\}]$ for all $ R_1,R_2 \in R$. Define the relation ”equiprobable” on the set of all events of $(R, P)$ as follows: Events $A$ and $B$ are equiprobable iff $P[A] = P[B]$.

a. Prove that ”equiprobable” is an equivalence relation.

b. How many equivalence classes does this relation define?

Here is my attempt at a, can anyone help me check?

  • Reflexive: $R_1 ,\in R$, then $P[\{R_1\}] = P[\{R_1\}]$, which is equiprobable $\Rightarrow$ $R_1\,R\, R_1$ $\Rightarrow$ reflexive

  • Transitive: $R_1,R_2,R_3 \in R$, suppose $P[\{R_1\}] = P[\{R_2\}\,] \& \,P[\{R_2\}] = P[\{R_3\}] \,\Rightarrow\, P[\{R_1\}] = P[\{R_3\}] \,\Rightarrow\, R_1 \,R \,R_3 \,\Rightarrow $transitive

  • Symmetric: $R_1, R_2 \in R$, $ P[\{R_1\}] = P[\{R_2\}]$ $\Rightarrow$ $P[\{R_2\}] = P[\{R_1\}]$ $\Rightarrow$ $R_2\, R\, R_1$ $\Rightarrow$ symmetric

I don't know how to solve b, and my teacher gave me a hint but I'm still a lot confused about equivalence classes

If $R_1$ and $R_2$ are equiprobable, is there any relation between $|R_1|$ and $|R_2|$?

This is just my guess: $|R_1| = |R_2|$ because they are equivalence relations, so the size of them are equal? Please help me understand this

  • $\begingroup$ How many elements does $R$ have? So how many values can $P$ take? $\endgroup$ – user10354138 Jun 3 '19 at 5:55
  • $\begingroup$ @user10354138 erm I'm not sure.. the question doesn't state, does it? Can you give me some more hints? $\endgroup$ – amV Jun 3 '19 at 6:03
  • $\begingroup$ Please use Mathjax when writing math :) $\endgroup$ – Riccardo Sven Risuleo Jun 3 '19 at 6:04
  • $\begingroup$ @RiccardoSvenRisuleo I will, thanks $\endgroup$ – amV Jun 3 '19 at 6:05
  • $\begingroup$ The equivalence class of an event $A\subseteq R$ is the set of all events $B\subseteq R$ which are equiprobable to $A$. Under the uniform distribution, the only condition to be satisfied is that $A$ and $B$ contain the same number of outcomes. You might as well label each equivalence class by the size of its elements! $\endgroup$ – M. Nestor Jun 3 '19 at 6:17

In general if $f:A\to B$ is some function then a relation $S$ over $A$ that is prescribed by: $$xSy\iff f(x)=f(y)$$can "immediately" be recognized as an equivalence relation on base of the observations that $f(x)=f(x)$ for every $x\in A$, $f(x)=f(y)\implies f(y)=f(x)$ for all $x,y\in A$ and $f(x)=f(y)\wedge f(y)=f(z)\implies f(x)=f(z)$ for all $x,y,z\in A$.

You did that in your attempt with function $P$.

Further the equivalence class represent by $a\in A$ is the set $\{x\in A\mid f(x)=f(a)\}$.

The cardinality of the set of equivalence classes equals the cardinality of the image of the function, i.e. the set $\{f(x)\mid x\in A\}$. This because there is a one-to-one relation between the image and the set of equivalence classes: every element $y$ of this image corresponds with equivalence class $\{x\mid f(x)=y\}$.

Application in your situation:

The set of outcomes is $R=\wp\left(X\times X\right)$. From the fact that $X$ has $n$ elements we conclude that $X\times X$ has $n^{2}$ elements, and secondly that $R=\wp\left(X\times X\right)$ has $2^{n^{2}}$ elements.

Further $P$ is an additive function $\wp\left(R\right)\to\mathbb{R}$ determined by $P\left(\left\{ r\right\} \right)=2^{-n^{2}}$ for every $r\in R$.

That implies that for event $A\subseteq\wp\left(R\right)$ we have $P\left(A\right)=\sum_{r\in A}P\left(\left\{ r\right\} \right)=\left|A\right|2^{-n^{2}}$ where $\left|A\right|$ can take the values $\left\{ 0,1,2,\dots,2^{n^{2}}\right\} $.

We conclude that the cardinality of the image of function $P$ is: $$2^{n^{2}}+1$$ and as shown above this is also the number of equivalence classes.

  • $\begingroup$ can you explain a little bit about the set of the image of P? why is it {0, 1/n^2, ... (n^2-1)/n^2, 1}? Sorry I'm not quite good at this $\endgroup$ – amV Jun 3 '19 at 7:00
  • $\begingroup$ I have repaired my answer. $\endgroup$ – drhab Jun 3 '19 at 8:25
  • $\begingroup$ Where does the "+ 1" come from for the cardinality of the relation? I'm a little unclear on that part $\endgroup$ – quantumferret Dec 15 '20 at 17:11
  • $\begingroup$ @quantumferret Do you agree that set $\{0,1,2,\dots m\}$ has $m+1$ elements? Here $m=2^{n^2}$. $\endgroup$ – drhab Dec 15 '20 at 18:37
  • $\begingroup$ @drhab would it be incorrect for me to think of it in terms of a probability space (Ω, F, P)? Ω would be |X x X| = n^2 and F = 2^(n^2), so F = m? $\endgroup$ – quantumferret Dec 16 '20 at 13:06

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.