AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_phase_length

def

The duration of phase k of the probabilistic serial procedure (k = 0, 1, ...): the total remaining item capacity before the phase minus the total after it, divided by n. While some item is left every one of the n agents eats at unit speed, so this is the length of the phase; it is 0 once every item is used up.

Statement

noncomputable def probabilistic_serial_phase_length (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
    (k : ℕ) : ℝ
Source
Helper for the item-waiting-time reduction of OP-1158 (probabilistic serial on the line, PS <= n*OPT); reduction found 2026-11-07 for IN-608, experiments 17916, 17917
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • probabilistic_serial_phase_stateThe state of the probabilistic serial (simultaneous eating) procedure for n agents and n unit-capacity items with rankings pref after its…
Used by 3

Lean source view module on GitHub

noncomputable def probabilistic_serial_phase_length (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
    (k : ℕ) : ℝ :=
  ((∑ j, (probabilistic_serial_phase_state n pref k).1 j) -
      ∑ j, (probabilistic_serial_phase_state n pref (k + 1)).1 j) / n
See it in the graphDiscuss this resultChallenge it