Wikipedia:Reference desk/Archives/Mathematics/2018 March 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 26

Probability of events expressed in a formal language

Suppose $e$ represents everything you know, expressed in formal or natural language. Suppose you wish to query $P(q|e)$ for some $q$, which is again expressed in a language. How do you calculate or approximate $P(q|e)$?

If you know the full joint probability distribution, then by definition $P(q|e)={\frac {P(q\land e)}{P(e)}}$. But in general, you may not know the joint probability distribution.

Let $H$ be the class of all joint probability distributions. Then $P(q|e)=\sum _{h\in H}\left({\frac {P(q\land e|h)}{P(e|h)}}P(h)\right)$ where $P(h)$ is a weight that quantifies the simplicity of the distribution, as per Occam's razor...doesn't it?

And I guess you could approximate it by picking the $h$ which gives the largest value for ${\frac {P(q\land e|h)}{P(e|h)}}P(h)$, call it $h_{M}$, and $P(q|e)\approx {\frac {P(q\land e|h_{M})}{P(e|h_{M})}}$. But $h_{M}$ could depend on $q$, which doesn't make much sense to me; surely the optimal $h_{M}$ would be independent of what question you're asking.--49.184.160.10 (talk) 12:03, 26 March 2018 (UTC)

Probability of all distinct choices in drawing with replacement

Let $A=\{a_{1},a_{2},\ldots ,a_{N}\}$ be a set of $N$ objects. $r$ drawings, with replacement, are made from the $N$ objects according to the same probability distribution, where the $p_{i}$ = prob. that $a_{i}$ is chosen in any given drawing. $\sum _{i=1}^{N}p_{i}=1$, but all the $p_{i}$'s are not constrained to have the same value. What is the probability that all objects chosen in $r$ drawings are distinct, where $r\leq N$? Thanks. --134.242.92.97 (talk) 19:16, 26 March 2018 (UTC)

By usual elementary counting arguments, it is $r!\cdot e_{r}(p_{1},\ldots ,p_{N})$, where $e_{r}$ is the elementary symmetric polynomial. --JBL (talk) 11:47, 27 March 2018 (UTC)

That's a "brute force" solution. Is there an expression for the probability that's easier to evaluate? --134.242.92.97 (talk) 17:32, 27 March 2018 (UTC)

What counts as "easier to evaluate"? If there was a reduction into "something simple", the elementary symmetric polynomial could be computed that way (at least for positive arguments whose sum is 1, which is still "a lot of numbers").

There might well be a tricky factorization Horner-style using Elementary symmetric polynomial#Properties, but I could only get it to work for an approximate solution.

Define $f(\lambda ):=\prod _{j=1}^{n}(\lambda -p_{j})$. This is equal to $\lambda ^{n}-e_{1}(p_{1},\ldots ,p_{n})\lambda ^{n-1}+e_{2}(p_{1},\ldots ,p_{n})\lambda ^{n-2}+\cdots +(-1)^{n}e_{n}(p_{1},\ldots ,p_{n})$ (cf. link above) so in particular, the (n-r)-th derivative of f at 0 will give us the value we want: $f^{(n-r)}(0):=(-1)^{r}(n-r)!e_{r}(p_{1},...p_{n})$ (if you actually want to use it, check the math carefully, an off-by-one error is likely). Now for an approximate value, each evaluation of f is O(n) multiplications and you need (n-r) of those to compute the (n-r)-th derivate at a given point so the total complexity is O(n^2) (rather than r choose n); but for an exact value, I do not see how you avoid the (r choose N). Tigraan^{Click here to contact me} 12:29, 28 March 2018 (UTC)

It's pretty clear that e_r(p₁, ... p_N) = e_r(p₁, ... p_N-1)+p_Ne_r-1(p₁, ... p_N-1); basically it's just multiplying out the product one factor at a time. This gives a recursive way of computing all e_r(p₁, ... p_N) for r from 1 to N in order N². There are fast methods of multiplying polynomials which could probably get you to below order N². In any case, the answer is what's given above, no matter how hard to compute it is. --RDBury (talk) 02:17, 30 March 2018 (UTC)