4
$\begingroup$

My goal is finding an explicit formula for a recursively defined funtion $f_{k,N}:\{1,\ldots,N\} \to \mathbb R$, where $N,k \in \mathbb N$.

(If it matters. $f_{k,N}$ is a probability distribution function over $\{1,2,\ldots,N\}$)

But I do have no idea how to approach this problem.

The anchors are: $$f_{k,1}(1) = 1, \quad \forall\, k\\ f_{1,N}(x) = \frac 1 N, \quad \forall N \in \mathbb N, x \in \{1,2,\ldots,N\}$$ The recursion is: $$f_{k,N}(x) = \sum_{l=x}^N \frac{1}{l} f_{k-1,l}(x).$$

Is there a general approach to this problem? Can anyone find a non-recursive formula for $f_{k,N}$ in general, or at least in some special cases?


EDIT: In the meantime I was able to come up with following to special cases, but can we find a formula for the general $x \in \{1,2,\ldots,N\}$?

$$ f_{k,N}(N) = \frac{1}{N}f_{k-1,N}(N) = \cdots = \frac{1}{N^{k-1}} f_{1,N}(N) = \frac{1}{N^k} $$

$$ \begin{align} f_{k,N}(N-1) &= \frac{1}{N-1} \underbrace{f_{k-1,N-1}(N-1)}_{= \frac{1}{(N-1)^{k-1}}}+ \frac{1}{N} f_{k-1,N}(N-1) \\ &= \frac{1}{(N-1)^k} + \frac{1}{N}\left( \frac{1}{(N-1)^{k-1}} + \frac{1}{N}f_{k-2,N}(N-1) \right)\\ &= \cdots = \sum_{n=0}^k \frac{1}{N^{k-n}(N-1)^n} \end{align} $$

$\endgroup$
7
$\begingroup$

If $f_{k, n}(x)$ for each $1 \leq x \leq n$ forms a vector $\vec{f_{k, n}}$ of probalities, then:

$$\vec{f_{k+1, n}} = \begin{bmatrix} 1 & 1\over 2 & 1\over 3 & \cdots & 1\over n \\ 0 & 1\over 2 & 1\over 3 & \cdots & 1\over n \\ 0 & 0 & 1\over 3 & \cdots & 1\over n \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 0 & 0 & 0 & \cdots& 1\over n \end{bmatrix} \vec{f_{k, n}} = A_n\vec{f_{k, n}}$$

We can use this identity repeatedly to show that:

$$\vec{f_{k, n}} = A_n^k \begin{bmatrix}0\\ \vdots \\ 0 \\ 1\end{bmatrix}$$

We can use $A$'s eigenvectors and values to diagonalize $A$ such that $P^{-1}HP = A$ where $H$ is a diagonal matrix. This is beneficial, because then we have $A^k = P^{-1} H^k P$, and taking the power of a diagonal matrix is trivial.

Since $A$'s diagonal elements are all distinct its diagonal is also its eigenvalues. But as it turns out, the eigenvectors of $A$ form Pascal's triangle! E.g. for $n = 5$:

$$P^{-1} = \begin{bmatrix} 1 & -1 & 1 & -1 & 1 \\ 0 & 1 & -2 & 3 & -4 \\ 0 & 0 & 1 & -3 & 6 \\ 0 & 0 & 0 & 1 & -4 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}, P = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} $$

Using this knowledge we can construct an explicit formula for $f_{k, n}$:

$$f_{k,n}(x) = \sum_{l=1}^n \underbrace{(-1)^{x + l}\binom{l-1}{x-1}}_\text{$x$th row of $P^{-1}$} \overbrace{\frac{1}{l^k}}^\text{$H$ diagonal}\underbrace{\binom{n-1}{l-1}}_\text{last column of $P$}$$

Using binomial identities and noticing that the sum is zero for $l < x$ we can simplify this to:

$$f_{k, n}(x) = \frac{x}{n} \left | \sum_{l=x}^n \frac{(-1)^l}{l^k}\binom{l}{x}\binom{n}{l} \right |$$

$\endgroup$
1
$\begingroup$

Let $g_{k,n}(x)=\frac1nf_{k,n}(x)$. Then $$ g_{k,1}(1)=1$$ $$g_{1,N}(x)=1\text{ for }1\le x\le N $$ $$g_{k,N}(x)=\frac1N\sum_{l=x}^Ng_{k-1,l}(x) $$ First observe that $g_{k,N}(x)=0$ for $x>N$. Henec the recursion can be simplified(?) to $$g_{k,N}(x)=\frac1N\sum_{l=1}^Ng_{k-1,l}(x). $$ From this, one can easily show some things like $\lim_{k\to\infty}g_{k,n}(x)=1$

$\endgroup$

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.