## Probability distribution on the power set of natural numbers?

**Moderators:** gmalivuk, Moderators General, Prelates

- gmalivuk
- GNU Terry Pratchett
**Posts:**26728**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Probability distribution on the power set of natural numbers?

It seems intuitive that an infinite subset of natural numbers would have a finite complement with probability zero, but to actually demonstrate that we'd need a pdf over the power set of naturals.

The most straightforward way seems like it would be to specify the pdf over [0,1] and then match those real numbers one-to-one with sets of naturals, but treating the binary representation as an indicator function isn't a bijection on account of all those pesky numbers with multiple binary representations that would each correspond to a pair of subsets instead of just one.

So, is there an easy way to patch that problem, or a similarly simple alternative way to do what I want?

The most straightforward way seems like it would be to specify the pdf over [0,1] and then match those real numbers one-to-one with sets of naturals, but treating the binary representation as an indicator function isn't a bijection on account of all those pesky numbers with multiple binary representations that would each correspond to a pair of subsets instead of just one.

So, is there an easy way to patch that problem, or a similarly simple alternative way to do what I want?

### Re: Probability distribution on the power set of natural numbers?

Maybe looking at the continued fraction representation of a random number between 0 and 1 will get you somewhere. If a natural number appears in that representation, then it is a member of that associated set of natural numbers.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26728**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Probability distribution on the power set of natural numbers?

The problem is that continued fractions can repeat numbers. Which set of natural numbers corresponds to 1/phi, which has just a string of 1's in its continued fraction?

### Re: Probability distribution on the power set of natural numbers?

gmalivuk wrote:The problem is that continued fractions can repeat numbers. Which set of natural numbers corresponds to 1/phi, which has just a string of 1's in its continued fraction?

I was suggesting that you ignore any natural numbers that repeat. 1/phi = [0,1,1,1,1,...] would map to the set {1}, the number e-2 = [0;1,2,1,1,4,1,1,6,1,...] would map to the set {1,2,4,6,8,...}, and so on. I don't know much about continued fractions of random numbers, but it seems reasonable that any positive integer will turn up with probability 1.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26728**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Probability distribution on the power set of natural numbers?

But then [0;1,1,1,...] and [0;1] map to the same set of naturals despite being distinct real numbers, while [0;1,1] and [0;2] map to different naturals despite both representing 1/2.

### Re: Probability distribution on the power set of natural numbers?

I assume you intend to find a distribution where (informally) each set has the same probability? Otherwise your claim would depend on the chosen pdf..

You can try your bijection, but after fixing the duplicates it'll get a bit ugly. I've seen several such constructions in my life, none of them simple or beautiful or workable beyond an existence proof.

You'll then take the set of sets with finite complement, map it back to the [0,1], and then you have a very unwieldy set of reals which you need to measure. Good luck with that.

It may be easier to find a measure within the original domain. Measure the set of sets with finite complement; compare it to the measure of the power set. Then you'll have your answer without introducing any pdf at all.

Even easier, can you *count* the sets with finite complement? I think you can (which would trivially prove your claim), but I'm too tired to be sure. You go do that rigor thing yourself.

You can try your bijection, but after fixing the duplicates it'll get a bit ugly. I've seen several such constructions in my life, none of them simple or beautiful or workable beyond an existence proof.

You'll then take the set of sets with finite complement, map it back to the [0,1], and then you have a very unwieldy set of reals which you need to measure. Good luck with that.

It may be easier to find a measure within the original domain. Measure the set of sets with finite complement; compare it to the measure of the power set. Then you'll have your answer without introducing any pdf at all.

Even easier, can you *count* the sets with finite complement? I think you can (which would trivially prove your claim), but I'm too tired to be sure. You go do that rigor thing yourself.

- eta oin shrdlu
**Posts:**451**Joined:**Sat Jan 19, 2008 4:25 am UTC

### Re: Probability distribution on the power set of natural numbers?

Well, the infinite subsets with finite complements correspond precisely to these ambiguous cases with two representations. These are exactly the real numbers with terminating binary representations, and these are enumerable, so they have measure zero in [0,1]. That seems to be enough; have I missed something? [On preview I think this is the same as Tub is saying.]

If you want to map an interval to 2^N, can't you just make it a pdf over [0,2], with the first bit telling you which of the two subsets to choose in the ambiguous cases (and ignored in the non-ambiguous cases)? This isn't one-to-one, but I don't think it actually needs to be, right? You just need an unambiguous mapping from your random variable to a subset of 2^N.

If you want to map an interval to 2^N, can't you just make it a pdf over [0,2], with the first bit telling you which of the two subsets to choose in the ambiguous cases (and ignored in the non-ambiguous cases)? This isn't one-to-one, but I don't think it actually needs to be, right? You just need an unambiguous mapping from your random variable to a subset of 2^N.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26728**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Probability distribution on the power set of natural numbers?

Yeah, I realized fairly quickly that the countability of cofinite sets implies they'd be measure 0, but decided to keep the thread because I was curious if more general probabilities could be addressed.

### Re: Probability distribution on the power set of natural numbers?

eta oin shrdlu wrote:Well, the infinite subsets with finite complements correspond precisely to these ambiguous cases with two representations. These are exactly the real numbers with terminating binary representations, and these are enumerable, so they have measure zero in [0,1]. That seems to be enough; have I missed something?

