Basic Probability Concepts

Probability measures the likelihood of events occurring, ranging from 0 (impossible) to 1 (certain):

Basic Probability Calculation

// Calculate probability as fraction and convert to decimal
double probability(long long favorable, long long total) {
    return (double)favorable / total;
}

// Calculate combinations C(n,r) = n!/(r!(n-r)!)
long long combination(int n, int r) {
    if(r > n || r < 0) return 0;
    if(r == 0 || r == n) return 1;
    
    long long result = 1;
    for(int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

// Probability of exactly k successes in n trials
double binomialProbability(int n, int k, double p) {
    return combination(n, k) * pow(p, k) * pow(1-p, n-k);
}
                    

Conditional Probability

The probability of event A given that event B has occurred: P(A|B) = P(A ∩ B) / P(B)

Bayes' Theorem

P(A|B) = P(B|A) × P(A) / P(B)

// Bayes' theorem implementation
double bayesTheorem(double priorA, double likelihoodB_given_A, double marginalB) {
    return (likelihoodB_given_A * priorA) / marginalB;
}

// Example: Medical test accuracy
double medicalDiagnosis(double diseaseRate, double testAccuracy, double falsePositiveRate) {
    // P(Disease|Positive Test)
    double priorDisease = diseaseRate;
    double likelihoodPositive_given_Disease = testAccuracy;
    double marginalPositive = testAccuracy * diseaseRate + falsePositiveRate * (1 - diseaseRate);
    
    return bayesTheorem(priorDisease, likelihoodPositive_given_Disease, marginalPositive);
}
                    

Expected Value and Variance

Expected value is the average outcome of a random variable over many trials:

// Calculate expected value for discrete random variable
double expectedValue(vector<double>& values, vector<double>& probabilities) {
    double expected = 0.0;
    for(int i = 0; i < values.size(); i++) {
        expected += values[i] * probabilities[i];
    }
    return expected;
}

// Calculate variance: E[X²] - (E[X])²
double variance(vector<double>& values, vector<double>& probabilities) {
    double mean = expectedValue(values, probabilities);
    double expectedSquare = 0.0;
    
    for(int i = 0; i < values.size(); i++) {
        expectedSquare += values[i] * values[i] * probabilities[i];
    }
    
    return expectedSquare - mean * mean;
}

// Linearity of expectation: E[X + Y] = E[X] + E[Y]
double linearExpectation(vector<double>& expectations) {
    double total = 0.0;
    for(double exp : expectations) {
        total += exp;
    }
    return total;
}
                    

Common Probability Distributions

Geometric Distribution

Probability of first success on the k-th trial: P(X = k) = (1-p)^(k-1) × p

// Geometric distribution - probability of first success on k-th trial
double geometricProbability(int k, double p) {
    return pow(1 - p, k - 1) * p;
}

// Expected value of geometric distribution: 1/p
double geometricExpectedValue(double p) {
    return 1.0 / p;
}
                    

Poisson Distribution

Models the number of events in a fixed interval: P(X = k) = (λ^k × e^(-λ)) / k!

// Poisson distribution
double poissonProbability(int k, double lambda) {
    double result = exp(-lambda);
    for(int i = 1; i <= k; i++) {
        result *= lambda / i;
    }
    return result;
}
                    

Randomized Algorithms

Algorithms that use random choices during execution:

Random Number Generation

#include <random>

class RandomGenerator {
private:
    mt19937 rng;
    
public:
    RandomGenerator() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    
    // Random integer in range [a, b]
    int randomInt(int a, int b) {
        uniform_int_distribution<int> dist(a, b);
        return dist(rng);
    }
    
    // Random double in range [0, 1)
    double randomDouble() {
        uniform_real_distribution<double> dist(0.0, 1.0);
        return dist(rng);
    }
    
    // Random permutation
    void randomShuffle(vector<int>& arr) {
        shuffle(arr.begin(), arr.end(), rng);
    }
};
                    

Monte Carlo Method

Estimate π using random points in a unit square:

double estimatePi(int numSamples) {
    RandomGenerator rng;
    int insideCircle = 0;
    
    for(int i = 0; i < numSamples; i++) {
        double x = rng.randomDouble() * 2 - 1; // [-1, 1)
        double y = rng.randomDouble() * 2 - 1; // [-1, 1)
        
        if(x * x + y * y <= 1.0) {
            insideCircle++;
        }
    }
    
    return 4.0 * insideCircle / numSamples;
}
                    

Markov Chains

A sequence of random states where the next state depends only on the current state:

// Simple Markov chain simulation
class MarkovChain {
private:
    vector<vector<double>> transitionMatrix;
    int numStates;
    RandomGenerator rng;
    
public:
    MarkovChain(vector<vector<double>>& transitions) 
        : transitionMatrix(transitions), numStates(transitions.size()) {}
    
    // Simulate one step
    int nextState(int currentState) {
        double rand = rng.randomDouble();
        double cumulative = 0.0;
        
        for(int i = 0; i < numStates; i++) {
            cumulative += transitionMatrix[currentState][i];
            if(rand <= cumulative) {
                return i;
            }
        }
        return numStates - 1; // Fallback
    }
    
    // Calculate steady-state probabilities (simplified)
    vector<double> steadyState(int iterations = 10000) {
        vector<double> currentProbs(numStates, 1.0 / numStates);
        
        for(int iter = 0; iter < iterations; iter++) {
            vector<double> nextProbs(numStates, 0.0);
            
            for(int i = 0; i < numStates; i++) {
                for(int j = 0; j < numStates; j++) {
                    nextProbs[j] += currentProbs[i] * transitionMatrix[i][j];
                }
            }
            currentProbs = nextProbs;
        }
        
        return currentProbs;
    }
};