Expected Value

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main() {
5
    // Example: Expected value of a fair six-sided die
6
    // Analytical computation using the PMF: p(k) = 1/6 for k=1..6
7
    vector<int> values = {1,2,3,4,5,6};
8
    vector<double> probs(6, 1.0/6.0);
9
10
    double expected = 0.0;
11
    for (int i = 0; i < 6; ++i) expected += values[i] * probs[i];
12
13
    // Monte Carlo simulation to estimate E[X]
14
    const int64_t TRIALS = 2'000'000; // 2 million rolls
15
    mt19937 rng(42); // fixed seed for reproducibility
16
    uniform_int_distribution<int> die(1, 6);
17
18
    long double sum = 0.0L;
19
    for (int64_t t = 0; t < TRIALS; ++t) sum += die(rng);
20
    long double estimate = sum / TRIALS;
21
22
    cout.setf(ios::fixed); cout << setprecision(6);
23
    cout << "Analytical E[die] = " << expected << "\n";
24
    cout << "Monte Carlo estimate = " << (double)estimate << " (|error| = " << fabs((double)estimate - expected) << ")\n";
25
26
    // Time Complexity: O(TRIALS)
27
    // Space Complexity: O(1)
28
    return 0;
29
}
30

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count collisions as number of colliding pairs across buckets
5
// If a bucket has c keys, it contributes c*(c-1)/2 colliding pairs.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n = 200;      // number of keys
12
    int m = 1000;     // number of buckets
13
    int TRIALS = 3000; // Monte Carlo trials
14
15
    // Analytical expectation via indicators:
16
    // For each pair (i,j), P(collision) = 1/m under uniform hashing.
17
    // E[collisions] = C(n,2)/m
18
    long double analytical = ( (long double)n * (n - 1) / 2.0L ) / (long double)m;
19
20
    mt19937 rng(123);
21
    uniform_int_distribution<int> bucket(0, m - 1);
22
23
    long double sum = 0.0L;
24
    vector<int> cnt(m);
25
    for (int t = 0; t < TRIALS; ++t) {
26
        fill(cnt.begin(), cnt.end(), 0);
27
        for (int i = 0; i < n; ++i) {
28
            int b = bucket(rng); // random bucket for key i
29
            ++cnt[b];
30
        }
31
        long long collisions = 0;
32
        for (int b = 0; b < m; ++b) {
33
            long long c = cnt[b];
34
            collisions += c * (c - 1) / 2; // number of colliding pairs in this bucket
35
        }
36
        sum += collisions;
37
    }
38
    long double estimate = sum / TRIALS;
39
40
    cout.setf(ios::fixed); cout << setprecision(6);
41
    cout << "Analytical E[collisions] = " << (double)analytical << "\n";
42
    cout << "Monte Carlo estimate     = " << (double)estimate
43
         << " (|error| = " << fabsl(estimate - analytical) << ")\n";
44
45
    // Time Complexity: O(TRIALS * (n + m)) because we assign n keys and scan m buckets each trial
46
    // Space Complexity: O(m) for bucket counts
47
    return 0;
48
}
49

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    double p = 0.3;          // success probability per trial
9
    int TRIALS = 1'000'000;  // number of experiments
10
11
    mt19937 rng(2024);
12
    uniform_real_distribution<double> U(0.0, 1.0);
13
14
    long double total_trials = 0.0L;
15
    for (int t = 0; t < TRIALS; ++t) {
16
        int count = 0;
17
        // Keep trying until success (U < p)
18
        while (true) {
19
            ++count;
20
            if (U(rng) < p) break;
21
        }
22
        total_trials += count;
23
    }
24
    long double estimate = total_trials / TRIALS;
25
    long double analytical = 1.0L / p;
26
27
    cout.setf(ios::fixed); cout << setprecision(6);
28
    cout << "Analytical E[trials] = " << (double)analytical << "\n";
29
    cout << "Monte Carlo estimate = " << (double)estimate
30
         << " (|error| = " << fabsl(estimate - analytical) << ")\n";
31
32
    // Time Complexity: O(TRIALS * E[X]) = O(TRIALS / p) expected, since each loop averages 1/p iterations
33
    // Space Complexity: O(1)
34
    return 0;
35
}
36

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute harmonic number H_n
5
long double harmonic(int n) {
6
    long double H = 0.0L;
7
    for (int k = 1; k <= n; ++k) H += 1.0L / k;
8
    return H;
9
}
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n = 50; // number of coupon types
16
17
    // Analytical formula: E[T] = n * H_n
18
    long double analytical = (long double)n * harmonic(n);
19
20
    // DP-style stage expectation: from k collected to k+1 collected takes geometric steps
21
    // with success prob p_k = (n - k) / n, so expected steps = 1 / p_k = n / (n - k)
22
    long double staged = 0.0L;
23
    for (int k = 0; k < n; ++k) staged += (long double)n / (n - k);
24
25
    // Monte Carlo simulation for a smaller n to keep runtime reasonable
26
    int n_small = 20;
27
    int TRIALS = 2000;
28
    mt19937 rng(7);
29
    uniform_int_distribution<int> pick(0, n_small - 1);
30
31
    long double sum_steps = 0.0L;
32
    vector<char> seen(n_small);
33
    for (int t = 0; t < TRIALS; ++t) {
34
        fill(seen.begin(), seen.end(), 0);
35
        int distinct = 0;
36
        int steps = 0;
37
        while (distinct < n_small) {
38
            int c = pick(rng);
39
            if (!seen[c]) { seen[c] = 1; ++distinct; }
40
            ++steps;
41
        }
42
        sum_steps += steps;
43
    }
44
    long double sim_estimate = sum_steps / TRIALS;
45
    long double sim_analytical = (long double)n_small * harmonic(n_small);
46
47
    cout.setf(ios::fixed); cout << setprecision(6);
48
    cout << "Coupon collector (n=" << n << ")\n";
49
    cout << "Formula: n*H_n           = " << (double)analytical << "\n";
50
    cout << "Stage sum (DP-style)     = " << (double)staged << "\n";
51
    cout << "\nSimulation (n=" << n_small << ", trials=" << TRIALS << ")\n";
52
    cout << "Monte Carlo estimate      = " << (double)sim_estimate << "\n";
53
    cout << "Analytical for n_small    = " << (double)sim_analytical
54
         << " (|error| = " << fabsl(sim_estimate - sim_analytical) << ")\n";
55
56
    // Time Complexity:
57
    // - Harmonic/Stage sums: O(n)
58
    // - Simulation: O(TRIALS * expected steps) ≈ O(TRIALS * n_small log n_small)
59
    // Space Complexity: O(1) for formulas, O(n_small) for simulation state
60
61
    return 0;
62
}
63