Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have an alphabet with countably many letters. Every letter has a particular weight (for instance, as in the game of Scrabble). There are a total of $n^2$ letters that have weight $n$.

Given any word in this alphabet, let the weight of that word be the sum of the weights of its letters (again, as in Scrabble). It follows that there are roughly exponentially many words of weight $W$.

I am sampling words of weight $W$, uniformly at random. My somewhat vague question is: what does a ``generic'' word look like, for large $W$? This can be made precise in a few ways:

  1. What is the expected value of the number of letters comprising a word of weight $W$? How many of these letters are expected to be distinct?

  2. Does a generic word of weight $W$ have a letter that appears only once?

  3. What is the expectation for the number of letters that appear only once in the word?

This is quite far from my field of expertise, so even simple pointers to references are much appreciated.

share|improve this question
    
---There are a total of $n^2$ letters that have weight n.--- Identical letters like in scramble? –  fedja Nov 27 '12 at 1:17
    
Nope - all the letters in the alphabet are distinct. But we are allowed to use each one many times. I'm thinking of them as, eg, generators of a group (except we're not simplifying the word at all). –  Dave Futer Nov 27 '12 at 1:49
add comment

2 Answers

up vote 6 down vote accepted

Here is a back of envelope computation. There will be no rigor whatsoever, just a cookbook approach that may be acceptable to a physicist but which every self-respecting mathematician should frown upon. It can give a plausible (but not guaranteed) answer to some of your questions if we just want the general order of magnitude without too high precision but if you want more than that, we'll need to count in honest.

If what I write below looks like gibberish, it's OK. As I said, I just did the calculus, not the actual analysis. If your model corresponds to some physical reality and you know the values of some constants involved, it will be funny to compare them with what follows from my predictions. If you want more, like the distribution laws for the number of occurences of individual letters (or, God forbid, joint distribution for several letters), you need to consult a true expert, not an amateur like myself. In any case, have fun reading and feel free to ask questions. Also watch for idiotic mistakes in algebra: it is quite late here now... :-)

The main local generating function for counting words of weight $W$ assuming typical length about $L$ and decent length concentration (the point is to kill factorials in the denominator; we will still be be off by the factor $e^L$, but we need a typical structure, not the counts).

$F(z,w)=\exp(Lz(w+4w^2+9w^3+16w^4+\dots))=\exp\left(Lz\frac{w+w^2}{(1-w)^3}\right)$

Everything is nice and positive, so the mountain pass in the circle method is a sure bet. We need to find the controlling radius $r$ for the weight $W$, so, for $z=1$, we need to minimize $Lz\frac{r+r^2}{(1-r)^3}-W\log r$. Alas, we are certain to end up with $r$ noticeably less than $1$, so we have to differentiate in honest: $$ r\frac{4+r-2r^2}{(1-r)^4}=\frac WL $$ We also need the consistency equation, which says that we, indeed, get $L$ as a typical length with $z=1$, i.e., $\frac\partial{\partial z}(Lz\frac{r+r^2}{(1-r)^3}-L\log z)|_{z=1}=0$, i.e., $r+r^2=(1-r)^3$ so $r=0.284774761\dots$ and $W/L=4.486414\dots$.

This is a bit counterintuitive because it predicts, in particular, that the typical word consists mainly of the letters of low weights and the option to diversify, which should lead to more possibilities, is really pretty useless. Let's run the sanity check. Suppose that we are looking at words using a few low weight letters. Then they are just $A^W$ with some fixed $A>1$. Let us add a letter of weight $n$ in proportion $p$. We get the new number about $A^{(1-pn)W}\left(\frac ep\right)^{pW}$, so to get the largest count, we have to solve $Cn=-\log p$ whence the portion of letters of length $n$ is decaying exponentially in $n$. Thus, the cost of diversification is prohibitively high here and the answer we got makes sense.

