Mastering Randomness and Collision Probability: A Hands-On Tutorial for Cs 6140 Assignments 1-6

Introduction: Why Randomness Matters in Data Science

Randomness is at the heart of many algorithms in data science, from randomized algorithms to probabilistic data structures. In this tutorial, we'll dive into the key concepts from Cs 6140 assignments 1-6, focusing on collision probability, coupon collector problems, and similarity estimation using min-hashing and LSH. By the end, you'll be able to implement experiments, analyze results, and connect theory to practice. This is especially relevant today (July 2026) as AI and big data applications rely on efficient randomized methods.

Part 1: The Birthday Paradox – Collision Probability in Action

The classic birthday paradox asks: How many people do you need in a room for a 50% chance that two share a birthday? For a domain size n=3000, we can simulate this. Assignment 1.A asks you to generate random numbers from [n] until a duplicate appears. Let's call the number of trials k.

Experiment: Simulating Collisions

Write a function that uses a set to track seen numbers. For each trial, generate a random integer between 1 and n. If it's already in the set, stop and return the count. For n=3000, you might get k around 64-70 on average. This is the empirical collision time.

Assignment 1.B requires repeating this m=300 times and plotting a cumulative density plot. The x-axis is k (trials), y-axis is fraction of experiments that succeeded (had a collision) by that k. Use Python's matplotlib to create the plot. The curve should rise from 0 to 1, resembling the theoretical CDF.

Empirical vs. Analytical Expected Value

For Assignment 1.C, compute the average k over m runs. For n=3000, the expected number of trials for a collision is about sqrt(π n/2) ≈ 68.6. Your empirical average should be close. Assignment 4.A asks for the analytical number of trials needed for probability ≥0.5. Using the approximation P(collision after k trials) ≈ 1 - exp(-k^2/(2n)), set this equal to 0.5 and solve for k: k ≈ sqrt(2n ln 2) ≈ sqrt(2*3000*0.693) ≈ 64.5. Compare to your empirical result.

Part 2: The Coupon Collector Problem – Collecting All Values

Now consider domain size n=100. Assignment 2.A asks: How many random trials until you have seen every number 1 to 100? This is the coupon collector problem. The expected number of trials is n * H_n ≈ 100 * (ln 100 + γ) ≈ 100 * (4.605 + 0.577) ≈ 518. So k should be around 500-600.

Experiment and Plot

Simulate by keeping a set of seen numbers. For each trial, generate a number and add to set. Stop when set size = n. Record k. Repeat m=300 times. For Assignment 2.B, create a cumulative density plot as before. The curve will rise more slowly than the collision case because it takes longer to collect all coupons.

Assignment 2.C: Compute empirical expected k. It should be close to the theoretical expectation. Assignment 4.B asks for analytical expected number: n * H_n ≈ 518. Compare.

Part 3: Random Bits to Random Integers

Assignment 5 explores generating random integers from random bits. If you only have rand-bit() that returns 0 or 1 uniformly, how to get a number between 1 and n=1024? Since 1024 = 2^10, you can generate 10 bits to form a binary number from 0 to 1023, then add 1. For n=1000 (not a power of 2), use a Las Vegas algorithm: generate enough bits to cover the range (e.g., 10 bits for 0-1023), then if the result is in [0,999], accept; otherwise repeat. This is expected to take about 1024/1000 ≈ 1.024 trials per number, so about 10.24 bit calls on average. As n grows, the number of bits needed is ceil(log2 n), and the rejection probability depends on how close n is to a power of 2.

Part 4: Concentration Bounds for Counts

Assignment 6 deals with the maximum deviation of frequencies from the average. For domain size n and k trials, let μ = max_i f_i / k. We want k such that Pr[|μ - 1/n| ≥ 0.01] ≤ δ. Using Chernoff bounds, we can show that k = O(n^2 log(1/δ)) for constant accuracy. For 0.1% accuracy, k scales by factor 100. This is a heavy-tailed result: to get high precision, you need many samples.

Part 5: Min-Hashing and LSH for Document Similarity

The second half of the assignment shifts to document similarity using k-grams, Jaccard similarity, min-hashing, and LSH. Given four documents (D1-D4), you construct character 2-grams, 3-grams, and word 3-grams. Assignment 7.A asks for the number of distinct k-grams per document. For example, D1 might have 150 character 2-grams, 200 character 3-grams, and 50 word 3-grams. Assignment 7.B requires Jaccard similarity between all pairs for each gram type. Jaccard = |intersection| / |union|. For two documents, this measures how similar they are.

Min-Hash Signatures

For Assignment 8.A, use character 3-grams (G2) and build min-hash signatures for D1 and D2 using t hash functions (t = 10, 50, 100, 250, 500). Each hash function maps k-grams to a large range (e.g., m=10000). The signature for a document is the minimum hash value among its k-grams. Then estimate Jaccard similarity as fraction of positions where signatures match. As t increases, estimate becomes more accurate. Assignment 8.B suggests t=100-250 is a good trade-off between accuracy and time.

LSH for Near-Duplicate Detection

Assignment 9 uses LSH with t=100 hash functions to find document pairs with Jaccard > 0.4. The trick: divide the signature into b bands of r rows each (b*r = t). For each band, hash the r-tuple to a bucket. Documents that agree on at least one band are candidate pairs. Choose b and r to optimize the S-curve: the probability that a pair with similarity s becomes a candidate is 1 - (1 - s^r)^b. For Jaccard threshold 0.4, typical choices are b=20, r=5. Adjust to achieve desired false positive and false negative rates.

Implementation Tips and Performance

For the experiments in assignments 1 and 2, use Python with efficient data structures (sets). For large n and m (e.g., n=1e6, m=10000), the simulation time can be significant. Plot runtime as a function of n for fixed m (e.g., m=300, 1000, 10000) to see O(n) or O(n log n) scaling. For min-hashing, use vectorized operations if possible. For LSH, implement band hashing carefully to avoid collisions.

Conclusion

Understanding randomness and probability is crucial for modern data science. This tutorial walked you through key concepts from Cs 6140 assignments 1-6: collision probability, coupon collector, random bit generation, concentration bounds, and similarity estimation via min-hashing and LSH. By implementing these experiments, you gain intuition that helps in designing and debugging algorithms. Whether you're working on AI, big data, or just curious about the math behind the scenes, these skills are invaluable.