Biased graph generating processes

Question

Given a random process (algorithm) that is supposed to generate with equal probability graphs from a given class $\Gamma$. Assume the process is not obviously biased, i.e. generating graphs unevenly (giving for example some graph properties a stronger weight).

How can it be checked or proved that the algorithm doesn't generate a finite amount of graphs with some property which in fact almost never occurs in $\Gamma$?

A related question is this one.

Answer 1

The method(s) will very much depend on the problem at hand, let me share few articles to make the point clear:

1. Finding Hidden Cliques in Linear Time with High Probability (DEKEL , GUREL-GUREVICH and PERES).

Here they proposed an algorithm to find a planted clique and showed that it works with a probability bounded below by a constant.

2. Limits of local algorithms over sparse random graphs by GAMARNIK AND SUDAN.

Here they proved that certain algorithms will not succeed to find the largest independent set in sparse random graphs with high probability.