630  The Birthday Problem in IoT Networks

630.1 Learning Objectives

By the end of this chapter, you will be able to:

• Apply the Birthday Problem formula to calculate collision probability
• Explain why address collisions occur more often than intuition suggests
• Evaluate the impact of address size on collision probability
• Calculate collision thresholds for different IoT address spaces

630.2 Introduction

Time: ~10 min | Difficulty: Intermediate | Unit: P07.C15.U04a

When designing IoT networks, engineers often assume that address collisions are extremely unlikely given the large address spaces available. However, the Birthday Problem (also called the Birthday Paradox) reveals a surprising truth: collisions occur far more frequently than intuition suggests, with critical implications for MAC addresses, short addresses, and network design.

630.3 The Classic Birthday Problem

The Question: In a room of randomly selected people, how many people do you need before there’s a 50% chance that two people share the same birthday?

Intuitive Answer: Most people guess around 183 (half of 365 days in a year).

Actual Answer: Only 23 people are needed for a 50% probability of a shared birthday!

Why So Few? The key insight is that we’re not comparing each person to a specific birthday - we’re comparing all possible pairs of people. With 23 people, there are 253 possible pairs (23 x 22 / 2 = 253), which is why the probability grows much faster than expected.

630.4 The Birthday Problem Formula

The general formula for collision probability is:

\[P(\text{collision}) \approx 1 - e^{-n^2/(2m)}\]

Where: - n = number of items (devices, addresses assigned) - m = number of possible values (address space size) - e = Euler’s number (approximately 2.718)

Key Insight: Probability depends on n squared, not n. This quadratic relationship means collisions grow much faster than the number of devices.

630.5 Application to IoT: MAC Address Collisions

MAC Address Space: - 48-bit MAC addresses = 2^48 = 281,474,976,710,656 addresses (281 trillion) - Seems impossible to ever have collisions, right?

Reality Check Using Birthday Problem:

Number of Devices	Collision Probability	Practical Scenario
1 million	0.000002% (1 in 50 million)	Small city IoT deployment
100 million	0.002% (1 in 50,000)	National IoT network
1 billion	0.2% (1 in 500)	Global smart home devices
10 billion	18% (nearly 1 in 5!)	Projected IoT devices by 2030
20 billion	53% (1 in 2)	High-density IoT future

Calculation Example (1 billion devices):

\[P(\text{collision}) \approx 1 - e^{-(10^9)^2/(2 \times 2^{48})} = 1 - e^{-0.00178} \approx 0.00178 = 0.178\%\]

Real-World Impact: With 1 billion IoT devices deployed globally, approximately 1.78 million devices will experience MAC address collisions! This explains why manufacturers must carefully manage MAC address allocation from IEEE-assigned blocks.

630.6 Short Addresses: The Critical Case

Many IoT protocols use short addresses for efficiency. The Birthday Problem becomes severe in these constrained address spaces.

630.6.1 16-bit Short Addresses (802.15.4, Zigbee)

Address Space: 2^16 = 65,536 addresses

Collision Probability:

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#E67E22', 'secondaryColor': '#16A085', 'tertiaryColor': '#E8F6F3'}}}%%
xychart-beta
    title "Collision Probability vs Network Size (16-bit addresses)"
    x-axis "Number of Devices" [50, 100, 150, 200, 250, 300, 350]
    y-axis "Collision Probability %" 0 --> 100
    line [2, 7, 15, 26, 39, 52, 64]

Figure 630.1: Collision probability growth from 2% at 50 devices to 64% at 350 devices

{fig-alt=“Line chart showing exponential growth of collision probability for 16-bit address space, rising from 2% at 50 devices to 64% at 350 devices, illustrating the Birthday Problem’s impact on IoT networks with constrained addressing”}

Critical Threshold: With just 300 devices, there’s a 52% chance of address collision!

Why Zigbee Networks Limit Device Count:

802.15.4 Personal Area Network (PAN):
- Coordinator assigns 16-bit short addresses randomly
- With 300 devices: 50% collision probability
- With 250 devices: 39% collision probability (acceptable with detection)
- With 500 devices: 85% collision probability (network breakdown!)

This is why Zigbee specifications recommend:
- Maximum 250-300 devices per PAN
- Use collision detection and reassignment
- Or fall back to 64-bit extended addresses

630.7 Collision Probability Table Across Address Sizes

The following table shows how many devices produce a 50% collision probability for different address sizes commonly used in IoT:

Address Size	Total Addresses	Devices for 50% Collision	IoT Protocol Examples
16-bit	65,536	~300 devices	802.15.4 short addresses, Zigbee PANs
24-bit	16,777,216	~4,800 devices	Some proprietary protocols
32-bit	4,294,967,296	~77,000 devices	IPv4 private networks (with NAT)
48-bit	281 trillion	~20 million devices	MAC addresses (Ethernet, Wi-Fi, BLE)
64-bit	18.4 quintillion	~5 billion devices	EUI-64, IPv6 IIDs, LoRaWAN DevEUI
128-bit	340 undecillion	~26 quintillion devices	IPv6 addresses, UUIDs