Now, how many different letters typically? The generating function to consider now is $$ G(s)=\prod_{k\ge 1}[1+s(e^{Lr^k}-1)]^{k^2}\\,. $$ The typical number $D$ of distinct letters would correspond to the zero derivative of $\log G(s)-D\log s$ with respect to $s$ at $1$. Thus, we expect something like $$ \sum_k k^2(1-e^{-Lr^k})\approx\int_0^\infty t^2(1-e^{-Le^{-\rho t}})\\,dt $$ where $\rho=-\log r$. The second factor is just a sharp cutoff at $t=\frac{\log L}{\rho}\approx\frac{\log W}{\rho}$, so, let's say $$ D\approx \frac 1{3\rho^{3}}\log^3 W= 0.168209\log^3 W. $$

What's next? Ah, the typical number $U$ of letters appearing once! Now we need to place $s$ only on one term in the exponent, so we go to $$ H(s)=\prod_{k\ge 1}[e^{Lr^k}-Lr^k(1-s)]^{k^2}\\,. $$ Same routine with setting the derivative of $\log H(s)-U\log s$ to $0$, we get $$ H\approx\sum_k k^2 Lr^k e^{-Lr^k}\\,. $$ This one is harder because we run through the bump very quickly, i.e., in constant time. It also suggests an "oscillating asymptotics", i.e., that the arithmetic nature of $W$ introduces an effect that does not decay with size. However, we can still play our usual game around $\log L/\rho$ and get the quasi-asymptotics $$ 0.7927\log^2 W \le U\le 0.7996 \log^2 W\\,. $$ Alas, as I said, the quasi-asymptotics is, probably, all we can hope for here.

share|improve this answer
    
Have you read "Generatingfunctionology"? If not, start with that. The free online text can be found at math.upenn.edu/~wilf/DownldGF.html. If yes, I'll assume that you know the basics and add an explanation starting from there. –  fedja Nov 27 '12 at 14:35
    
Thank you, Fedja! As I'm quite ignorant of this area of math, it's somewhat opaque to me why these particular generating functions arise. Perhaps you can point me to a reference that explains the "cookbook" for this type of counting question? –  Dave Futer Nov 27 '12 at 14:36
    
Also, one phrase that I cannot parse at all is "the mountain pass in the circle method". Thanks for answering my stupid questions! –  Dave Futer Nov 27 '12 at 14:38
    
Thank you -- please do add an explanation assuming the basics. I will try to backfill the basics as needed. –  Dave Futer Nov 27 '12 at 14:43
    
They aren't stupid! You just don't understand something because you've not seen it before and because I'm prone to using slang occasionally. Genuine stupidity looks very different and usually manifests itself in the original post in its full and unsurpassed beauty ;-). I have to go lecturing now, but I'll come back in an hour and try to elaborate a bit on the things you asked about. :-) –  fedja Nov 27 '12 at 14:52
show 3 more comments

Sorry for the long silence. Believe it or not, it was impossible to find even 10 minutes until now, not a full hour I need to explain everything in a decent way. Even now I'm starting but I'm not at all sure I'll finish. I'll try to do it in as few shots as possible but I apologize in advance if I will need to bump this thread a few times.

Part 1. Generating functions and counters.

The key idea is that if $A_j$ are some sets of non-negative integers and $N_a$ is the number of ordered representations $a=a_1+a_2+\dots$ with $a_j\in A_j$, then $$ \sum_{a\ge 0} N_az^a=\prod_j\left(\sum_{a_j\in A_j} z^{a_j}\right)\\,. $$ Unfortunately, this simplest form is not quite suitable for the weighted letter word counting. However, we can tweak this formula a bit.

Suppose we have an alphabet with letter weights $w_1,w_2,\dots$ and can use any letter any number of times. The number of words of weight $W$ we can create is $$ \sum_{\sum_j \ell_jw_j=W}\frac{\left(\sum_j\ell_j\right)!}{\prod_j\ell_j!} $$ (the standard combination with repetitions formula). Thus, taking into account that $\sum_{\ell\ge 0}\frac{Z^\ell}{\ell!}=e^Z$, we get almost what we want for the coefficient at $z^W$ if we consider the product $$ \prod_j \exp(z^{w_j}) $$
The only problem is that each word is counted not with the weight $1$, as it should in the uniform sampling, but with the weight that is the inverse factorial of its length, which skews the uniform distribution quite a bit. The way to compensate for that is to guess the typical length $L$ and to change the function to $$ \prod_j \exp(Lz^{w_j}) $$ Now, the coefficient is multiplied by $L^{\sum_j\ell_j}$, which is approximately proportional to $\left(\sum_j\ell_j\right)!$ as long as $\sum_j\ell_j\approx L$. As a matter of fact, this weighing emphasizes the words of the length $L$ a bit stronger than it should because $\frac{L^\ell}{\ell!}$ is maximized at $L$. However, as long as $\ell-L=o(\sqrt L)$, the skewing it introduces is negligible. This is what I called the local counting function: the weights are way too much suppressed outside a small window but we hope that outside that window we have only a small portion of words anyway, so suppressing them even further changes nothing in the picture.

