Anagrams contained within random strings What is the probability that a random string of length $n$ will contain an anagram of a shorter string of length $k$?
E.g., you generate a string of 50 random letters, repetitions allowed, what are the odds of it containing all of the letters H,E,L,L,O,W,O,R,L,D or indeed I,M,A,D,E,T,H,E,U,N,I,V,E,R,S,E ?
The best I can come up with is
$[1-(25/26)^n]\times[1-(25/26)^{n-1}]\times\dots\times[1-(25/26)^{n-(k-1)}]$
Obviously the order of the letters doesn't matter, so lets just take the first one from the anagram and say the probability the string doesn't contain that letter is $(25/26)^n,$ so the probability it does is $[1-(25/26)^n].$ Repeat for the second and subsequent letters from the anagram, except we now only have $n-1,\, n-2,\, \dots,\, n-(k-1)$ letters in the string etc.
Multiply probabilities and hey presto!
Unfortunately, my maths skills (ok, so in fact I am a musician!) end there and I have a sneaking feeling all kinds of things are wrong with this reasoning, although a few computer generated tests seem to give some general agreement.
Any thoughts appreciated!
 A: Your question probably does not have an easy answer. For one thing, with your given reasoning, you  are omitting at least one fact: Repeated characters in the query substring change the calculation. 
What you really want to calculate is if each character in your string is chosen randomly, then what are the chances that for each character $a$ appearing $k_a$ times in your query substring, that your randomly generated string will have at least $k_a$ occurrences of the character $a$. There are probably complex summation formulas or recursive formulas or other exotic forms for the answer in terms of combinatorial functions, but I believe nothing that can be nearly as easily calculated as your proposed formula.
A: Let the substring be made up of letters $a_1,\ldots,a_m$ with $a_i$ occuring $k_i$ times and $k_1+\cdots+k_m=k.$ You can think of a time varying Markov chain with state $(k_1,\ldots,k_m)$ starting at time $t=0$ and time being nonnegative integers, i.e., discrete. Now, let the random uniformly distributed letter sequence in the string of length $n$ be $Z_1,\ldots,Z_n.$
Let the chain start at state $X_0=(k_1,\ldots,k_m),$ i.e., no anagram letters have been observed yet. This state specifies that we still have to see $a_i$ of the letter $k_i$ to get to the anagram. And the state associated with the anagram, say state $(0,\ldots,0)$ will be an absorbing state.
If $X_1$ is one of the anagram letters, say letter $s$, (which happens with probability $1/M$ where $M$ is the alphabet size, then the state will change to $1$ (one of the anagram letters observed) and the new vector will be $(k_1,\ldots,k_s-1,\ldots,k_m)$. All links with "good" letters have probability $1/M.$ Once those are computed one minus their sum gives "bad" letters which lead to no change in the state.
Once the budget for a letter is spent, i.e., you've seen $k_i$ occurences for letter $i$, the state won't change if you see that letter $i$ again.
For small $n,k$ this can be explicitly computed by forming the time varying markov transition matrices $P_i$, for $i=1,2,\ldots,$ where the $i^th$ matrix will depend on what has so far appeared of the anagram letters, and will also depend on their sequence.
Thus, an explicit solution is doable but quite complex for $n,k,M$ of moderate size. A closed form of approximate probabilities may be possible.
