Average Complexity, Random Walks and the Gambler's Ruin

Flashcards covering key concepts from average complexity, random walks, and the gambler's ruin, designed for exam preparation.

Averaging Complexity

The mathematical study of the expected performance or resource usage of algorithms, particularly in the context of their input size.

Random Walk

A stochastic process involving a sequence of steps where each step's direction is determined by a random outcome.

Biased Random Walk

A random walk where one direction is more likely than the other, affecting the overall outcome.

Gambler's Ruin

A classical problem in probability theory that describes a gambler who bets with fixed odds and either wins or loses money until they go broke or reach a target amount.

Markov Model

A statistical model that predicts a system's future state based on its current state, often used in analyzing random walks.

Harmonic Series

A divergent series defined as the sum of the reciprocals of the positive integers, denoted Hn = 1 + 1/2 + 1/3 + … + 1/n.

Absorbing State

In a Markov chain, an absorbing state is a state that, once entered, cannot be left.

Recurrence Equation

An equation that defines a sequence recursively, where each term is defined as a function of preceding terms.

Martingale

A model of a fair game where knowledge of past events never helps predict future winnings.

Probability of a Win (Gambler's Ruin)

In the context of gambling, it represents the likelihood of reaching a specified amount of funds before losing all.

Birthday Paradox

A probability theory phenomenon that shows how a surprisingly low number of people are required in a room for a shared birthday among them to be probable.

Total Capital (T)

The sum of a gambler's initial capital and the target amount they wish to win in a betting game.

Expected Value (E[X])

The average outcome of a random variable or process, computed as the weighted average of all possible values.