Key Observation: The “50% threshold” device count is approximately square root(address space x 1.177). This square root relationship means doubling the address bits increases the safe device count by 2^8 = 256x, not just 2x!

630.8 Interactive Visualization: Birthday Problem Calculator

NoteCalculate Collision Probability for Your IoT Network

Estimate the probability of address collisions based on your address space size and device count.

viewof addressBits = Inputs.range([8, 128], {value: 16, step: 1, label: "Address Size (bits)"})
viewof deviceCount = Inputs.range([10, 100000], {value: 300, step: 10, label: "Number of Devices"})

birthdayCalc = {
  const addressSpace = Math.pow(2, addressBits);
  const n = deviceCount;
  const m = addressSpace;

  // Birthday problem approximation: P = 1 - e^(-n^2/2m)
  const exponent = -(n * n) / (2 * m);
  const collisionProb = 1 - Math.exp(exponent);
  const collisionPct = collisionProb * 100;

  // Calculate 50% threshold
  const fiftyPctDevices = Math.sqrt(2 * m * Math.log(2));

  return {
    addressSpace: addressSpace.toExponential(2),
    collisionProb: collisionProb,
    collisionPct: collisionPct.toFixed(4),
    fiftyPctDevices: Math.round(fiftyPctDevices),
    risk: collisionPct < 1 ? "Low Risk" : collisionPct < 10 ? "Medium Risk" : collisionPct < 50 ? "High Risk" : "Critical Risk"
  };
}

md`### Collision Probability Analysis

| Metric | Value |
|--------|-------|
| **Address Space Size** | 2^${addressBits} = ${birthdayCalc.addressSpace} addresses |
| **Current Device Count** | ${deviceCount} devices |
| **Collision Probability** | ${birthdayCalc.collisionPct}% |
| **Risk Level** | ${birthdayCalc.risk} |
| **50% Collision Threshold** | ${birthdayCalc.fiftyPctDevices} devices |

**Interpretation:** ${birthdayCalc.collisionPct < 1 ?
  "Your network has very low collision risk. Address space is adequate." :
  birthdayCalc.collisionPct < 10 ?
  "Moderate risk - implement collision detection mechanisms." :
  birthdayCalc.collisionPct < 50 ?
  "High risk - consider using larger address space or deterministic assignment." :
  "Critical risk - address collisions are highly probable! Use larger addresses or reduce device count per network segment."}`

{
  const container = document.getElementById('kc-net-collision-birthday-1');
  if (container && typeof InlineKnowledgeCheck !== 'undefined') {
    container.innerHTML = '';
    container.appendChild(InlineKnowledgeCheck.create({
      question: "A smart building deploys 400 Zigbee sensors using 16-bit short addresses (65,536 possible addresses) assigned randomly by the coordinator. The network administrator notices intermittent communication failures. Based on the Birthday Problem, what is the approximate collision probability?",
      options: [
        {text: "Less than 1% - address space is large enough", correct: false, feedback: "With 400 devices in a 65,536 address space, the Birthday Problem formula gives P = 1 - e^(-(400^2)/(2x65536)) = 1 - e^(-1.22) = 70%. The quadratic relationship (n^2) makes collisions far more likely than linear intuition suggests."},
        {text: "About 10% - some collisions expected", correct: false, feedback: "The collision probability is much higher. The Birthday Problem shows that with n^2 in the numerator, 400 devices produces ~70% collision probability. At just 300 devices, you already have 50%+ collision probability."},
        {text: "About 70% - collisions are highly likely", correct: true, feedback: "Correct! Using P = 1 - e^(-(n^2)/(2m)) where n=400 and m=65,536: P = 1 - e^(-1.22) = 70%. This explains the intermittent failures. The 50% threshold for 16-bit addresses is only ~300 devices. Solution: use 64-bit extended addresses or split into multiple PANs."},
        {text: "100% - every device will collide", correct: false, feedback: "While 70% is high, it's not 100%. Some devices will have unique addresses. However, the collision rate is severe enough that many devices will experience address conflicts, causing the observed communication failures."}
      ],
      difficulty: "hard",
      topic: "Birthday Problem"
    }));
  }
}

630.9 Summary

• The Birthday Problem shows collision probability grows with n squared (quadratic), causing collisions far sooner than intuition suggests
• 23 people create 50% birthday collision probability - the same math applies to network addresses
• 16-bit addresses support ~250-300 devices before 50% collision probability
• 48-bit MAC addresses can have 18% collision probability with 10 billion devices
• The 50% threshold is approximately the square root of the address space

630.10 What’s Next

Continue to the Collision Design Strategies chapter to learn practical approaches for handling collisions in IoT network design, including Zigbee limitations, IPv6 addressing, and collision resolution strategies.