What is "first step conditioning"? In some probability exercises I can red the term "first step conditioning" but I was not able to find any explication on the internet about it. What is it?
 A: "Conditioning on the first step" is a clever trick taking advantage of "time symmetry" in "time invariant" random process problems.
Wow, that sounds confusing. Let me explain.
When the transition probabilities between states in a random process (random walk) do not change after taking new steps, there is a nice "similarity" or "symmetry" that is sometimes useful for calculating quantities of interest. Quantities like "what is the probability of ever ..." or "what is the expected number of steps before ever...". 
"First step conditioning" conquers the main challenge with calculating these quantities: the word "ever" allows for an infinite number of steps.
How the heck does one calculate some quantity involving potentially an infinite number of random steps?
Symmetry is how. Symmetry is extremely helpful for problem-solving in general, since it means something stays the same.
When a symmetry can be found between the starting situation and the situation after taking one step, this symmetry can be expected to hold for the second step, the third step, and so on, allowing us to say something about what happens after an infinite number of steps.
Consider some quantity $Q$ that asks about something ever happening, and depends on the starting state $s_0$: $Q(s_0)$. For instance, "starting from $s_0$, what is the expected number of steps $Q$ before you ever get to the goal $s_{goal}$?".
The clever trick is that you see how $Q$ changes if you take one random step, which will put you in new states with certain probabilities. From each new state $s_i$, $Q(s_i)$ is still asking the same question of something "ever" happening.
Thus taking this first step (using math) will provide a relationship between the values of $Q(s_0)$ before the first step, $Q(s_0)$,$Q(s_1)$,$Q(s_2)$, ... after the first step, and the transition probabilities to get between $s_0$, $s_1$, $s_2$....
For this "first step relationship" to hold, you can often figure out what $Q$ must be for all the states, which solves the problem.
The key symmetry exploited is that $Q$ is a quantity that only depends on the state, but not on time.
