1
$\begingroup$

Let $P$ be a probability distribution over a finite Boolean algebra $\mathfrak{B}$, and fix a parameter $t_{P} \in (\frac{2}{3}, 1)$. Define the `revision function of $P$', $R_{P}: \mathfrak{B}\setminus\{\bot\} \rightarrow \mathbb{P}(\mathfrak{B})$ as follows, (assuming that $P$ assigns positive probability to all events other than the null event $\bot$)

$R_{P}(X) = \{Y \in \mathfrak{B}|P(Y|X) \geq t\}$

In words, the revision function of $P$ takes an event $X$ in $\mathfrak{B}$ and returns the set of all events whose conditional probability given $X$ (according to $P$) is at least $t_{p}$.

I want to find general method for constructing, for any given $P$ and any $t_{P} \in (\frac{2}{3}, 1)$, another probability function $P^{*}$ with a corresponding parameter $t_{P^{*}} \in (\frac{2}{3}, 1)$ such that $R_{P^{*}} = R_{P}$. In other words, I want a method that constructs, for any probability function and fixed parameter in the specified range, another function that (for some choice of parameter in the specified range) gives rise to the same revision function as the original function.

Importantly, the method should not take $P$ itself (or $t_{P}$) as an input -- it should be a function of $R_{P}$ alone. In essence, I want a function that takes a revision function obtained from a probability distribution/parameter, and constructs another probability distribution/parameter pair that also corresponds to the same revision function, and does so without `looking at' the function/parameter that the revision function initially came from.

$\endgroup$
  • $\begingroup$ Typo Error? What is $t$? $\endgroup$ – Dieter Kadelka Jan 13 at 18:55
  • $\begingroup$ sorry, yes, edited now $\endgroup$ – King Kong Jan 13 at 18:56
1
+200
$\begingroup$

(Too long for a comment.)

Let $A_1, \ldots, A_n$ be the atoms of $\mathfrak B$, and write $P^*(A_i) = p_i$. Then the conditions on $p_i$ and $t^* = t_{P^*}$ are:

  • $p_i \geqslant 0$ and $\sum_{i = 1}^n p_i = 1$;
  • $\tfrac{2}{3} < t^* < 1$;
  • for every $X, Y \in \mathfrak B$ such that $X \ne \varnothing$ and $Y \in R_P(X)$ we have $$\sum_{i = 1}^n p_i (\mathbb{1}_{A_i \subset X \cap Y} - t^* \mathbb{1}_{A_i \subset X}) \geqslant 0;$$
  • for every $X, Y \in \mathfrak B$ such that $X \ne \varnothing$ and $Y \in \mathfrak B \setminus R_P(X)$ we have $$\sum_{i = 1}^n p_i (\mathbb{1}_{A_i \subset X \cap Y} - t^* \mathbb{1}_{A_i \subset X}) < 0.$$

For a fixed $t^*$, this is a linear programming problem (with no optimization goal, but it does not matter), so it should be solvable using standard methods. (I do not expect this is an optimal solution, though.)

With $t^*$ unknown, the problem is no longer linear. I guess there is a smart way to convert it to another linear optimization problem, but that is not my area of expertise.


I am not even sure if I understood the problem correctly, and so the above idea can be plainly wrong. However, if it is correct, one may consider adding a linear-programming tag to the question to attract attention of specialists in the area.

$\endgroup$
  • $\begingroup$ Does the probability of the atoms have to sum to 1? $\endgroup$ – Bill Bradley Jan 16 at 4:55
  • $\begingroup$ I think so — if $P^*$ is supposed to be a probability measure. $\endgroup$ – Mateusz Kwaśnicki Jan 16 at 8:29
  • $\begingroup$ Thanks! I've added a linear programming tag. Can I ask what the 𝟙𝐴𝑖⊂𝑋∩𝑌 notation denotes? $\endgroup$ – King Kong Jan 16 at 17:36
  • 1
    $\begingroup$ @KingKong: That is just an abuse of the notation for an indicator function: $\mathbb 1_{A_i \subset X \cap Y}$ is equal to one if $A_i \subset X \cap Y$ and zero otherwise. Perhaps I should have used the Iverson bracket for that and simply write $[A_i \subset X \cap Y]$. $\endgroup$ – Mateusz Kwaśnicki Jan 16 at 17:42
  • 1
    $\begingroup$ @KingKong: This is correct. One thing that I am afraid is that one can craft $P$ and $t_P$ in such a way that we necessarily have $t_{P^*} = t_P$. In this case the kind of "iterative" method might fail to finish in finite time. Also, this seems to be extremely inefficient. Finally, people know a lot about extensions of the linear programming problem, I suspect a more efficient approach is feasible (in case you care about time complexity of the solution). $\endgroup$ – Mateusz Kwaśnicki Jan 18 at 20: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.