Skip to main content
added 1482 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*}\begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \tag{-2}\label{-2} \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*}\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in[k]}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \tag{-1}\label{-1} \end{equation*} SoThe first equality in \eqref{-1} follows by the conditioning on $(a_1,c_1),\dots,(a_k,c_k)$ and using the fact that the random pairs $(a_1,c_1),\dots,(a_k,c_k),(a_{k+1},c_{k+1}),\dots,(a_n,c_n)$ are iid. Details on the second equality in \eqref{-1} are given at the end of this answer.

By \eqref{-2}, \eqref{-1}, and the Fubini–Tonelli theorem, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \tag{0}\label{0} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.


Now there also is a combinatorial way to get \eqref{2} (but not \eqref{0} or \eqref{1}).


Details on the second equality in \eqref{-1}: Letting $f(t):=P(a_n<0,c_n\ge t)^{n-k}$ and $\mu(dt):=P(a_1>0,c_1\in dt)$, we have \begin{equation*} \begin{aligned} &\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in[k]}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_{\R^k}f(\max_{i\in[k]}t_i)\prod_{i\in[k]}\mu(dt_i) \\ &=k\int_{\R^k}f(t_1)1(t_1\ge\max_{i\in[k]\setminus\{1\}}t_i)\prod_{i\in[k]}\mu(dt_i) \\ &=k\int_\R \mu(dt_1)f(t_1) \int_{\R^{k-1}}1(t_1\ge\max_{i\in[k]\setminus\{1\}}t_i) \prod_{i\in[k]\setminus\{1\}}\mu(dt_i) \\ &=k\int_\R \mu(dt_1)f(t_1) \int_{\R^{k-1}} \prod_{i\in[k]\setminus\{1\}}[1(t_1\ge t_i)\mu(dt_i)] \\ &=k\int_\R \mu(dt_1)f(t_1) \mu((-\infty,t_1])^{k-1} \\ &=\int_\R f(t)k \mu((-\infty,t])^{k-1}\mu(dt) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt); \end{aligned} \tag{3}\label{3} \end{equation*} the second equality in \eqref{3} follows because (i) the $t_i$'s are interchangeable and (ii) the measure $\mu$ is non-atomic (since the distribution of $c_1$ is non-atomic).

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \tag{0}\label{0} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.


Now there also is a combinatorial way to get \eqref{2} (but not \eqref{0} or \eqref{1}).

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \tag{-2}\label{-2} \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in[k]}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \tag{-1}\label{-1} \end{equation*} The first equality in \eqref{-1} follows by the conditioning on $(a_1,c_1),\dots,(a_k,c_k)$ and using the fact that the random pairs $(a_1,c_1),\dots,(a_k,c_k),(a_{k+1},c_{k+1}),\dots,(a_n,c_n)$ are iid. Details on the second equality in \eqref{-1} are given at the end of this answer.

By \eqref{-2}, \eqref{-1}, and the Fubini–Tonelli theorem, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \tag{0}\label{0} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.


Now there also is a combinatorial way to get \eqref{2} (but not \eqref{0} or \eqref{1}).


Details on the second equality in \eqref{-1}: Letting $f(t):=P(a_n<0,c_n\ge t)^{n-k}$ and $\mu(dt):=P(a_1>0,c_1\in dt)$, we have \begin{equation*} \begin{aligned} &\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in[k]}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_{\R^k}f(\max_{i\in[k]}t_i)\prod_{i\in[k]}\mu(dt_i) \\ &=k\int_{\R^k}f(t_1)1(t_1\ge\max_{i\in[k]\setminus\{1\}}t_i)\prod_{i\in[k]}\mu(dt_i) \\ &=k\int_\R \mu(dt_1)f(t_1) \int_{\R^{k-1}}1(t_1\ge\max_{i\in[k]\setminus\{1\}}t_i) \prod_{i\in[k]\setminus\{1\}}\mu(dt_i) \\ &=k\int_\R \mu(dt_1)f(t_1) \int_{\R^{k-1}} \prod_{i\in[k]\setminus\{1\}}[1(t_1\ge t_i)\mu(dt_i)] \\ &=k\int_\R \mu(dt_1)f(t_1) \mu((-\infty,t_1])^{k-1} \\ &=\int_\R f(t)k \mu((-\infty,t])^{k-1}\mu(dt) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt); \end{aligned} \tag{3}\label{3} \end{equation*} the second equality in \eqref{3} follows because (i) the $t_i$'s are interchangeable and (ii) the measure $\mu$ is non-atomic (since the distribution of $c_1$ is non-atomic).

