Bins and Balls Simulator (RA Assignment)

A C++ simulation of the balls and bins model, with multiple ball allocation strategies. With support for automated experiments and analysis via a Python notebook.

---

1. Setup

Clone the repository:

git clone https://github.com/PauJimeno/RA_Assignment-2.git
cd RA_Assignment-2

---

2. Compiling and Running the Simulation

2.1 Compilation

Compile the C++ code using g++:

g++ -o simulation simulation.cpp

No external libraries have been used.

2.2 Simulation Parameters

The simulation supports several parameters. Use --help or -h to view usage:

./simulation --help

Flag	Type	Description	Default
-m / --bins	<int>	Number of bins	100
-n / --balls	<int>	Number of balls	100
-d / --sample	<double>	Number of bins for d-choice criteria (1<=d)	1
-k / --queries	<int>	Number of binary queries to use in b-batched setting	0
-b / --batches	<int>	Number of batches (b>0) for the b-batched setting	1

2.3 Examples

1. Heavily loaded d-choice scheme with $d=3$

./simulation -m 100 -n 10000 -d 3 

2. Heavily loaded $1+\beta$-choice scheme with $\beta=0.7$

Here the $\beta$ parameter is passed through the decimal part of the $d$ paremeter so $d=1.7$ means 70% of 2 choice and 30% of 1 choice allocation.

./simulation -m 100 -n 10000 -d 1.7

3 . Heavily loaded b-batch scheme with $k=2$, $b=8$ and $d=2$

./simulation -m 100 -n 10000 -d 2 -k 2 -b 8

2.4 Output

The simulation prints the most loaded bin $\max(X_i)$, average load, maximum gap $G_i$ and the amount of balls in each bin. Example (10 bins, 100 balls):

99;101;100;99;98;101;100;100;101;101
max(Xi) = 101
average/bin = 100
Gn = 1

---

3. Python Notebook for Analysis

A Python notebook (Balls_and_Bins.ipynb) is provided to average multiple simulations, compute variance, analyze results and generate plots. Requires numpy and matplotlib.

3.1 Example Usage for an icreasing amount of balls following a logaritmic step (with 20 steps), 10 averaged simulations ($T=10$), different amounts of bins.

exec_name = "simulation"
bins = [10, 30, 50, 70, 100, 1000]
d_choice = [1, 2, 3]
n_s = 10
step = 20
log=True

for m in bins:
    results_matrix = []
    labels = []
    for d in d_choice:
        Gn_arr, _, n_values = run_experiment(exec_name, m, m, d, m*m, step, n_s, log=log)
        results_matrix.append(Gn_arr)
        labels.append(f"d={d}")
    title = f"d-choice comparison with $n\in[m..m^2$], m={m}"
    plot_multiple(n_values, results_matrix, m, labels, title, log=log, xticks=(m<=100))

The run_experiment function:

1. Runs the C++ simulation in a subprocess.
2. Collects results over $T$ runs of the experiment.

More details can be found in the notebook.

---

3.2 Example Plots

The notebook produces plots such as:

---

Group

Pau Jimeno Román

Thomas Aubertier

---