6

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} $$

Ѕᴀᴀᴅ
  • 34,263
flawr
  • 16,533
  • 5
  • 41
  • 66

2 Answers2

8

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 |$$

orlp
  • 10,508
1

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$

Hagen von Eitzen
  • 374,180