Probabilistic proof: why are we allowed to work with an "arbitrary" probability?

Question

Let $G = (V,E)$ be a graph with $n$ vertices and $e$ edges. Then $G$ contains a bipartite subgraph with at least $e/2$ edges.

The proofs starts like this:

Let $T \subset V$ be a random subset given by $Pr[x \in T] = 1/2$, these choices mutually independent.

I know that this is often the structure of probabilistic proofs, but I wonder why we are allowed to assume that $Pr[x \in T] = 1/2$ respectively why did the author think that $1/2$ would be a decent probability to work with.

Answer 1

If you choose probability $p$, the expected number of edges of your bipartite graph comes out at $2p(1-p)e(G)$. You want as many edges as possible, so the best choice of $p$ is whatever maximises $p(1-p)$, which is easy to see is $p=1/2$. Often probabilistic proofs are first written with a general $p$, then at the end you work out which $p$ is best and rewrite the proof with that value.

For this case, heuristically, you would expect $1/2$ to be best. This is because you define your bipartite graph by randomly putting vertices to the right or to the left. But swapping the roles of right and left gives you exactly the same subgraph, so there is a symmetry between right and left. That suggests you want to treat them the same, i.e. $p=1-p$.

Answer 2

This probabilistic proof is equivalent to a combinatorial proof taking all $2^n$ subsets of $V$ into account. Bringing in probability in such a context has nothing to do with fate or luck, it is just a handy way of replacing the large numbers arising from counting by probabilities.