Jep, and your strategy gets worse, while another strategy may stay average.

Assume you flip a coin. heads or tails.

You NP-complete algorithm knows the sequence.

The probalistic one just guesses "heads".

Now the Expectation value of both are Zero in the stochastic case. In the deterministic one its infinite win for the np-complete one and zero for the probalistic one.

So this is an example, where a perfect algorithm for deterministic data is just as good as another for stochastic data.

This does not mean, you cannot get better than the deterministic-optimal algorithm. As the data is random, the deterministic-optimal algorithm becomes "just another algorithm" and you will need to proof again its better than the other candidates. It may be, maybe even provable the still the optimal one, but the fact that its det-optimal does not imply that its prob-optimal.

A real world example: Las Vegas Quicksort.

Quicksort is O(n log n), choosing log n times a median element, then sorting in n the elements on both sides to the correct side.

calculating the median element is O(n), with some constant C.

Choosing the median element randomly is O(1).

Now you can show, that the propability of a "not too bad" element is so, that the log n * C factor is slower in most cases than the slowdown of the algorithm by choosing a non-optimal "median".