Page 1 of 1

Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Tue Jul 18, 2017 6:41 am UTC
Hi,

I am looking at defining a function a(n) in terms of another function f(n), with a(n) defined as:

a(n) = f(n) - ∑i=1n-1( f(i)*a(n-i) )

I have noticed that for some functions f, the sum of a(n) over positive integers n goes to 1. I have proved this for f(n)=1/(n+1) , as well as for f(n) = c , where 0<c<1 is constant (the inequalities here are strict.). (I can fetch the proofs of these if desired)

Call the sum of the first n values of a(n), b(n). Call the sum of the first n values if f(n), g(n).

I have noticed that b(n) = g(n) - ∑i=1n-1( f(i)*b(n-i) ),

which I thought was interesting, because it has a very similar form to the definition of a(n).

The values of f in the context I am looking at represent probabilities, so they should all be between 0 and 1.

f(n) is, as I am looking at it, the probability that the first n terms of a permutation of the natural numbers is by itself a permutation of the first n natural numbers. a(n) is the probability that this is the case, and that there is no n* < n such that the first n* terms of the permutation is a permutation of the first n* natural numbers.

So, the sum over a(n) should be the probability that there is some N such that the first N terms of the random permutation is a permutation of the first N natural numbers.

There are a few different probability distributions over the permutations of the natural numbers which I am considering, and these give rise to different functions for f. One of the nicest ones I've found has f(n)=1/(n+1) , and as I've mentioned, I've shown that the sum over a(n) in that case does sum to 1. (Well, ok, I've shown it under the assumption that the oeis sequence that came up and the description also made sense as matching what I was doing was the same sequence as what I was looking for. Haven't strictly proven it yet, but I'm fairly sure I'm right about it. Relates to the bernoulli numbers. I can give the argument for this upon request.)

However, another possible distribution which is of interest to me has a much less nice function for f.

What I am hoping is the case is that in the other distribution(s) I am looking at, that the associated f function will give an a(n) function which also sums to 1.

So, I thought that instead of looking at the particular f(n) for that distribution, I would consider how a(n) depends on f(n) in general.

I have found a few things :

f(n) >= (f(1))^n , provided that f(n) always in (0,1) and that a(n) always in [0,1) .

a(n) can be expressed as a sum of all the products of f(m_i) such that the sum of the m_i is equal to n, which corresponds to a partition of n, with coefficients being, assuming I am correct about the oeis sequence being right for this, basically the number of distinct ways to order that particular partition, along with a sign depending on the ways to order that partition or something like that. I don't know what a good notation to use for this sum would be.

Looking experimentally/computationally, a number of the functions I have tried for f(n) (such as 1/sqrt(n+1) ) do seem to make the partial sums of a(n) converge to 1. Some of these however are cases that wouldn't make sense, because they have some negative values for a(n) sometimes, and so it converges to 1 from both sides. I think this sort of thing shouldn't happen with any function f(n) which would actually make sense for my purpose though. I think these functions converging to 1 even in these cases suggests that it might be easier to show that the b(n) -> 1 in a fairly broad range of cases.

Some restrictions on what functions f(n) I think are likely to be relevant:
non-increasing, positive, limit being 0

The oeis sequences which I believe should be the (negative of) the coeffecients for the terms that correspond to the different permutations : http://oeis.org/A111786

If anyone would like to give any feedback or assistance with any of this, I'd appreciate it.

I've been wishing I had someone to work with on my little math projects...

Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Thu Jul 20, 2017 4:18 pm UTC
madaco wrote:I am looking at defining a function a(n) in terms of another function f(n), with a(n) defined as:

a(n) = f(n) - ∑i=1n-1( f(i)*a(n-i) )

I have noticed that for some functions f, the sum of a(n) over positive integers n goes to 1. I have proved this for f(n)=1/(n+1) , as well as for f(n) = c , where 0<c<1 is constant (the inequalities here are strict.).
Are you familiar with the convolution operation? Do you know about Fourier series? Below is an approach to solving this equation using these ideas.

The summation in this definition is called the convolution of sequences f and a, conventionally written with the "*" operator

(f*a)(n) = ∑i=1n-1( f(i)a(n-i) )

(I got rid of the scalar multiplication symbol * just to avoid confusion). Convolution is a very important and fundamental operation, even though its definition may appear rather random. (In general the sum runs over all integer n; here we implicitly take f(n)=a(n)=0 for n<=0 so that the sum is restricted to the range shown.)

One important interpretation of convolution is as polynomial (or formal power series) multiplication: If sequences f and g are the coefficients of two polynomials or power series in x,
F(x) = ∑n f(n) xn
G(x) = ∑n g(n) xn
then sequence f*g is the sequence of coefficients of F(x)G(x).

