MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Update: To write a quick preamble, this question is basically asking that, if you take all possible pairs of some set of characters, call these pairs elements of the set $S$, and if you throw out some of the elements in $S$ with uniform probability, what the probability distribution is for the longest chain of elements you can construct, drawing from this pruned set, s.t. each element has exactly one character in common with both the previous element in the permutation and the next element in the permutation (noting that all elements/pairs must be distinct).
Imagine I have a set, $(s_1, ..., s_{(N^2)}) \in S$, of all possible ordered pairs of identical or non-identical integers over the domain $s_i \in [1, N]$. For example, if $N = 2$, we would have the set: $S =$ {{1,1},{1,2},{2,1},{2,2}}, where $||S|| = 2^2 = 4$.