Name of phenomenon on estimated CDF plots of censored data

Question

My dataset contains two (rather strongly correlated) variables $t$ (runtime of algorithm) and $n$ (number of examined nodes, whatever). Both are strongly correlated by design, because the algorithm can manage roughly $c$ nodes per second.

The algorithm was run on several problems, but it was terminated if a solution hasn't been found after some timeout $T$. So data is right-censored on the time variable.

I plot the estimated cumulative density function (or the cumulated count) of variable $n$ for the cases where the algorithm did terminate with $t<T$. This shows how many problems could be solved by expanding at most $n$ nodes and is useful for comparing different configurations of the algorithm. But in the plot for $n$, there are those funny tails at the top going right sharply, as can be seen in the image below. Compare the ecdf for variable $t$, on which the censoring was done.

Cumulated Count of $n$

Cumulated Count of $t$

Simulation

I understand why this happens, and can reproduce the effect in a simulation using the following R code. It's caused by censoring on a strongly correlated variable under the addition of some noise.

qplot(
  Filter(function(x) (x + rnorm(1,0,1)[1]) < 5,
         runif(10000,0,10)),
  stat="ecdf",geom="step")

How is this phenomenon called? I need to state in a publication that these fans are artifacts of the experiment and do not reflect the real distribution.

Answer 1

I'm not an expert, but I believe what you're seeing is analogous to soft clipping.

Sort Clipping (Gain Compression)

It's a little different, because your clipping is caused by a non-deterministic process, in that your signal is clipped when it plus a random noise exceeds a threshold, instead of a device that deterministically reduces an analog signal. I have a guitar pedal that does this, it softens the "punch" of playing an electric guitar:

Keeyley Compressor Demo

Seems like a decent analogy. Im not sure if there is a name in the statistical community.

Answer 2

I suspect you run into the family of stable non-symmetric distributions.
First, plot your ecdf in a log-log plot. Adopt a parametric approach, assume Pareto Distribution,

The cdf in your case is translated as $F_t(t)=1-(\frac{t_{min}}{t})^a \ for \ t>t_{min}$, where $t_{min}$ is the minimum completion time of your algorithm, hence the threshold appearing on the left side of the ecdf graph
If you see a line in the log-log plot, then you are on the right path, make a linear regression on the log transformed data you have, to find out $\hat{\alpha}$, the so called Pareto index.

Pareto index must be greater than 1, it gives and interpretation of the heavy "tailness" of the distribution, how much data is spans on the edges. The closer to 1 the more pathogenic situation you have.
In other words, $\alpha$ expresses the ratio of nodes spent negligible time vs nodes spent excessive time before their completion. Previous reader pinpointed the fact you terminate abruptly your experiment, this introduces a complication described as $\hat{\alpha}=\hat{\alpha}(T)$. I suggest you should vary $T$ to explore this dependence.

Heavy tails phenomenon is common in computer science, particularly when nodes compete against shared resources in a random fashion, e.g. computer networks.

Answer 3

say that your distribution is truncated, like truncated normal