Suppose $a_i$'s and $b_i$'s ($1\leq i\leq n$) are i.i.d Gaussian random variables. What's the probability that a $\lambda$ exists such that $\lambda a_i \geq b_i, ~\forall i$?
Actually, an upper bound (as a function of $n$) on the probability is what I'm looking for. And if a bound can be found that's independent of the underlying distribution (just like Hoeffding's inequality, maybe assuming boundedness on the random variables), that would be great.
Thanks.
$\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).
