Let $p, q \in \mathbb R$ be positive reals for which $p + q = 1$. How to prove that for any two natural numbers $n, m$ the following inequality is true?

$(1 - p^n)^m + (1 - q^m)^n \ge 1$

I don't have a big knowledge about solving inequalities, so I tried to use cauchy-schwarz inequality, binomial theorem and some other baisc techniques, but it lead me nowhere. I've been thinking about it for a long time and now I'm completly stuck.

  • $\begingroup$ Say us what you have attempted. $\endgroup$ – Jean Marie Dec 8 '16 at 17:15
  • 1
    $\begingroup$ @J. Abraham I think must be solution with probability. $\endgroup$ – Michael Rozenberg Dec 8 '16 at 17:16
  • 1
    $\begingroup$ Would you please put the question "off hold"? I've completed it with all the information. $\endgroup$ – J. Abraham Dec 8 '16 at 19:59
  • 2
    $\begingroup$ This is another "missing context or other details" hold which I totally disagree with. To me, this is an interesting question and, as such, does not need any context. Let these questions go! $\endgroup$ – marty cohen Dec 8 '16 at 20:17
  • $\begingroup$ tactical dot..... $\endgroup$ – james black Feb 8 '18 at 14:19

Probability argument

Consider $m \times n$ grid (matrix if you like) with $m$ rows and $n$ columns, with either $0$ or $1$ numbers in its cells. Now let $p$ be probability that a cell contains $1$ and $q$ be probability that a cell contains $0$, so we have $p+q=1$.

Now what is the probability of (event $A$) each row having at least one $0$ in it? That is exactly the $P(A)=(1-p^n)^m$ ($p^n$ for a row made of $1s$, $1-p^n$ for row with at least one $0$, $(1-p^n)^m$ then for $m$ rows with this property). Similarly, probability of (event $B$) having in each column at least one $1$, is $(1-q^m)^n$. Thus we have

$$ (1-p^n)^m+(1-q^m)^n = P(A) + P(B) $$

Now notice that $P(A \cup B) = 1$. This is because we will always have all rows containing a $0$ or all columns containing a $1$. If there would be for example no row containing a $0$, it would mean there is a row full of $1$s, which means all columns contain a $1$ (at least the one from the row which is filled with them). You can argue similarly for the case when there would be no column containing a $1$...

Another way to see this is to notice

$$P(A \cup B) = 1- P(\overline{A \cup B}) = 1- P(\overline{A} \cap \overline{B}) = 1$$

since $\overline{A}$ (having a row consisting only of $1s$) and $\overline{B}$ (having a row consisting only of $0$s) are clearly mutually exclusive, you can't have both at the same time, therefore $P(\overline{A} \cap \overline{B}) = 0$.

Putting all these together gives $$(1-p^n)^m+(1-q^m)^n = P(A) + P(B) = P(A \cup B) + P(A \cap B) \geq P(A \cup B) = 1 $$

Alternative solution - double induction

The problem 19 found here states and proves more general inequality using double induction:

$$(1-x_1 \dots x_n)^m + (1-y_1^m) \dots (1-y_n^m) \geq 1,\ x_i, y_i \in [0,1],\ x_i + y_i = 1.$$

You can just plug in the $x_i = p$, $y_i=q$ and reproduce the proof.

  • $\begingroup$ Oh, I'm sorry I meant not $\le$ but $\ge$ $\endgroup$ – J. Abraham Dec 8 '16 at 18:20
  • $\begingroup$ Inequality 19 is completely different than mine $\endgroup$ – J. Abraham Dec 9 '16 at 11:42
  • $\begingroup$ @J.Abraham Have you tried the suggested substitution? $(1-p\dots p)^m = (1-p^n)^m$ and $(1-q^m)\dots (1-q^m) = (1-q^m)^n$. $\endgroup$ – Sil Dec 9 '16 at 11:50
  • $\begingroup$ I understand but look again at the inequality at this site. It doesn't look like the one you wrote (the part with y) $\endgroup$ – J. Abraham Dec 9 '16 at 11:53
  • $\begingroup$ Yea there was a mistake, but the referenced site still has it correct. Updated it here now. $\endgroup$ – Sil Dec 9 '16 at 11:53

Let there are two coins each with probability of head $p$. Let coin 1 has been tossed $n$ times independently and this whole scheme is repeated independently for $m$ times.

Similarly coin 2 is tossed $m$ times independently and this whole scheme is repeated independently for $n$ times and independently of coin 1.

$A$= at least one tail occurs in the string of 1st $n$-tosses, 2nd $n$ tosses, $\cdots$, $m^{th}$ $n$-tosses for coin 1

$B$= at least one head occurs in the string of 1st $m$-tosses, 2nd $m$ tosses, $\cdots$, $n^{th}$ $m$-tosses for coin 1

Notice the desired form is $P(A\cup B)\leq1$


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.