|
McDiarmid's Inequality
In probability theory and theoretical computer science, McDiarmid's inequality is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a ''bounded differences'' property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function. =Statement= A function f: \mathcal_1 \times \mathcal_2 \times \cdots \times \mathcal_n \rightarrow \mathbb satisfies the ''bounded differences property'' if substituting the value of the ith coordinate x_i changes the value of f by at most c_i. More formally, if there are constants c_1, c_2, \dots, c_n such that for all i\in /math>, and all x_1\in \mathcal_1,\,x_2\in \mathcal_2,\, \ldots,\, x_n \in \mathcal_n, : \sup_ \left, f(x_1, \dots, x_, x_i, x_, \ldots, x_n) - f(x ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Azuma's Inequality
In probability theory, the Azuma–Hoeffding inequality (named after Kazuoki Azuma and Wassily Hoeffding) gives a concentration inequality, concentration result for the values of martingale (probability theory), martingales that have bounded differences. Suppose \ is a Martingale (probability theory), martingale (or Martingale_(probability_theory)#Submartingales.2C_supermartingales.2C_and_relationship_to_harmonic_functions, super-martingale) and :, X_k - X_, \leq c_k, \, almost surely. Then for all positive integers ''N'' and all positive real number, reals ''\epsilon'', :\text(X_N - X_0 \geq \epsilon) \leq \exp\left ( \right). And symmetrically (when ''X''''k'' is a sub-martingale): :\text(X_N - X_0 \leq -\epsilon) \leq \exp\left ( \right). If ''X'' is a martingale, using both inequalities above and applying the union bound allows one to obtain a two-sided bound: :\text(, X_N - X_0, \geq \epsilon) \leq 2\exp\left ( \right). Proof The proof shares similar idea of the pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Azuma's Inequality
In probability theory, the Azuma–Hoeffding inequality (named after Kazuoki Azuma and Wassily Hoeffding) gives a concentration inequality, concentration result for the values of martingale (probability theory), martingales that have bounded differences. Suppose \ is a Martingale (probability theory), martingale (or Martingale_(probability_theory)#Submartingales.2C_supermartingales.2C_and_relationship_to_harmonic_functions, super-martingale) and :, X_k - X_, \leq c_k, \, almost surely. Then for all positive integers ''N'' and all positive real number, reals ''\epsilon'', :\text(X_N - X_0 \geq \epsilon) \leq \exp\left ( \right). And symmetrically (when ''X''''k'' is a sub-martingale): :\text(X_N - X_0 \leq -\epsilon) \leq \exp\left ( \right). If ''X'' is a martingale, using both inequalities above and applying the union bound allows one to obtain a two-sided bound: :\text(, X_N - X_0, \geq \epsilon) \leq 2\exp\left ( \right). Proof The proof shares similar idea of the pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chernoff Bound
In probability theory, the Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, the result is due to Herman Rubin. It is a sharper bound than the first- or second-moment-based tail bounds such as Markov's inequality or Chebyshev's inequality, which only yield power-law bounds on tail decay. However, the Chernoff bound requires the variates to be independent, a condition that is not required by either Markov's inequality or Chebyshev's inequality (although Chebyshev's inequality does require the variates to be pairwise independent). The Chernoff bound is related to the Bernstein inequalities, which were developed earlier, and to Hoeffding's inequality. The generic bound The generic Chernoff bound for a random variable is attained by applying Markov's inequality to . This gives a bound in terms of the moment-generating function ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Probability Theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set of axioms. Typically these axioms formalise probability in terms of a probability space, which assigns a measure taking values between 0 and 1, termed the probability measure, to a set of outcomes called the sample space. Any specified subset of the sample space is called an event. Central subjects in probability theory include discrete and continuous random variables, probability distributions, and stochastic processes (which provide mathematical abstractions of non-deterministic or uncertain processes or measured quantities that may either be single occurrences or evolve over time in a random fashion). Although it is not possible to perfectly predict random events, much can be said about their behavior. Two major results in probability ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Probabilistic Inequalities
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty."Kendall's Advanced Theory of Statistics, Volume 1: Distribution Theory", Alan Stuart and Keith Ord, 6th Ed, (2009), .William Feller, ''An Introduction to Probability Theory and Its Applications'', (Vol 1), 3rd Ed, (1968), Wiley, . The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin. Since the coin is fair, the two outcomes ("heads" and "tails") are both equally probable; the probability of "heads" equals the probability of "tails"; and since no other outcomes are possible, the probability of either "heads" or "tails" is 1/2 (which could also be written as 0.5 or 50%). These conc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Notation In Probability
Probability theory and statistics have some commonly used conventions, in addition to standard mathematical notation and mathematical symbols. Probability theory * Random variables are usually written in upper case roman letters: ''X'', ''Y'', etc. * Particular realizations of a random variable are written in corresponding lower case letters. For example, ''x''1, ''x''2, …, ''x''''n'' could be a sample corresponding to the random variable ''X''. A cumulative probability is formally written P(X\le x) to differentiate the random variable from its realization. * The probability is sometimes written \mathbb to distinguish it from other functions and measure ''P'' so as to avoid having to define "''P'' is a probability" and \mathbb(X\in A) is short for P(\), where \Omega is the event space and X(\omega) is a random variable. \Pr(A) notation is used alternatively. *\mathbb(A \cap B) or \mathbb \cap A/math> indicates the probability that events ''A'' and ''B'' both occur. The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of Probability Topics
This is a list of probability topics, by Wikipedia page. It overlaps with the (alphabetical) list of statistical topics. There are also the outline of probability and catalog of articles in probability theory. For distributions, see List of probability distributions. For journals, see list of probability journals. For contributors to the field, see list of mathematical probabilists and list of statisticians. General aspects * Probability * Randomness, Pseudorandomness, Quasirandomness * Randomization, hardware random number generator * Random number generation * Random sequence * Uncertainty * Statistical dispersion * Observational error * Equiprobable ** Equipossible * Average * Probability interpretations * Markovian * Statistical regularity * Central tendency * Bean machine * Relative frequency * Frequency probability * Maximum likelihood * Bayesian probability * Principle of indifference * Credal set * Cox's theorem * Principle of maximum entropy * Information entropy * Urn ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Glossary Of Probability And Statistics
This glossary of statistics and probability is a list of definitions of terms and concepts used in the mathematical sciences of statistics and probability, their sub-disciplines, and related fields. For additional related terms, see Glossary of mathematics and Glossary of experimental design. A B C D E F G H I J K L M N O P Q R S T ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Variance
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers is spread out from their average value. Variance has a central role in statistics, where some ideas that use it include descriptive statistics, statistical inference, hypothesis testing, goodness of fit, and Monte Carlo sampling. Variance is an important tool in the sciences, where statistical analysis of data is common. The variance is the square of the standard deviation, the second central moment of a distribution, and the covariance of the random variable with itself, and it is often represented by \sigma^2, s^2, \operatorname(X), V(X), or \mathbb(X). An advantage of variance as a measure of dispersion is that it is more amenable to algebraic manipulation than other measures of dispersion such as the expected absolute deviation; for e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Expected Value
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a large number of independently selected outcomes of a random variable. The expected value of a random variable with a finite number of outcomes is a weighted average of all possible outcomes. In the case of a continuum of possible outcomes, the expectation is defined by integration. In the axiomatic foundation for probability provided by measure theory, the expectation is given by Lebesgue integration. The expected value of a random variable is often denoted by , , or , with also often stylized as or \mathbb. History The idea of the expected value originated in the middle of the 17th century from the study of the so-called problem of points, which seeks to divide the stakes ''in a fair way'' between two players, who have to end th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Concentration Inequality
In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value (typically, its expected value). The law of large numbers of classical probability theory states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results show that such behavior is shared by other functions of independent random variables. Concentration inequalities can be sorted according to how much information about the random variable is needed in order to use them. Markov's inequality Let X be a random variable that is non-negative (almost surely). Then, for every constant a > 0, : \Pr(X \geq a) \leq \frac. Note the following extension to Markov's inequality: if \Phi is a strictly increasing and non-negative function, then :\Pr(X \geq a) = \Pr(\Phi (X) \geq \Phi (a)) \leq \frac. Cheb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Catalog Of Articles In Probability Theory
This page lists articles related to probability theory. In particular, it lists many articles corresponding to specific probability distributions. Such articles are marked here by a code of the form (X:Y), which refers to number of random variables involved and the type of the distribution. For example (2:DC) indicates a distribution with two random variables, discrete or continuous. Other codes are just abbreviations for topics. The list of codes can be found in the table of contents. Core probability: selected topics Probability theory Basic notions (bsc) * Random variable * Continuous probability distribution / (1:C) * Cumulative distribution function / (1:DCR) * Discrete probability distribution / (1:D) * Independent and identically-distributed random variables / (FS:BDCR) * Joint probability distribution / (F:DC) * Marginal distribution / (2F:DC) * Probability density function / (1:C) * Probability distribution / (1:DCRG) * Pro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.svg "Click for more on -> Probability Theory")
.svg "Click for more on -> Probabilistic Inequalities")