added 171 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \end{equation*}\begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \tag{0}\label{0} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.


Now there also is a combinatorial way to get \eqref{2} (but not \eqref{0} or \eqref{1}).

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \tag{0}\label{0} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.


Now there also is a combinatorial way to get \eqref{2} (but not \eqref{0} or \eqref{1}).

`{gather}` and `\eqref`
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dots,n\}$$[n]:=\{1,\dotsc,n\}$, \begin{equation*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \end{equation*} \begin{equation*} p_k:=p_{[k]}. \end{equation*}\begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1} \end{equation*}\begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2} \end{equation*}\begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, (\eqref{1)} turns into an equality.


The expression for $p$ in (\eqref{2)} agrees with simulation results for $n=1,\dots,10$$n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dots,n\}$, \begin{equation*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \end{equation*} \begin{equation*} p_k:=p_{[k]}. \end{equation*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2} \end{equation*} In this case, (1) turns into an equality.


The expression for $p$ in (2) agrees with simulation results for $n=1,\dots,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.

$\newcommand\R{\mathbb R}$Assume that the $a_i$'s and $b_i$'s are iid random variables with a common non-atomic distribution. Let $c_i:=b_i/a_i$.

Then the probability in question is \begin{equation*} p:=\sum_{J\subseteq[n]}p_J=\sum_{k=0}^n\binom nk p_k, \end{equation*} where $[n]:=\{1,\dotsc,n\}$, \begin{gather*} p_J:=P(a_i>0\ \forall i\in J, a_j<0\ \forall j\notin J,\ \sup_{i\in J}c_i\le\inf_{j\notin J}c_j), \\ p_k:=p_{[k]}. \end{gather*} In particular, \begin{equation*} p_0=P(a_j<0\ \forall j\in[n])=P(a_1<0)^n, \end{equation*} since $\sup_{i\in\emptyset}c_i=-\infty$. On the other hand, for $k\in[n]$,
\begin{equation*} \begin{aligned} &p_k=\int_{\R^k}P(a_n<0,c_n\ge\max_{i\in J}t_i)^{n-k}\prod_{i\in[k]}P(a_1>0,c_1\in dt_i) \\ &=\int_\R P(a_n<0,c_n\ge t)^{n-k}\,kP(a_1>0,c_1\le t)^{k-1} P(a_1>0,c_1\in dt). \end{aligned} \end{equation*} So, \begin{equation*} \begin{aligned} p &=p_0+\int_\R P(a_1>0,c_1\in dt) \\ &\qquad\qquad\times\sum_{k=1}^n\binom nk kP(a_1>0,c_1\le t)^{k-1} P(a_n<0,c_n\ge t)^{n-k} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\, \\ &\qquad\qquad\qquad\qquad\times n[P(a_1>0,c_1\le t)+P(a_n<0,c_n\ge t)]^{n-1} \\ &=P(a_1<0)^n+ \int_\R P(a_1>0,c_1\in dt)\,nP(b_1\le ta_1)^{n-1}. \end{aligned} \end{equation*}

So, a simple upper bound on $p$ is given by \begin{equation*} p\le P(a_1<0)^n+P(a_1>0)\,nq^{n-1}, \tag{1}\label{1} \end{equation*} where \begin{equation*} q:=\sup_{t\in\R}P(b_1\le ta_1). \end{equation*}

In the case when the common non-atomic distribution of the $a_i$'s and $b_i$'s is symmetric about $0$, we have $P(b_1\le ta_1)=1/2$ for all real $t$, and hence the expression for $p$ simplifies: \begin{equation*} p=\frac{n+1}{2^n}. \tag{2}\label{2} \end{equation*} In this case, \eqref{1} turns into an equality.


The expression for $p$ in \eqref{2} agrees with simulation results for $n=1,\dotsc,10$ when the common distribution of the $a_i$'s and $b_i$'s is standard normal.

added 47 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
added 293 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
added 252 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
added 1 character in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading