Difference between revisions of "With high probability"

From Algorithmist
Jump to: navigation, search
(O as lower bound makes no sense. Omega is needed here.)
(Example: latex)
 
Line 4: Line 4:
 
Since we can choose <math>\alpha</math>, we can make the probability arbitrarily low, at a cost of time and/or space.
 
Since we can choose <math>\alpha</math>, we can make the probability arbitrarily low, at a cost of time and/or space.
 
== Example ==
 
== Example ==
With high probability, a set of N random numbers will contain at least <math>\Omega(N)</math> evens.  
+
With high probability, a set of N random numbers will contain at least <math>\Omega</math>(N) evens.  
  
 
What it means is: For any <math>\alpha</math>, there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability <math>1 - \frac{c_\alpha}{n^\alpha}</math>, where <math>c_\alpha</math> depends only on <math>\alpha</math>.  
 
What it means is: For any <math>\alpha</math>, there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability <math>1 - \frac{c_\alpha}{n^\alpha}</math>, where <math>c_\alpha</math> depends only on <math>\alpha</math>.  
 
[[Category:Randomized Algorithms]]
 
[[Category:Randomized Algorithms]]

Latest revision as of 07:51, 3 April 2014

Definition[edit]

An event occurs with high probability if, for any \alpha \geq 1, the event occurs with probability at least 1-{\frac  {c_{\alpha }}{n^{\alpha }}}, where c_{\alpha } depends only on \alpha .

Since we can choose \alpha , we can make the probability arbitrarily low, at a cost of time and/or space.

Example[edit]

With high probability, a set of N random numbers will contain at least \Omega (N) evens.

What it means is: For any \alpha , there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability 1-{\frac  {c_{\alpha }}{n^{\alpha }}}, where c_{\alpha } depends only on \alpha .