Concept icon
Concept

Computing conditional expectations without enumerating every schedule assignment

Each collision indicator depends on at most four independent schedule choices: a_v,d_f,a_v_prime,d_f_prime. Repeated indices mean one shared choice. After partial fixing, enumerate at most K^4=D^2 equally likely settings for its remaining choices. A variable-group indicator needs at most two schedules. Sum the M^2+Q*n^2 probabilities, subtract the fixed constants, and normalize. Each probability has denominator dividing K^4, so K^4*M*(b+w)*Q*n is a common denominator for the potential. Numerators and denominators need O(log(2D)+log(2M)+log(2n)+log(2Q)+log(2+b+w)) bits. There are at most n+number-of-factors schedules to fix and K candidates per step. This is polynomial in the listed parameters, including D; it is polynomial in n only after D and the other parameters are bounded appropriately.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math