Universal alignment probability revisited (Q5894853)

Let \(\Theta\) be the search space for optimization, \(N\) the set of uniform samples elements of \(\Theta\), \(GS_\Theta\) a ``good enough'' subset of \(\Theta\), \(GS_N\) a ``good enough'' subset of \(N\), and \(SS\) a selected subset of \(N\). What is the relation between the two alignment probabilities \[ P_A= \{|SS\cap GS_N|> k\}\quad\text{and}\quad P^*_A= \{|SS\cap GS_\Theta|> k^*\}? \] Let \(GS^r_\Theta\) be a reduced good enough subset of \(N\). With a sufficiently stringent definition of what is ``good enough'' in \(N\), it can be guaranteed with high probability that \(GS^r_N\subseteq GS_\Theta\). Consequently, using the tabulated value of \(P_A\), a lower bound for \(P^*_A\) can be given, thus quantifying hitherto merely empirical evidence for the successful use of the ordinal optimization approach.