When attending a Dagstuhl seminar, you are randomly assigned a seat for lunch and dinner, to have a high chance to talk to everyone and not sticking to your peer group. A slideshow in the main stairway shows some minimal statistics if this is sufficient to meet everyone.
This post attempts to recreate the shown simulations for the Dagstuhl Seminar 25351: Computational Proteomics and find a theoretical formulation for this variant of the coupon collector problem.
The question is: If seating were purely random, would that even work for meeting everyone during a week-long seminar?
To answer this, a mathematical framework is needed that goes beyond the classical coupon collector problem. While that classic problem assumes collecting one coupon (meeting one person) at a time, Dagstuhl assigns you to a table with $r$ different people at once - you meet multiple people per "round."
A Generalization of the Coupon Collector Problem
The paper by Athreya, Mukherjee, and Mukherjee1 generalizes the classical coupon collector problem in a way by introducing the concept of "super-coupons" and analyzes the time complexity of collecting them all. A simpler formulation for problem can be found in earlier work 2 3.
The Generalization: Super-Coupons
- Universe: $n$ coupons, denoted $[n] = {1, 2, \ldots, n}$
- represents the set of participants
- Super-coupon: Any $s$-subset of the universe (where $s$ is fixed)
- represents the type of set you need to mark them as met
- Collection process: In each round, draw $r$ distinct coupons randomly. All $s$-subsets of these $r$ coupons are marked as "collected"
- Goal: Collect all $\binom{n}{s}$ possible super-coupons
In each round, you collect $\binom{r}{s}$ super-coupons. The question is: how long does it take to see all possible super-coupons?
Main Results
Expected Collection Time
The paper proves that the expected time $T^{(r,s)}$ to collect all super-coupons is:
$$\mathbb{E}T^{(r,s)} = \frac{\binom{n}{s} \log \binom{n}{s}}{\binom{r}{s}} \times (1 + o(1))$$
This can be rewritten as:
$$\mathbb{E}T^{(r,s)} = \frac{1}{(s-1)! \times \binom{r}{s}} \times n^s \log n \times (1 + o(1))$$
Key Insights
-
Understanding super-coupons:
- For $s=1$: Super-coupons are just individual entities (all 1-subsets)
- For $s=2$: Super-coupons are all possible pairs (2-subsets, unordered)
- For $s=k$: Super-coupons are all possible $k$-element combinations
-
Connection to classical case: When $s=1$, this becomes nearly identical to the classical coupon collector problem, but with $r$ items collected per round instead of 1. The formula simplifies to: $$\mathbb{E}T^{(r,1)} = \frac{n \log n}{r}$$
-
Consistency with classical case: When $r = s$, this reduces to the classical coupon collector problem (collecting one super-coupon per round)
-
Partial collection: For collecting $(1-\alpha)$-proportion of all super-coupons: $$\mathbb{E}T^{(r,s)}_\alpha = \frac{\binom{n}{s} \log(1/\alpha)}{\binom{r}{s}} \times (1 + o(1))$$
Back to the Dagstuhl Question
Now we can answer the original question: How long would it take to meet everyone at the Proteomics Seminar with random seating?
For our Dagstuhl setting with approximately 23 participants, sitting 6 people per table, this becomes a perfect case study of the generalized coupon collector problem with parameters $n=22, r=5, s=1$. $r$ is set to 5 because you are always part of the table, $n$ is set to 22 because you don't need to meet yourself.
The theoretical framework tells us that with purely random seating, we'd expect to meet everyone after approximately: $$\mathbb{E}T^{(5,1)} = \frac{22 \log 22}{5} \approx 14 \text{ meals}$$
Since a typical Dagstuhl seminar (Monday to Friday) has around 7 meals (3 days × 2 meals; 1 day x 1 meal (social events tend to happen outside of the venue); the random seating is not applied for breakfast; people leave Dagstuhl before lunch on Friday), random seating should not allow you to meet everyone - if the seating were truly random.
Testing the Theory with Simulation
Let's test whether the mathematical theory matches reality. We'll simulate the Dagstuhl seating process assuming purely random assignment and see how it compares to the theoretical predictions.
First, let's calculate the exact theoretical predictions using the paper's formulas:
Paper's Theoretical Formulas
# Theoretical Formulas from the Paper
# Parameters for our example
n <- 22 # total people (universe size)
r <- 5 # people at table each round (draw size)
s <- 1 # collecting individuals (super-coupon size)
cat("=== Paper's Theoretical Formulas ===\n")
cat("Parameters: n =", n, ", r =", r, ", s =", s, "\n\n")
# Main result: Expected collection time
# ET^(r,s) = [(n choose s) log (n choose s)] / (r choose s) × (1 + o(1))
n_choose_s <- choose(n, s)
r_choose_s <- choose(r, s)
expected_time_exact <- (n_choose_s * log(n_choose_s)) / r_choose_s
cat("Main Formula: ET^(r,s) = [(n choose s) log (n choose s)] / (r choose s)\n")
cat(" (n choose s) =", n_choose_s, "\n")
cat(" (r choose s) =", r_choose_s, "\n")
cat(" Expected time =", round(expected_time_exact, 2), "rounds\n\n")
# Simplified form for large n (when s=1)
# ET^(r,s) = n log n / r × (1 + o(1))
expected_time_simplified <- n * log(n) / r
cat("Simplified Formula (s=1): ET^(r,1) = n log n / r\n")
cat(" Expected time =", round(expected_time_simplified, 2), "rounds\n\n")
# Partial collection formula
# ET^(r,s)_α = [(n choose s) log(1/α)] / (r choose s) × (1 + o(1))
cat("Partial Collection Formula: ET^(r,s)_α = [(n choose s) log(1/α)] / (r choose s)\n")
alpha_values <- c(0.5, 0.05, 0.01)
alpha_labels <- c("50%", "95%", "99%")
for(i in 1:length(alpha_values)) {
alpha <- alpha_values[i]
label <- alpha_labels[i]
time_alpha <- (n_choose_s * log(1/alpha)) / r_choose_s
cat(" For", label, "probability (α =", alpha, "):\n")
cat(" log(1/α) = log(1/", alpha, ") =", round(log(1/alpha), 2), "\n")
cat(" Expected time =", round(time_alpha, 1), "rounds\n")
}
cat("\n=== Formula Verification ===\n")
cat("Main formula equals simplified? ",
abs(expected_time_exact - expected_time_simplified) < 0.001, "\n")
cat("Both give:", round(expected_time_exact, 2), "rounds\n")
Click "Run R Code" to execute. WebR will initialize on first use (may take 10-30 seconds).
Now let's run Monte Carlo simulations to see how random seating actually performs. The first plot shows the distribution of completion times from many simulated seminars, each running until all participants have met:
Simulation Results and Plots
# Monte Carlo Simulation and Visualization
library(ggplot2)
library(dplyr)
# Parameters (matching the theoretical analysis)
n <- 22 # total people
r <- 5 # people at table each round
s <- 1 # collecting individuals
# Theoretical predictions (from formulas)
expected_time_theory <- (choose(n,s) * log(choose(n,s))) / choose(r,s)
# Partial collection: time to see (1-α)-proportion of all people
time_see_50pct <- (choose(n,s) * log(1/0.5)) / choose(r,s) # α=0.5 → see 50% of people
time_see_95pct <- (choose(n,s) * log(1/0.05)) / choose(r,s) # α=0.05 → see 95% of people
time_see_99pct <- (choose(n,s) * log(1/0.01)) / choose(r,s) # α=0.01 → see 99% of people
cat("=== Theoretical Predictions ===\n")
cat("Expected time to see everyone:", round(expected_time_theory, 2), "rounds\n")
cat("Expected time to see 50% of people:", round(time_see_50pct, 1), "rounds\n")
cat("Expected time to see 95% of people:", round(time_see_95pct, 1), "rounds\n")
cat("Expected time to see 99% of people:", round(time_see_99pct, 1), "rounds\n\n")
# Single simulation function
simulate_collection <- function() {
seen <- rep(FALSE, n)
round <- 0
while(sum(seen) < n) {
round <- round + 1
# Sample r people without replacement
people_at_table <- sample(1:n, r, replace = FALSE)
seen[people_at_table] <- TRUE
}
return(round)
}
# Run Monte Carlo simulation
num_sims <- 2000
set.seed(11) # for reproducibility
results <- replicate(num_sims, simulate_collection())
cat("=== Simulation Results (", num_sims, " runs) ===\n")
cat("Mean:", round(mean(results), 2), "rounds\n")
cat("Median:", median(results), "rounds\n")
cat("Standard deviation:", round(sd(results), 2), "\n")
cat("95th percentile:", quantile(results, 0.95), "rounds\n\n")
# Compare theory vs simulation
cat("=== Theory vs Simulation ===\n")
cat("Theory predicts:", round(expected_time_theory, 2), ", Simulation gives:", round(mean(results), 2), "\n")
cat("Difference:", round(abs(expected_time_theory - mean(results)), 2), "rounds\n\n")
# Plot 1: Histogram of complete collection times
hist_data <- data.frame(rounds = results)
p1 <- ggplot(hist_data, aes(x = rounds)) +
geom_histogram(binwidth=1, alpha = 0.7, fill = "steelblue", color = "white") +
geom_vline(xintercept = expected_time_theory, color = "red", linetype = "dashed", linewidth = 1) +
geom_vline(xintercept = mean(results), color = "orange", linetype = "solid", linewidth = 1) +
labs(title = "Distribution of Times to See Everyone",
subtitle = paste("n =", n, ", r =", r, ", s =", s, "(", num_sims, "simulations)"),
x = "Rounds to see all people",
y = "Frequency") +
annotate("text", x = expected_time_theory + 1.5, y = max(table(results)) * 0.8,
label = paste("Theory:", round(expected_time_theory, 1)), color = "red", size = 3) +
annotate("text", x = mean(results) + 1.5, y = max(table(results)) * 0.6,
label = paste("Simulation:", round(mean(results), 1)), color = "orange", size = 3) +
theme_minimal()
print(p1)
# Plot 2: Cumulative probability of complete collection
sorted_results <- sort(results)
cum_prob <- seq_along(sorted_results) / length(sorted_results)
cum_data <- data.frame(rounds = sorted_results, probability = cum_prob)
p2 <- ggplot(cum_data, aes(x = rounds, y = probability)) +
geom_step(color = "steelblue", linewidth = 1, alpha = 0.8) +
geom_hline(yintercept = 0.5, color = "red", linetype = "dashed", alpha = 0.7) +
geom_hline(yintercept = 0.95, color = "orange", linetype = "dashed", alpha = 0.7) +
geom_hline(yintercept = 0.99, color = "purple", linetype = "dashed", alpha = 0.7) +
labs(title = "Cumulative Probability of Seeing Everyone",
subtitle = "Simulation results - probability of complete collection",
x = "Rounds",
y = "Probability of having seen all people") +
annotate("text", x = max(sorted_results) * 0.8, y = 0.52,
label = "50%", color = "red", size = 3) +
annotate("text", x = max(sorted_results) * 0.8, y = 0.97,
label = "95%", color = "orange", size = 3) +
annotate("text", x = max(sorted_results) * 0.8, y = 1.01,
label = "99%", color = "purple", size = 3) +
scale_y_continuous(labels = scales::percent_format()) +
theme_minimal()
print(p2)
# Plot 3: Partial collection progress (theoretical vs simulation)
# Simulate partial collection progress for one run
set.seed(123)
seen <- rep(FALSE, n)
round <- 0
progress <- c()
progress_pct <- c()
while(sum(seen) < n) {
round <- round + 1
people_at_table <- sample(1:n, r, replace = FALSE)
seen[people_at_table] <- TRUE
progress <- c(progress, sum(seen))
progress_pct <- c(progress_pct, sum(seen) / n * 100)
}
partial_data <- data.frame(
round = 1:length(progress),
people_seen = progress,
percent_seen = progress_pct
)
p3 <- ggplot(partial_data, aes(x = round, y = percent_seen)) +
geom_line(color = "steelblue", linewidth = 1) +
geom_point(color = "steelblue", alpha = 0.7, size = 2) +
geom_hline(yintercept = 50, color = "red", linetype = "dashed", alpha = 0.7) +
geom_hline(yintercept = 95, color = "orange", linetype = "dashed", alpha = 0.7) +
geom_hline(yintercept = 99, color = "purple", linetype = "dashed", alpha = 0.7) +
geom_hline(yintercept = 100, color = "black", linetype = "solid", alpha = 0.7) +
geom_vline(xintercept = time_see_50pct, color = "red", linetype = "dotted", alpha = 0.7) +
geom_vline(xintercept = time_see_95pct, color = "orange", linetype = "dotted", alpha = 0.7) +
geom_vline(xintercept = time_see_99pct, color = "purple", linetype = "dotted", alpha = 0.7) +
labs(title = "Example: Partial Collection Progress",
subtitle = "Theory vs. single simulation run",
x = "Round",
y = "Percentage of people seen") +
annotate("text", x = time_see_50pct - 0.5, y = 25,
label = paste("Theory 50%:", round(time_see_50pct, 1)), color = "red", size = 3, angle = 90) +
annotate("text", x = time_see_95pct - 0.5, y = 25,
label = paste("Theory 95%:", round(time_see_95pct, 1)), color = "orange", size = 3, angle = 90) +
annotate("text", x = time_see_99pct - 0.5, y = 25,
label = paste("Theory 99%:", round(time_see_99pct, 1)), color = "purple", size = 3, angle = 90) +
ylim(0, 105) +
theme_minimal()
print(p3)
Click "Run R Code" to execute. WebR will initialize on first use (may take 10-30 seconds).
What This Means for Dagstuhl
- With truly random seating, you'd expect to meet everyone in about 14 meals on average
- It should require ~4 meals to meet 50% of all participants