Stochastic convergence

From Citizendium
Revision as of 03:55, 7 July 2007 by imported>Jitse Niesen (use \stackrel)
Jump to navigation Jump to search

Stochastic convergence is a mathematical concept intended to formalize the idea that a sequence of essentially random or unpredictable events sometimes is expected to settle into a pattern.


Various possible modes of stochastic convergence

The pattern may for instance be

  • convergence in the classical sense to a fixed value, perhaps itself coming from a random event.
  • an increasing similarity of outcomes to what a purely deterministic function would produce
  • an increasing preference towards a certain outcome
  • an increasing "aversion" against straying far away from a certain outcome
  • an increasing adherence to one particular probability distribution
  • the series formed by calculating the expected value of the outcome's distance from a particular value may converge to 0
  • the variability of the results may grow smaller and smaller, i.e. the variance converging to 0


Four different varieties of stochastic convergence are noted:

  • Almost sure convergence
  • Convergence in probability
  • Convergence in distribution
  • Convergence in rth order mean


Almost sure convergence

This is the type of stochastic convergence that is most similar to ordinary convergence known from elementary real analysis.

Examples

Basic example 1

Consider an animal of some short-lived species. We note the exact amount of food that this animal consumes day by day. This sequence of numbers will be unpredictable in advance, but we may be quite certain that one day the number will become zero, and will stay zero forever after.

Basic example 2

Consider a man who starts tomorrow to toss seven coins once every morning. Each afternoon, he donates a random amount of money to a certain charity. The first time the result is all tails, however, he will stop permanently.

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1, X_2, ... } be the day by day amounts the charity receives from him.

We may be almost sure that one day this amount will be zero, and stay zero forever after that.

However, when we consider any finite number of days, there is a nonzero probability the terminating condition will not occur.

Intermediate example

A business owner has two sources of income: His business, and interest from a large bank deposit with fixed interest and no withdrawal or deposits.

The business income varies unpredictably from month to month, while income from interest is predictable and given by a simple function f.

The income for month i can thus be modeled by a random variable Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_i=X_i+f(i)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} is the income from the business.

Now assume Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} converges almost surely to 0 (history bears out that all businesses sooner or later fold up).

Then the total monthly income Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_i} has almost sure convergence to the function f(i).

Formal definition

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle X_0, X_1, ... } be an infinite sequence of random variables defined over a subset of R.

Then the actual outcomes will be an ordinary sequence of real numbers.

If the probability that this sequence will converge to a given real number a equals 1, then we say the original sequence of stochastic variables has almost sure convergence to a.

In more compact notation:

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\lim_{i \to \infty} X_i = a) = 1 } for some a, then the sequence has almost sure convergence to a.

Note that we may replace the real number a above by a real-valued function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(i)} of i, and obtain almost sure convergence to a function rather than a fixed number.

The number a may also be the outcome of a random variable X. In that case the compact notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\lim_{i \to \infty} X_i = X) = 1 } is often used.

Commonly used notation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i \stackrel{a.s.}{\rightarrow} a } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i \stackrel{a.s.}{\rightarrow} X } .

Convergence in probability

The basic idea is that the probability of an "freaky" outcome becomes smaller and smaller, while the idea of "non-freaky" may become stricter and stricter.

Examples

Basic example

Assume someone has an infinite supply of envelopes and money, and likes to play the following game: He shows you a number of sealed envelopes. Inside exactly one is a $5 bill, any and all of the others all contain $1. You get to pick exactly one envelope, and keep the content.

Tomorrow he plays the game using 1 envelope, the second day he uses two envelopes, the 3rd day there'll be 3 envelopes, etc.

Then the amount of dollars you earn from the game on a given day will be a random variable that converges in probability to $1, because the probability of guessing the "right" envelope steadily shrinks.

In the long run, then, an outcome different from $1 will become an increasingly "freaky" event.

Formal definition

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle X_0, X_1, ... } be an infinite sequence of random variables defined over a subset of R.

If there exists a real number a such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{i \to \infty} P( |X_i - a| > \varepsilon) = 0 } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon >0} , then the sequence has convergence in probability to a.


Commonly used notation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i \stackrel{P}{\rightarrow} a} .

Convergence in distribution

With this mode of convergence, we increasingly expect to see our next outcome in a sequence of random experiments becoming better and better modeled by a given probability distribution.

Examples

Basic example

The outcome from tossing a non-biased dice follows the uniform discrete distribution.

Assume a new dice factory has just been built.

The first few dices come out quite biased, due to imperfections in the production process. The outcome from tossing any of them will follow a distribution markedly different from the desired uniform discrete distribution.

As the factory is improved, the dices will be less and less loaded, and the outcomes from tossing a newly produced dice will follow the desired distribution more and more closely.

Intermediate example

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle X_n} be the result of flipping n unbiased coins, and noting the fraction of heads.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle X_1} will then follow the uniform discrete probability distribution with expected value Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu=0.5} and variance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma^2=0.25} , but as n grows larger, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle X_n} will follow a distribution that gradually takes on more and more similarity to the gaussian distribution .

Forming the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle Z_n= \frac{ (X_n - \mu) }{\frac {\sigma} {\sqrt {n }}} } , we find the random variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_n } becoming distributed more and more like the standard normal distribution as n increases.

We then say the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle Z_n} converges in distribution to the standard normal distribution.

(This convergence follows from the famous central limit theorem).

Formal definition

Given a random variable X with a cumulative distribution function F(x), let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} be a sequence of random variables, each with cumulative distribution function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_i (x)} , respectively.

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \lim_{i \to \infty} F_i (x) = F(x)} for all x where F(x) is continuous, then the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} of stochastic variables converges in distribution to the distribution of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} .

Commonly used notation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i \stackrel{L}{\rightarrow} X} . One can also use the distribution directly, so if f.i. X is normally distributed with mean 0 and variance 1, one could write Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i \stackrel{L}{\rightarrow} N(0,1)} .

Convergence in rth order mean

This is a rather "technical" mode of convergence. We essentially compute a sequence of real numbers, one number for each random variable, and check if this sequence is convergent in the ordinary sense.

Example

A newly built factory produces cans of beer. The owners want each can to contain exactly a certain amount.

Knowing the details of the current production process, engineers may compute the expected error in a newly produced can.

They are continuously improving the production process, so as time goes by, the expected error in a newly produced can tends to zero.

This example illustrates convergence in first order mean.

Formal definition

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \lim_{n \to \infty} E(|X_n - a|^r ) =0} for some real number a, then {Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_n} } converges in rth order mean to a.

Commonly used notation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_n \stackrel{L_r}{\rightarrow} a} .

Relations between the different modes of convergence

  • If a sequence of random variables has almost sure convergence, then it also has convergence in probability.
  • If a sequence of random variables has convergence in probability, then it also has convergence in distribution.
  • If a sequence of random variables has convergence in (r+1)th order mean, then it also has convergence in rth order mean (r>0).
  • If a sequence of random variables has convergence in rth order mean, then it also has convergence in probability.


See also


Related topics


References

External links

Retrieved from "https://citizendium.org/wiki/index.php?title=Stochastic_convergence&oldid=251004"