Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Randomized Experiments01:13

Randomized Experiments

7.9K
The randomization process involves assigning study participants randomly to experimental or control groups based on their probability of being equally assigned. Randomization is meant to eliminate selection bias and balance known and unknown confounding factors so that the control group is similar to the treatment group as much as possible. A computer program and a random number generator can be used to assign participants to groups in a way that minimizes bias.
Simple randomization
Simple...
7.9K
Propagation of Uncertainty from Random Error00:59

Propagation of Uncertainty from Random Error

1.1K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
1.1K
Random Variables01:09

Random Variables

13.5K
A random variable is a single numerical value that indicates the outcome of a procedure. The concept of random variables is fundamental to the probability theory and was introduced by a Russian mathematician, Pafnuty Chebyshev, in the mid-nineteenth century.
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
13.5K
Random Sampling Method01:09

Random Sampling Method

12.6K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
12.6K
Wald-Wolfowitz Runs Test I01:17

Wald-Wolfowitz Runs Test I

749
The Wald-Wolfowitz test, also known as the runs test, is a nonparametric statistical test used to assess the randomness of a sequence of two different types of elements (e.g., positive/negative values, successes/failures). It examines whether the order of the elements in a sequence is random or if there is a pattern or trend present. This nonparametric test applies to any ordered data despite the population and sample data distribution, even if a higher sample size is available.
The test works...
749
Wald-Wolfowitz Runs Test II01:17

Wald-Wolfowitz Runs Test II

331
The Wald-Wolfowitz runs test, commonly referred to as the runs test, is a nonparametric test used to assess the randomness of ordered data. The test evaluates the number of runs, which are consecutive sequences of similar elements within the data. If the number of runs is significantly higher or lower than expected, the data is considered non-random, indicating a detectable pattern or structure.
For binary data, runs are identified using symbols such as + and −, or equivalently, 1s and...
331

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Sep 24, 2025

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
05:30

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Published on: September 8, 2023

672

Randomized Online Computation with High Probability Guarantees.

Dennis Komm1, Rastislav Královič2, Richard Královič1

  • 1Department of Computer Science, ETH Zurich, Zurich, Switzerland.

Algorithmica
|May 10, 2022
PubMed
Summary
This summary is machine-generated.

Researchers explored randomized online algorithms, finding that a constant expected competitive ratio implies a high-probability competitive ratio for many problems. This applies to paging, k-server, and metrical task systems.

Keywords:
Bounds with high probabilityOnline algorithmsRandomization

More Related Videos

The Collective Trust Game: An Online Group Adaptation of the Trust Game Based on the HoneyComb Paradigm
06:18

The Collective Trust Game: An Online Group Adaptation of the Trust Game Based on the HoneyComb Paradigm

Published on: October 20, 2022

2.2K
Closed-loop Neuro-robotic Experiments to Test Computational Properties of Neuronal Networks
11:18

Closed-loop Neuro-robotic Experiments to Test Computational Properties of Neuronal Networks

Published on: March 2, 2015

10.5K

Related Experiment Videos

Last Updated: Sep 24, 2025

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
05:30

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Published on: September 8, 2023

672
The Collective Trust Game: An Online Group Adaptation of the Trust Game Based on the HoneyComb Paradigm
06:18

The Collective Trust Game: An Online Group Adaptation of the Trust Game Based on the HoneyComb Paradigm

Published on: October 20, 2022

2.2K
Closed-loop Neuro-robotic Experiments to Test Computational Properties of Neuronal Networks
11:18

Closed-loop Neuro-robotic Experiments to Test Computational Properties of Neuronal Networks

Published on: March 2, 2015

10.5K

Area of Science:

  • Computer Science
  • Algorithm Analysis
  • Online Algorithms

Background:

  • Online algorithms make decisions without future knowledge.
  • Competitive ratio measures algorithm performance against an optimal offline algorithm.
  • Randomized algorithms introduce probability to improve performance bounds.

Purpose of the Study:

  • Investigate the link between competitive ratio and tail distributions in randomized online problems.
  • Identify a class of problems where constant expected competitive ratio guarantees a high-probability competitive ratio.

Main Methods:

  • Theoretical analysis of randomized online algorithms.
  • Characterization of problem classes based on competitive ratio properties.
  • Examination of tail distribution implications for algorithm performance.

Main Results:

  • A broad class of online problems identified where constant expected competitive ratio implies a high-probability competitive ratio.
  • This relationship holds for problems measured against optimal profit or cost.
  • Includes well-known problems like paging, k-server, and metrical task systems.

Conclusions:

  • The study establishes a significant theoretical connection between different performance measures in randomized online algorithms.
  • Findings offer a deeper understanding of algorithm behavior and bounds for critical online problems.