12
$\begingroup$

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
    This would be much $n$icer with a multinomial coefficient in the sum.2011-05-01

1 Answers 1

1

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.

  • 0
    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 :-)2011-05-04