Implementation of a sparse Markov Chain
If you're using ContainsKey, you're probably doing it wrong and you need to use Dictionary&lt;TKey, TValue&gt;.TryGetValue Method (TKey, TValue).

Your first method would then become:

public double GetTransition(T p1, T p2)
{
    Dictionary&lt;T, int&gt; p1Value;
    if (!_sparseMarkovChain.TryGetValue(p1, out p1Value))
    {
        return 1f/_size;
    }

    int p2Value;
    if (p1Value.TryGetValue(p2, out p2Value))
    {
        return (1f + p2Value)/(_countEltLeaving[p1] + _size);
    }

    return 1f/(_countEltLeaving[p1] + _size);
}




Your naming could be improved. The "MC" in _sparseMC makes sense in context, but why not write "MarkovChain" in full? p1 and p2 aren't clear to me, but I don't know the convention.



These three lines could be a single one:

Dictionary&lt;T, int&gt; nd = new Dictionary&lt;T, int&gt;();
nd.Add(p2, 1);
_sparseMC.Add(p1, nd);


versus:

_sparseMC.Add(p1, new Dictionary&lt;T, int&gt;{{ p2, 1 }});




Use braces everywhere to avoid introducing bugs, even for code like this:

if (_sparseMC[p1].ContainsKey(p2))
{
    _sparseMC[p1][p2] += 1;
}
else
{
    _sparseMC[p1].Add(p2, 1);
}




_sparseMC and _countEltLeaving can be made readonly.