This suggests an approach to solving for sequence {a(n)}, using what you might call either a generating-functions approach or application of Fourier (or Laplace or Z) transforms, by converting the equation to one for the power series F(x) and A(x). The formal algebraic manipulations are basically the same either way, though the transform variable is typically given some sort of frequency interpretation: e.g., in Fourier series we take x=exp(i ω) for some "frequency" ω.

[If you haven't seen the concepts of convolutions, transforms, or generating functions, a forum post is not the place to learn all about them. The above is just a short motivation for this idea.]

So the equation above transforms to
A(x) = F(x) - F(x) A(x)
where A and F are the generating functions (or transforms) of sequences a and f, i.e.
F(x) = ∑n f(n) xn
A(x) = ∑n a(n) xn .

This can trivially be algebraically solved for A:
A(x) = F(x) / (1 + F(x)) .
Now the coefficients a(n) are just the coefficients of the power series for A.

In general it can be kind of tedious to find these coefficients, so you may not have gained much over the original equation (though in special cases where the power series are simple or well-known this version may be quick). However, note that
A(1) = ∑n a(n)
is the sum over a(n), which you are interested in; so you have the equation
A(1) = F(1) / (1 + F(1))
giving the sum over a(n) in terms of the sum over f(n), which you may find useful.

You'll note that A(1)=1 iff F(1)=+-infinity. Your examples f(n)=1/(n+1) and f(n)=c both have divergent sums, so by this result you expect the a(n) to sum to 1. If you choose f(n) to approach zero more rapidly so that the sum over f(n) is finite, then you get a sum over a(n) smaller than 1.

Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Fri Jul 21, 2017 2:37 am UTC
Oh wow, yes, that is very helpful! You have my gratitude.

I am not really familiar with convolutions, but I have learned some about the laplace transform, and have some idea of what the fourier transform is like. Also I think I had seen that the product of two power series as a power series has the coefficients being the convolution of the coefficients of the 2 input power series, but hadn't really ever looked into that.

I would like to check to see that I understood correctly.

The definition I gave of a(n) could be rephrased as

a(n) = f(n) - (a*f)(n)

(where * is involution)

and then A(n) = ∑n a(n) xn is therefore = ∑n ( f(n) - (a*f)(n) ) xn,
and so A(n) = ∑n ( f(n)xn - (a*f)(n)xn ),
= ∑n ( f(n)xn) - ∑n ((a*f)(n)xn )
= F(x) - A(x)*F(x)
And so A(x) = F(x) - A(x)*F(x)
so A(x)*(1+F(x))=F(x)
so A(x) = F(x)/(1+F(x))
and then A(1) is the sum of the a(n) that I want.

Right?

So then, at this point my question is, does it matter if the radius of convergence of F(x) is substantially less than 1, or does the line of reasoning hold regardless?

Or, do some of the transforms allow one to sidestep the convergence issue?

In any case, "A(1)=1 exactly when F(1) diverges to +- infinity" seems like exactly why I need.

And, I think I can prove that (1-p) + (1-p)*(1-p^2) + (1-p)*(1-p^2)*(1-p^3) + ... diverges by comparison test with the harmonic series as expressed as
1/2 + (1/2)*(2/3) + (1/2)*(2/3)*(3/4) + ... ,

So, this is great, I think that this solves my problem.

Thank you very much!

(the conclusion that this gives me is that, for the distributions I'm looking at, a randomly selected permutation of N can, with probability 1, be split up into infinitely many finite blocks of sequential integers, which are each permuted separately.)

Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Fri Jul 21, 2017 2:02 pm UTC

I am looking at defining a function a(n) in terms of another function f(n), with a(n) defined as:

a(n) = f(n) - ∑i=1n-1( f(i)*a(n-i) )
...

f(n) is, as I am looking at it, the probability that the first n terms of a permutation of the natural numbers is by itself a permutation of the first n natural numbers. a(n) is the probability that this is the case, and that there is no n* < n such that the first n* terms of the permutation is a permutation of the first n* natural numbers.

So, the sum over a(n) should be the probability that there is some N such that the first N terms of the random permutation is a permutation of the first N natural numbers.

There are a few different probability distributions over the permutations of the natural numbers which I am considering, and these give rise to different functions for f. One of the nicest ones I've found has f(n)=1/(n+1) , and as I've mentioned, I've shown that the sum over a(n) in that case does sum to 1. (Well, ok, I've shown it under the assumption that the oeis sequence that came up and the description also made sense as matching what I was doing was the same sequence as what I was looking for. Haven't strictly proven it yet, but I'm fairly sure I'm right about it. Relates to the bernoulli numbers. I can give the argument for this upon request.)

However, another possible distribution which is of interest to me has a much less nice function for f.

I was trying to understand why you claim that a(n) would be the probability you state above.

A nice simple distribution of permutations over the natural numbers is the one generated by starting with the original sequence 1,2,3,...,
and then swapping each pair (2n-1, 2n) for n=1,2,..., independently with probability 1/2. (Yes, I know there are a lot of permutations this cannot generate .)

In this case, f(n) = 1/2 for n odd, and f(n) = 1 for n even.

a(1) = f(1) = 1/2.
a(2) = f(2) - f(1)*a(1) = 1 - (1/2)*(1/2) = 3/4.

However, the probability, under this distribution, of the first two elements of the permutation being a permutation of {1,2}, while the first element of the permutation not being a permutation of {1} is clearly 1/2.

Is there some further condition on the distribution of the permutations that makes the formulas give the stated probabilities?

Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Fri Jul 21, 2017 10:37 pm UTC
First, thank you for your interest.

In the distributions I am looking at, the probability that, given that the first m elements of the permutation form a permutation themselves, the probability that the next n elements after the first m form a permutation, is the same as the probability that the first n elements of a random permutation forms a permutation. Further, the distribution of what permutation the n elements after the m elements have, does not depend on what permutation the first m elements have.

In general, if you condition on the first m elements forming a permutation, or forming a specific permutation (either one), the conditional distribution over the rest of the permutation is the same as the distribution you get to start with without conditioning, except with everything shifted forward by m.

So, for example, the chance of getting 2,1,5,7,4,... conditional on getting 2,1,... is the same as the chance of getting 3,5,2... .

So, it doesn't have the sorts of correlations that your example has.

(Also, any finite prefix of a permutation has a nonzero chance of occurring in the ones I am looking at.)

Does that make the conditions I'm reasoning under clear enough?

Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Sat Jul 22, 2017 2:45 pm UTC
Yes, that makes things clear now. Thank you.

Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

Posted: Tue Jul 25, 2017 10:33 pm UTC
madaco wrote:I would like to check to see that I understood correctly.

The definition I gave of a(n) could be rephrased as

a(n) = f(n) - (a*f)(n)

(where * is involution)
...convolution, not involution; otherwise yes...
and then A(n) = ∑n a(n) xn is therefore = ∑n ( f(n) - (a*f)(n) ) xn,
and so A(n) = ∑n ( f(n)xn - (a*f)(n)xn ),
= ∑n ( f(n)xn) - ∑n ((a*f)(n)xn )
= F(x) - A(x)*F(x)
And so A(x) = F(x) - A(x)*F(x)
so A(x)*(1+F(x))=F(x)
so A(x) = F(x)/(1+F(x))
and then A(1) is the sum of the a(n) that I want.

Right?
Right. (Just to emphasize, you're using * to mean two different things in different contexts: simple multiplication, A(x)*F(x), and convolution, a*f.)

So then, at this point my question is, does it matter if the radius of convergence of F(x) is substantially less than 1, or does the line of reasoning hold regardless?

Or, do some of the transforms allow one to sidestep the convergence issue?
I glossed over convergence issues in my previous post, so good catch. First note that in your problem the f(n) are supposed to be probabilities, so they are bounded in [0,1]. Hence F has radius of convergence at least 1, and is positive and monotone nondecreasing for 0<x<1. In the two examples you give (f(n)=1/(n+1) and f(n)=c) the radius of convergence is exactly 1, though the sums don't converge at x=1 (both series have poles at x=1).

Write A(x) = H(F(x)) with H(y) = y/(1+y); we have that H is positive and monotone increasing from (0,infinity) -> (0,1). So for 0<x<1, F is positive and nondecreasing; so A is also positive and nondecreasing, with 0 < A(x) < 1.

So because the sum F(x) converges for all 0<x<1, you can at any rate consider the limit as x approaches 1 from below. Since A is monotone and bounded, this limit must exist and must lie in [0,1] (which is good since A(1) has an interpretation as a probability). For cases where F has a pole at 1, the expression A(x) = F(x)/(1+F(x)) will have a removable singularity on the right side, after which it becomes continuous at 1, giving you a valid expression for A on [0,1].

More generally I *think* that as long as the power series for F has a nonzero radius of convergence, the expression for A(x) will have power-series coefficients which are correct for a(n); you can think of the transform as a set of formal algebraic manipulations without worrying too much about convergence. I'm not sure about this though; there may be some further constraints you need for this to work.