If we have a clear idea of what the typical length is, we can introduce all other kinds of counters. To count the number of distinct letters, we need a variable that appears only once if the letter is used at all no matter how many times the letter is used after that. The factor $1+s(e^{Lz^{w_j}}-1)$ does exactly that if you look at the "typical" power of $s$ in the expansion (recall that $\frac{z^{\ell w_j}}{\ell!}$ corresponds to using the $j$-th letter $\ell$ times, so $s$ should appear once if $\ell>0$ and not appear if $\ell=0$). The unique letter counter should appear only if $\ell=1$, so $e^{Lz^{w_j}}-(1-s)Lz^{w^j}$ does the job adding the $s$-factor to the "linear term" in the expansion of the exponent but not anywhere else. You can now play a bit setting various counters yourself to see what generating functions to consider in various cases.

Part 2. The central term extraction.

Suppose now that we have a function $F(s,r)=\sum_{\ell,w}N(\ell,w)s^\ell r^w$ of two variables (you can trivially generalize this to more than two variables as well but I do not want to do the one-variable case because some games you can play with several variables would be invisible there). Suppose that we want to estimate $N(L,W)$. The obvious upper bound (the whole is larger than its part) is $$ N(W,L)\le s^{-L}r^{-W}F(s,r) $$ where we are free to choose $s$ and $r$. Of course, we are going to choose them so that the right hand side is as small as possible. This leads to the minimization problem $$ G(s,r)-L\log s-W\log r\to\min\\,. $$ Suppose that $(1,r)$ is a stationary point of the objective function, i.e., the differential vanishes there. Suppose also that, after switching to the variables $\log s,\log r$ (which makes the subtracted terms linear), the second differential is bounded by $A^2(ds)^2+B^2(dr)^2$ near this stationary point. Then we can easily control the sum of all terms that correspond to pairs $\ell,w$ that differ a lot from the pair $(L,W)$ in $F(s,r)$ by looking at $F(se^\sigma,re^\rho)$. We still have $$ N(\ell,w)s^\ell r^w\le e^{-\sigma\ell-\rho w}F(se^\sigma,re^\rho)= e^{-\sigma(\ell-L)-\rho (w-W)} e^{-\sigma L-\rho W}F(se^\sigma,re^\rho)\le e^{-\sigma(\ell-L)-\rho (w-W)}e^{A^2\sigma^2+B^2\rho^2}F(s,r) $$ due to the stationarity and the second derivative estimate.

Now, choosing $|\sigma|=A^{-1},|\rho|=B^{-1}$, we see that $$ N(\ell,w)s^\ell r^w\le \exp(-A^{-1}|\ell-L|+B^{-1}|w-W|)F(s,r)\\,, $$ so the terms with $|\ell-L|>A'$ or $|w-W|>B'$ can contribute at most $[Be^{-A'/A}+Ae^{-B'/B}]$ to $F(s,r)$. This crude bound is often enough to show that the main contribution comes from the terms with $w\approx W$, $\ell\approx L$, which sort of allows us to say that the pair $(L,W)$ is typical in the weighted counting where the pair $(\ell,w)$ has the weight $N(\ell,w)s^\ell r^w$. The key idea is that if $s=1$, then this counting is uniform in $\ell$ for each fixed $w$, so getting a typical pair in such weighted counting is essentially the same as getting a typical $L$ for fixed $W$.

Part 3. Circle method and mountain pass.

To be continued...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.