dimostrazione probabilistica

Una dimostrazione probabilistica, o metodo probabilistico, è una tecnica di dimostrazione matematica non costruttiva dell'esistenza certa di un oggetto matematico tramite considerazioni probabilistiche. Il metodo è stato introdotto da Paul Erdős ed è applicato in combinatoria, teoria dei numeri, algebra lineare, analisi e in altre discipline applicate, come informatica o teoria dell'informazione. In generale, sfrutta il fatto che se tutti gli oggetti di un insieme non hanno una determinata proprietà, la probabilità che un oggetto scelto casualmente nell'insieme soddisfi quella proprietà è nulla. Se la probabilità è invece strettamente minore di uno, sicuramente almeno uno degli oggetti nell'insieme non soddisfa la proprietà. Considerando invece il valore atteso di una variabile aleatoria, se si dimostra che la variabile può assumere un valore inferiore al valore atteso allora deve assumere anche un valore maggiore rispetto ad esso.