I usually use randomization in algorithms so I am familiar with basics of probability but nothing much advanced. I have gone through the derivation for Birthday Paradox (Cormen et al) and decided to do the same thing in a slightly different way.
(Lets talk in terms of balls and bins. Let there be m balls and n bins). Let E_ij be the event that two balls i and j end up in same bin. Clearly, $ Pr(E_{ij}) = \frac{1}{n} $.
I claim: probability that there exists at least 2 balls which end up in same bin <= $\sum Pr(E_{ij})$; by union bound. Firstly, is this claim correct? I guess it is not since I don't get the same answer by this formulation. Just for the sake of completeness, $\sum Pr(E_{ij}) = {m \choose 2} * \frac{1}{n}$
I want to get my understanding right and thats why I want to know why this is wrong. I am almost sure that I am messing this up in some very fundamental concept. I am just not able to find which one!
What you are counting with $\sum_{1\leq i < j \leq m} \Pr[E_{i,j}]$ is the expected number of collisions, i.e. the expectation of $X$, defined as the number of (pairs of balls that fall in the same bin). What you want is the probability to have at least one of these pairs: an loose upperbound is indeed be given by Markov's Inequality, which states that $$\Pr[X \geq 1] \leq \frac{\mathbb{E}[X]}{1}$$ (since $X$ is a non-negative r.v.).
But what do you mean by "I don't get the same answer by this formulation"? (depending on what you mean, it may come from the fact that Markov's inquality is usually not tight, and so the analysis does not result in the optimal conclusion).