As a further comment (but slightly longer than an actual comment) on the accepted answer:

1. Kolmogorov Complexity (or Algorithmic Complexity) deals with optimal descriptions of "strings" (in the general sense of strings as sequences of symbols)

2. A string is (sufficiently) incompressible or (sufficiently) algorithmicaly random if its (algorithmic) description (kolmogorov comlplexity $K$) is not less than its (literal) size.

3. Major result of the theory is that most strings are (algorithmicaly) random (or typical) (which is also related to other areas like Goedel's Theorems, through Chaitin's work)

4. Kolmogorov Complexity is related to Probabilistic (or Shannon) Entropy, in fact Entropy is an upper bound on KC. And this relates analysis based on descriptive complexity to probabilistic-based analysis. They can be inter-changeable.

5. Sometimes it might be easier to use probabilisrtic analysis, others descriptive complexity (views of the same lets say)

So in the light of the above, assuming an algorithmicaly random input to an algorithm, one asumes the following:

1. The input is typical, thus the analysis describes average-case scenario (point 3 above)
2. The input size is related in certain way to its probability (point 2 above)
3. One can pass from algorithmic view to probabilistic view (point 4 above)

As a further comment (but slightly longer than an actual comment) on the accepted answer:

1. Kolmogorov Complexity (or Algorithmic Complexity) deals with optimal descriptions of "strings" (in the general sense of strings as sequences of symbols)

2. A string is (sufficiently) incompressible or (sufficiently) algorithmicaly random if its (algorithmic) description (kolmogorov comlplexity K) is not less than its (literal) size. In other words the optimal description of the string, is the string itself.

3. Major result of the theory is that most strings are (algorithmicaly) random (or typical) (which is also related to other areas like Goedel's Theorems, through Chaitin's work)

4. Kolmogorov Complexity is related to Probabilistic (or Shannon) Entropy, in fact Entropy is an upper bound on KC. And this relates analysis based on descriptive complexity to probabilistic-based analysis. They can be inter-changeable.

5. Sometimes it might be easier to use probabilisrtic analysis, others descriptive complexity (views of the same lets say)

So in the light of the above, assuming an algorithmicaly random input to an algorithm, one asumes the following:

1. The input is typical, thus the analysis describes average-case scenario (point 3 above)
2. The input size is related in certain way to its probability (point 2 above)
3. One can pass from algorithmic view to probabilistic view (point 4 above)