It is often in the random graph theory proofs that we are looking at the expectation. But why? Why is it not the probability that we studying.
To clarify my question, look at the following example. Assume we are working in the $G(n,p)$ model. What is the probability that we have an induced cycle with t edges in $G(n,p)$ ? My approach would be.
Fix $t$ vertices. The probability of having induced cycle on these $t$ vertices is $p^t(1-p)^{\binom{n}{2}-t}$.
Now consider all possible $\binom{n}{t}$ subsets of $t$ vertices. Probability of having an induced cycle in a graph is equal to probability that at least one of these $t$-subsets of vertices has an induced cycle, which is the sum of the probabilities over all $t$-sets to have an induced cycle which is:
$$\text{Probability of having an induced cycle in G(n,p)}= \binom{n}{t} p^t(1-p)^{\binom{n}{2}-t}$$
Suppose, I choose $N=N(p)$ such that this quantity is $<1$. Then MY QUESTION IS: can I conclude that there exists a graph on $N$ vertices having no induced cycle, because the probability above is <1?
Why do people even consider expectation? I know that it is possible to define indicator random variables for each $t$-set and then calculate the expected number of induced cycles. Provided that this expected number is $<1$, we can say that there will be a graph on $N$ vertices with no induced cycle.
TL;DR Why just considering a probability alone would not be enough? Why do we even need expectation?
Many thanks!
Well, first of all: the probability of $G(n,p)$ having an induced $t$-vertex cycle is not $$\binom nt p^t (1-p)^{\binom n2 - t}.$$ That's (aside from an error) the probability of $G(n,p)$ being a $t$-vertex cycle with $n-t$ isolated vertices, because you've included a $(1-p)^{\binom n2 - t}$ factor saying that $G(n,p)$ has no other edges whatsoever. Usually, this probability is not what we want.
(The error is that once you've chosen the $t$ vertices of the cycle in $\binom nt$ ways, there are $\frac{(t-1)!}{2}$ ways to arrange them into a cycle, so $\binom nt$ should be replaced by $\frac{(t-1)!}{2}\binom nt = \frac{(n)_t}{2t}$.)
There's no easy formula for the probability that $G(n,p)$ contains an induced $t$-vertex cycle.
Once we pick a specific cycle $v_1, v_2, \dots, v_t$ in the complete graph $K_n$, the probability that it will be an induced cycle in $G(n,p)$ is $p^t (1-p)^{\binom t2 - t}$: the probability that all $t$ edges $v_1 v_2, v_2 v_3, \dots, v_{t-1} v_t, v_t v_1$ are present, and all other edges $v_i v_j$ are absent.
However, there are $\frac{(n)_t}{2t}$ such events, for the $\frac{(n)_t}{2t}$ different cycles in $K_n$, and we can't just add their probabilities, because these events are not all disjoint. Multiple induced cycles can appear in $G(n,p)$ at once. Some of these events are disjoint: for instance, the events for two different cycles on the same vertex set. Other pairs of these events are independent: that happens if there is at most one vertex in common between the cycles. Other pairs (such as cycles that share some of their edges) have a more complicated relationship.
So, it's not clear how to combine these probabilities into the probability that $G(n,p)$ has an induced $t$-vertex cycle. Even if a formula exists, it is probably awful and hard to work with.
We use expectation because it is easy to work with. Linearity of expectation, applied to indicator variables, tells us that $$ \frac{(n)_t}{2t}p^t (1-p)^{\binom t2 - t}$$ is definitely the expected number of induced $t$-vertex cycles, even though these events are not independent or disjoint. (Linearity of expectation works for any sum of random variables!) Sure, probability would be more useful - but the probability is hard to find, and the expectation is easy to find.
We have the relationship $\Pr[\mathbf X \ge 1] \le \mathbb E[\mathbf X]$ for any nonnegative random variable $\mathbf X$; in particular, this holds when $\mathbf X$ is the number of cycles. This tells us that even though we took the easy way out, and computed the expectation instead of the probability, we have still learned something. We have found an upper bound on the (unknown, unknown, unknown!) probability.
This can be used to prove that this probability is less than $1$, if the expectation is less than $1$, for example.