# Which monomials in $p$ and $q$ can be a probability in a finite coin experiment?

The question generate event with $6.75\space p^2q$, $20\space p^3q^2$, $3.9\space pq$? prompted me to think more generally about which expressions of this form can be a probability in a finite coin experiment. Since the answer turns out to be rather nice, I thought I'd post it here as an answer to the general question.

We have a coin that shows heads with probability $p$ and tails with probability $q:=1-p$, and the question is whether for given $\mu\in\mathbb R^+$ and $i,j\in\mathbb N$ (not both zero) there is an event in an experiment with a fixed finite number of tosses of the coin whose probability is $\mu p^iq^j$ for all $p\in[0,1]$.

The monomial $\mu p^iq^j$ is a probability in a finite coin experiment if and only if $\mu$ is an integer and $\mu p^iq^j\lt1$ for all $p\in[0,1]$.

First, $\mu$ needs to be an integer: The probability of any event in an experiment with a fixed finite number of tosses is a polynomial in $p$ with integer coefficients; and $\mu p^iq^j=\mu p^i(1-p)^j$ is a polynomial in $p$ with coefficient $\mu$ for $p^i$, so $\mu$ must be integer for the two to be equal.

The rest of the “only if” direction is also readily proved. Since $\mu p^iq^j$ is a probability for all $p$, it must be $\le1$ for all $p$. If there were $p$ such that $\mu p^iq^j=1$, the event would have to include all elementary events, which implies $\mu p^iq^j=1$ for all $p$, which only occurs in the trivial case $i=j=0$ that was excluded in the question.

Now, to prove the “if” direction, consider an experiment with $i+j+l$ tosses. If we can select $\mu\binom lk$ elementary events with $i+k$ heads and $j+l-k$ tails for all $k=0,\ldots,l$, then the probability of the event composed of all these elementary events is

$$\sum_{k=0}^l\mu\binom lkp^{i+k}q^{j+l-k}=\mu p^iq^j(p+q)^l=\mu p^iq^j\;.$$

There are $\binom{i+j+l}{i+k}$ such elementary events, so we can choose $\mu\binom lk$ of them if

$$\mu\binom lk\le\binom{i+j+l}{i+k}$$

for all $k$. If we cancel factors in the three pairs of corresponding factorials, this becomes

$$\mu(k+i)\cdots(k+1)(l-k+j)\cdots(l-k+1)\le(l+i+j)\cdots(l+1)\;,$$

and then dividing through by $l^{i+j}$ and denoting $\frac kl\in[0,1]$ by $\alpha$ leads to

$$\mu\left(\alpha+\frac il\right)\cdots\left(\alpha+\frac1l\right)\left(1-\alpha+\frac jl\right)\cdots\left(1-\alpha+\frac 1l\right)\le\left(1+\frac{i+j}l\right)\cdots\left(1+\frac1l\right)$$

and thus to

$$\mu\alpha^i(1-\alpha)^j+O\left(\frac{(i+j)^2}l\right)\le1\;.$$

Thus, we can satisfy this inequality for sufficiently large $l$ if $\mu\alpha^i(1-\alpha)^j\lt1$ for all $\alpha\in[0,1]$.

• but, if you take an event from a subset of the (finite) probability space, can't $\mu$ be rational ? and even greater than one , keeping safe that $\mu p^i q^j <1$ ? – G Cab Jul 16 '18 at 21:49
• @GCab: $\mu$ can certainly be greater than $1$; in the original question that I linked to, it was $20$. But I don't understand your question about $\mu$ being rational. Is there an error in my proof that it can't? Perhaps I don't understand what you mean by "taking an event from a subset". – joriki Jul 16 '18 at 21:54
• My doubt was about introducing order. But I got your point now, in a different way: let's say that each of all the possible binary strings of length $n$ has a probability that corresponds to the product of $(p_1p_2\cdots p_m,\;q_1q_2\cdots q_{n-m})$ in whichever order. So $p_iq_j$ is the .."granularity" of any event you can define in them, and so $\mu$ must be an integer. (+1) – G Cab Jul 16 '18 at 23:50
• @GCab: I don't think the argument works in quite that way. As the proof here and already the example given in the linked question illustrate, you can make use of $p+q=1$ to combine monomials into lower ones; and you can also use it to artificially increase the degree of a polynomial in $p$ and $q$; so I don't see how working with $p$ and $q$ allows for such a "granularity" argument; I think you really do need to switch to a representation in terms of $p$ alone, as I did in the proof, in order to make that argument go through. – joriki Jul 17 '18 at 3:56