Is it possible to simplify the following function: $$p(n, k) = \sum_{\substack{x_1 + x_2 + \cdots + x_k = n \\\ x_i \in \mathbb{N}}} x_1^{x_1} x_2^{x_2} \cdots x_k^{x_k},$$ or, at least, find a good (easy to compute) approximation of $\log{(p(n, k))}$?

Here is my motivation. Consider a probabilistic node $A$ with $k$ output arrows $a_1, \cdots, a_k$, and let us assume that the probability of passing the $k$-th arrow is $p_k$. Then the probability of consecutively moving through arrows $x = \langle a_{i_1}, \cdots, a_{i_n} \rangle$ is $$ p^A(x) = \prod_{i = 1}^n p_{k_i} = \prod_{i = 1}^k p_i^{s_i}, $$ where $s_i$ is the number of occurences of $a_i$ in $x$. So given a sample $x$ and a probabilistic node $A$ the optimal length of a code describing $x$ is about $\log(\frac{1}{p^A(x)})$, and the shortest code is achieved for $A$ having probabilities $p_1 = \frac{s_1}{n}, \cdots, p_k = \frac{s_k}{n}$.

Now, let us assume that we do not know probabilities at $A$. Then any code describing $x$ via $A$ has to contain some information about these probabilities. A ``uniform approach'' would look like follows: for a given sample $x$ chose the optimal probability node $A_x$, then $u(x) = p^{A_x}(x)$ is not a probability on $k^n$ as it does not sum up to $1$ (it does not contain information about choosing appropriate $A_x$); however $p(x)$ is, where $$ p(x) = \frac{u(x)}{\sum_{y \in k^n} u(y)} = \frac{\prod_{i = 1}^k s_i^{s_i}}{\sum_{t_1 + \cdots + t_k = n} \prod_{i = 1}^k t_i^{t_i}}. $$

One may take another approach based on Bayesian interpretation. Let us fix a meta-distribution $q$ on all probabilistic nodes $A$ having the same output arrows. This distribution chooses probabilities $p_1, \cdots, p_k$, that is --- non-negative real numbers such that $p_1 + \cdots + p_k = 1$ --- then for a given sample $x$ chose a node $A_{p_1, \cdots, p_k}$ with probability $q(A_{p_1, \cdots, p_k})$ and describe $x$ according to that node: $$ b(x) = \int_{p_1 + \cdots + p_n = 1, p_i \geq 0} p^{A_{p_1, \cdots, p_k}}(x) q(A_{p_1, \cdots, p_k}). $$ If $q$ is a uniform distribution (and I have not made any mistake during calculations), then $$ b(x) = \frac{\int_{p_1 + \cdots + p_k = 1, p_i \geq 0} \prod_{i = 1}^k p_i^{s_i}}{\mathit{Vol}(\Delta_k)} = \frac{\Gamma(k) \prod_{i = 1}^k\Gamma(s_i + 1)}{\Gamma(\sum_{i = 1}^k (s_i + 1))}. $$ So $$p(x) = p \prod_{i = 1}^k s_i^{s_i}$$ is proportional to the probability corresponding to the Kolmogorov complexity of $x$ seen from the perspective of a "stateless" random source, and $$q(x) = q \prod_{i = 1}^k s_i^{\underline{s_i}}$$ is inversly proportional to the number of sequences containing exactly $s_i$ of $a_i$ (if there are a lot of such sequences, then from the perspective of a "stateless" random source they are "more" random, so less interesting). Here $p, q$ are some constants. In fact, these distributions are really close --- by using Striling's formula $n^{\underline{n}} \approx \sqrt{2\pi n}(\frac{n}{e})^n$ we have $$q(x) \approx q' \prod_{i=1}^k s_i^{s_i+\frac{1}{2}}$$ where $q' = q\;e^{-n} (2\pi)^{k/2}$ is just another constant.

I would like to compare $p(x)$ with $b(x)$.

  • 1
    $\begingroup$ I've slightly modified your formulas to make them more easily readable. I interpreted $\mathit{Nat}$ as the natural numbers, so I wrote $\mathbb{N}$ instead. Also, you should enclose LaTeX in $...$, not in \$...\$. $\endgroup$ – t.b. May 1 '11 at 17:02
  • 1
    $\begingroup$ is $0$ in $\mathbb{N}$? What is $0^0$? $\endgroup$ – Chris Eagle May 1 '11 at 17:06
  • 1
    $\begingroup$ Chris: let us assume that $0^0 = 1$ $\endgroup$ – Michal R. Przybylek May 1 '11 at 17:09
  • 6
    $\begingroup$ Here's an idea. Each term describes a partition of $[n] = \{ 1, 2, ... n \}$ and counts the number of functions $[n] \to [n]$ which preserve this partition (sending elements of a block to the same block). So instead of summing over partitions one can sum over functions $[n] \to [n]$ and ask how many partitions they preserve. This still seems rather complicated, but it might be more tractable to get bounds this way. $\endgroup$ – Qiaochu Yuan May 1 '11 at 17:09
  • 1
    $\begingroup$ The hyperfactorial will probably be needed here. $\endgroup$ – J. M. is a poor mathematician May 1 '11 at 18:39

Since the function $\log(x^x)$ is convex, the terms maximizing the sum are those equal to $n^n$, of which there are $k$. Conversely, the term minimizing the sum (assuming $k \mid n$) is $(n/k)^n$. Since there are in total $\binom{n+k-1}{k-1}$ summands, we get the following estimates for the sum: $$ kn^n + \left(\binom{n+k-1}{k-1} - k\right)(n/k)^n \leq S \leq \binom{n+k-1}{k-1} n^n \approx (n/k)^k n^n. $$ The second term on the left-hand side is equal to roughly $(n/k)^{n+k}$, so it's negligible compared to the first term for most values of $k$.

Taking the logarithm and making some estimates, we get $$ n\log n + \log k \leq \log S \stackrel{<}{\sim} (n + k) \log n. $$ This estimate is especially good if $k$ is small, and even in the worst case we get that $$ 1 \leq \frac{\log S}{n \log n} \leq 2. $$

It is surely possible to get better estimates with some more work, but it could get quite tedious.

  • $\begingroup$ Thanks for your estimation. In fact, after seeing your answer, it came to me that I was thinking about the wrong expression :-) Of course, there are $\binom{n}{t_1, \cdots, t_k}$ sequences having exactly $t_i$ of $a_i$. So, the right product is over $\frac{s_i^{s_i}}{\Gamma(s_i + 1)}$., but I guess both series give us about the same amount of fun :-) $\endgroup$ – Michal R. Przybylek May 4 '11 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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