Monotonicity Property Testing

• Monotonicity is an array that is sorted.
• Since I don’t read everything, the answer is probably XX.
• Definition of ε-farness in this case:
  • ε: a constant threshold $0<\epsilon <100\%$
  • If we don’t rewrite ε times n or more elements, it doesn’t seem to be monotonic = ε-far.
  • Determine if it is monotonic or ε-far (not monotonic at all) with high probability.
• It can be calculated that just comparing two elements repeatedly at random does not yield results with high probability (confidence).
• Therefore, we apply binary search.
  • Originally, binary search doesn’t work if it’s not sorted.
  • By performing binary search 2ε^{-1} times and verifying if we reach the answer, we can check for monotonicity! #Property testing (Expert in computer science)