Question
You receive a hardware source `raw_bit()` that independently returns `0` or `1` with one stable but unknown probability of returning `1`. The probability is strictly between zero and one, and no other random source is available. Implement the following four functions. ```python def extract_bit(raw_bit) -> int: ... def choose_slot(slot_count, balanced_bit) -> int: ... def estimate_load(slot_count, trials, raw_bit) -> float: ... def estimate_load_parallel(slot_count, trials, source_factory, workers) -> float: ... ``` ## Requirements ### 1. Extract balanced bits Read the raw source in fresh pairs. Discard pairs whose values match. For the first pair whose values differ, return its first value. A scripted source raises `EOFError` when exhausted; let that exception propagate, including for a partial pair. Explain why the returned values are balanced despite the unknown source bias and why the loop terminates with probability one. ### 2. Select a slot without modulo bias - `slot_count` must be a positive integer or the function raises `ValueError`. - Use only `balanced_bit()`. - A one-slot choice consumes no bits. - Draw an integer from the smallest power-of-two range that covers all slots. Reject values outside `range(slot_count)` and try again. Identify the smallest slot count for which simple modulo folding is biased, and explain why powers of two conceal that defect. ### 3. Estimate synthetic load Each trial must first obtain a balanced enable bit, then choose a zero-based slot. Return `slot + 1` when the enable bit is `1`; otherwise return `0`. Always choose the slot so scripted runs consume events in a fixed order. Run `trials` trials and return their arithmetic mean. A zero-trial run returns `0.0` without reading the source. Invalid `slot_count` or `trials` raises `ValueError`. The exact expectation is `(slot_count + 1) / 4`; the implementation must estimate it by sampling rather than returning the formula. ### 4. Run independent batches concurrently Each worker calls `source_factory(worker_index)` exactly once and owns that private event source. Never share a stateful source between workers. For a non-empty run, use `worker_count = min(workers, trials)`. Divide work so the first `trials % worker_count` workers receive one additional trial. Combine integer partial sums and divide once at the end. If `trials == 0`, return `0.0` without calling the factory. Invalid `workers` raises `ValueError`. Discuss when Python threads improve wall-clock time and when the GIL makes a process pool, native implementation, or vectorized computation more appropriate.