That would work iff you had a bijection; the issue is that you don't due to the duplicates.

I've found the last time someone gave a bijection:

http://tasvideos.org/forum/viewtopic.ph ... 195#381195

The mapping between the cofinite sets and one of the rational representations means that the bijection is not quite as unwieldy as it is usually; you also don't need the tan() when you're working on [0,1] instead of |R. But the countability of the cofinite sets ends up being a requirement for the construction of the bijection, so you haven't gained much by transforming to the reals.

### Re: Probability distribution on the power set of natural numbers?

Let f() be the natural mapping from the power set of N to [0,1] defined as:

f(S) = sum_{i in S) 2^{-i}.

We know f() doesn't provide a bijection, but I think g() below provides a bijection between the power set of N and [0,1).

g(S) = f(S)/2 if S is finite;

= 1-(f(S)/2) if S is cofinite;

= f(S) otherwise.

Almost what we want, but there is no S such that g(S)=1.

Tub's link included a construction similar to this, as well as the more complete construction that used explicit enumerations.

=====

On a second note, selecting each element independently from N with equal probability p, with 0 < p < 1, gives finite and cofinite sets with probability 0. But if you select i in N to be in S with probability p_i = i^{-2}, if I calculate correctly, finite sets should appear with positive probabilities. If p_i = 1 - i^{-2}, cofinite sets should appear with finite probabilities. I wonder if you can tune p_i so that both finite and infinite sets appear with positive probabilities.

f(S) = sum_{i in S) 2^{-i}.

We know f() doesn't provide a bijection, but I think g() below provides a bijection between the power set of N and [0,1).

g(S) = f(S)/2 if S is finite;

= 1-(f(S)/2) if S is cofinite;

= f(S) otherwise.

Almost what we want, but there is no S such that g(S)=1.

Tub's link included a construction similar to this, as well as the more complete construction that used explicit enumerations.

=====

On a second note, selecting each element independently from N with equal probability p, with 0 < p < 1, gives finite and cofinite sets with probability 0. But if you select i in N to be in S with probability p_i = i^{-2}, if I calculate correctly, finite sets should appear with positive probabilities. If p_i = 1 - i^{-2}, cofinite sets should appear with finite probabilities. I wonder if you can tune p_i so that both finite and infinite sets appear with positive probabilities.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26728**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Probability distribution on the power set of natural numbers?

What do you mean "with equal probability p"? There can be no such p if you're considering all of N.DavidSh wrote:On a second note, selecting each element independently from N with equal probability p, with 0 < p < 1, gives finite and cofinite sets with probability 0.

Do you mean 2^-i? Otherwise you have to scale it to get a probability distribution that sums to 1.But if you select i in N to be in S with probability p_i = i^{-2}, if I calculate correctly, finite sets should appear with positive probabilities. If p_i = 1 - i^{-2}, cofinite sets should appear with finite probabilities. I wonder if you can tune p_i so that both finite and infinite sets appear with positive probabilities.

---

One way to randomly generate sets is to choose, with 50% probability, whether each natural number in sequence will be in the set, in which case you definitely do get probability zero of finite or cofinite sets, as each would require an infinite string of "yes" or "no" answers (which happens with probability zero).

### Re: Probability distribution on the power set of natural numbers?

gmalivuk wrote:What do you mean "with equal probability p"? There can be no such p if you're considering all of N.DavidSh wrote:On a second note, selecting each element independently from N with equal probability p, with 0 < p < 1, gives finite and cofinite sets with probability 0.

I see the confusion now. I meant select each element of N independently with probability p, much like what you are doing below with 50% instead of p, not each element of S uniformly over N. I know there is no uniform distribution over a countably infinite set like N.

Do you mean 2^-i? Otherwise you have to scale it to get a probability distribution that sums to 1.But if you select i in N to be in S with probability p_i = i^{-2}, if I calculate correctly, finite sets should appear with positive probabilities. If p_i = 1 - i^{-2}, cofinite sets should appear with finite probabilities. I wonder if you can tune p_i so that both finite and infinite sets appear with positive probabilities.

I meant i^{-2}, as I wrote. These are meant to be independent events, not mutually exclusive events. I wasn't talking about a probability distribution over N.

---

One way to randomly generate sets is to choose, with 50% probability, whether each natural number in sequence will be in the set, in which case you definitely do get probability zero of finite or cofinite sets, as each would require an infinite string of "yes" or "no" answers (which happens with probability zero).

### Re: Probability distribution on the power set of natural numbers?

You should be able to apply Kolmogorov's zero-one law:

https://en.wikipedia.org/wiki/Kolmogorov's_zero%E2%80%93one_law

The Hewitt--Savage zero-one law is even better for this problem I would think.

https://en.wikipedia.org/wiki/Hewitt%E2%80%93Savage_zero%E2%80%93one_law

https://en.wikipedia.org/wiki/Kolmogorov's_zero%E2%80%93one_law

The Hewitt--Savage zero-one law is even better for this problem I would think.

https://en.wikipedia.org/wiki/Hewitt%E2%80%93Savage_zero%E2%80%93one_law

### Who is online

Users browsing this forum: No registered users and 5 guests