Exponents, logarithms and basic probability

1. 8-bit 1's-complement sum of 200 and 100 (decimal answer)?
   Stuck? Peek at 0.2.3 XOR, 1's complement addition and modulo-2 division

   • AND (mask), OR, NOT (flip), XOR (1 where bits differ).
   • a ⊕ a = 0, a ⊕ 0 = a, (a ⊕ k) ⊕ k = a.
   • 1's complement = flip all bits; 1's-complement addition wraps the end carry back in.
   • Modulo-2: + = − = XOR, no carries; bits ↔ polynomial.
   • Mod-2 division: leading 1 → XOR divisor; leading 0 → XOR zeros; remainder = (divisor length − 1) bits.

   Read lesson 0.2.3

2. Time to push 1 KB out at 1 kbps (default units)?
   Stuck? Peek at 0.2.1 Bits, bytes and prefixes: powers of 10 for rates, powers of 2 for sizes

   • 1 B = 8 b. Lower-case b = bit, upper-case B = byte.
   • Rates: k = 10³, M = 10⁶, G = 10⁹ (bps).
   • Sizes: K = 2¹⁰, M = 2²⁰, G = 2³⁰ (bytes) — unless the question says 1000.
   • Time to push out = (size in bits) ÷ (rate in bit/s).
   • ms = 10⁻³ s, µs = 10⁻⁶ s, ns = 10⁻⁹ s.

   Read lesson 0.2.1

3. What happens on a broadcast link when two nodes send at once?
   Stuck? Peek at 0.1.2 Nodes, links, topologies, LAN/WAN and the boxes in the middle

   • Node = any device; host = node where messages start/end.
   • Point-to-point (2 nodes) vs broadcast (all hear all).
   • Simplex (one way) · half-duplex (two ways, one at a time) · full-duplex (both at once).
   • Links: mesh n(n−1)/2, star n, ring n, tree n−1, bus 1 backbone.
   • LAN (building) ⊂ WAN (cities) ⊂ the Internet (network of networks).
   • Hub repeats to all · switch delivers within a LAN · router picks the next network.

   Read lesson 0.1.2

Picture a classroom where any student may speak whenever they like. Each one, independently, speaks in a given second with some small chance. The teacher hears something useful only if exactly one student speaks. How likely is that? Shared links in Phase 2 are exactly this classroom, and their best-case efficiency turns out to be a number involving e. Today we build the math.

10 students each speak in a given second with probability 0.1, independently. Guess the chance that exactly one speaks: about 10 %, about 39 %, or about 90 %?

About 39 % (0.387). Any one particular student speaks while the other nine stay quiet with probability 0.1 × 0.9⁹; there are 10 choices of who that student is, so 10 × 0.1 × 0.9⁹ ≈ 0.387. As the class grows (with probability 1/n each) this tends to 1/e ≈ 0.368.

Exponent rules

• 2ᵃ × 2ᵇ = 2ᵃ⁺ᵇ; 2ᵃ / 2ᵇ = 2ᵃ⁻ᵇ; (2ᵃ)ᵇ = 2ᵃᵇ; 2⁰ = 1; 2⁻ᵃ = 1/2ᵃ.
• Useful: 2¹⁰ ≈ 10³, so 2²⁰ ≈ 10⁶ and 2³⁰ ≈ 10⁹ (for estimates only).

Logarithm base 2

log₂ answers "how many bits?" and "how many doublings?". When x is not a power of 2 we round: ⌈x⌉ (ceiling) rounds up, ⌊x⌋ (floor) rounds down. Bits needed for N values = ⌈log₂ N⌉. Rules: log₂(ab) = log₂ a + log₂ b; log₂(aᵏ) = k log₂ a.

Probability basics

• A probability is a number from 0 (never) to 1 (always).
• Complement: P(not A) = 1 − P(A).
• Independent events (one does not affect the other): P(A and B) = P(A) × P(B).
• Mutually exclusive cases add: P(A or B) = P(A) + P(B) when they cannot both happen.

n independent senders

n stations, each sends in a slot with probability p, independently:

• P(none sends) = (1 − p)ⁿ
• P(at least one) = 1 − (1 − p)ⁿ
• P(exactly one) = n · p · (1 − p)ⁿ⁻¹ (n choices of who, that one sends, the other n − 1 stay quiet)

The number e and the 1/e limit

e ≈ 2.71828. Two facts matter for networks:

• (1 − 1/n)ⁿ → 1/e ≈ 0.368 as n grows. (n = 10: 0.349; n = 100: 0.366.)
• The best chance of "exactly one of n" is when p = 1/n, and it also tends to 1/e. Phase 2 meets two numbers built from e as best-case efficiencies of random sharing: 1/e ≈ 0.368 and 1/(2e) ≈ 0.184.

Geometric series and expected value

• 1 + 2 + 4 + … + 2ᵏ⁻¹ = 2ᵏ − 1.
• 1 + r + r² + … + rⁿ⁻¹ = (1 − rⁿ)/(1 − r); for 0 ≤ r < 1 the infinite sum is 1/(1 − r).
• Expected value = Σ (value × probability). If each try succeeds with probability p, the expected number of tries until the first success is 1/p.

Putting it together

• log₂ counts bits and doublings; round up with ⌈ ⌉ for "how many bits".
• For n independent senders: none (1−p)ⁿ, exactly one n·p·(1−p)ⁿ⁻¹, at least one 1 − (1−p)ⁿ.
• e appears as the limit 1/e ≈ 0.368 — the ceiling on random sharing efficiency in Phase 2.

• "At least one" is 1 − P(none), not n·p (n·p can exceed 1).
• Exactly one of n needs the factor n — any of the n stations can be the lucky one.
• ⌈log₂ N⌉ gives the bits for N values; 0..N is N + 1 values.

"One talks, the rest are quiet, any one of n": n · p · (1 − p)ⁿ⁻¹.

Phase 0's toolkit is complete: units (0.2.1), binary and hex (0.2.2), bit operations (0.2.3), logs and probability (0.2.4). Next (Phase 1): sending one message involves many separate jobs — encoding, addressing, choosing paths, checking. How do engineers split such a big job so that each part can be built and changed independently?

1. NAT

   ⌈log₂ 3000⌉ = ?

   Write your answer before opening the key.

2. NAT

   4 stations each send with probability 0.25. P(exactly one sends)? (4 decimals)

   Write your answer before opening the key.

3. MCQ

   As n grows, (1 − 1/n)ⁿ approaches:

   1. 0
   2. 1/e ≈ 0.368
   3. 1/2
   4. e ≈ 2.718
4. MSQ

   For n independent stations with probability p each, which are correct?

   1. P(none) = (1 − p)ⁿ
   2. P(at least one) = n·p
   3. P(exactly one) = n·p·(1 − p)ⁿ⁻¹
   4. P(at least one) = 1 − (1 − p)ⁿ
5. NAT

   Each attempt succeeds with probability 0.2. Expected number of attempts until the first success?

   Write your answer before opening the key.

• 2ᵃ·2ᵇ = 2ᵃ⁺ᵇ; 2¹⁰ ≈ 10³ (estimates only).
• log₂ x = power of 2 giving x; bits for N values = ⌈log₂ N⌉.
• P(none) = (1−p)ⁿ · P(≥ 1) = 1 − (1−p)ⁿ · P(exactly 1) = n·p·(1−p)ⁿ⁻¹.
• (1 − 1/n)ⁿ → 1/e ≈ 0.368; 1/(2e) ≈ 0.184.
• 1 + 2 + … + 2ᵏ⁻¹ = 2ᵏ − 1; expected tries = 1/p.

• exponent rules
• log₂
• ceiling ⌈ ⌉ / floor ⌊ ⌋
• probability, complement
• independent events
• (1 − p)ⁿ, n·p·(1 − p)ⁿ⁻¹
• e, 1/e limit
• geometric series
• expected value, 1/p

1. P(exactly one of n sends)?
   Reveal answer

   n·p·(1 − p)ⁿ⁻¹.
2. (1 − 1/n)ⁿ for large n?
   Reveal answer

   ≈ 1/e ≈ 0.368.
3. 1 + 2 + 4 + … + 2ᵏ⁻¹?
   Reveal answer

   2ᵏ − 1.
4. Expected tries with success probability p?
   Reveal answer

   1/p.
5. Bits for N values?
   Reveal answer

   ⌈log₂ N⌉.

• Exactly one of n = n·p·(1−p)ⁿ⁻¹; maximised at p = 1/n; → 1/e for large n. — n identical, independent senders, each with the same p.
• 1/e ≈ 0.368, 1/(2e) ≈ 0.184. — whenever a maximum efficiency of a random sharing scheme is asked (Phase 2).