Probability distribution on the power set of natural numbers?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
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?

Postby gmalivuk » Thu Dec 22, 2016 8:51 pm UTC

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?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
cyanyoshi
Posts: 407
Joined: Thu Sep 23, 2010 3:30 am UTC

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

Postby cyanyoshi » Thu Dec 22, 2016 9:56 pm UTC

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.

User avatar
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?

Postby gmalivuk » Thu Dec 22, 2016 10:17 pm UTC

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?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
cyanyoshi
Posts: 407
Joined: Thu Sep 23, 2010 3:30 am UTC

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

Postby cyanyoshi » Thu Dec 22, 2016 11:12 pm UTC

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.

User avatar
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?

Postby gmalivuk » Thu Dec 22, 2016 11:30 pm UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Tub
Posts: 465
Joined: Wed Jul 27, 2011 3:13 pm UTC

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

Postby Tub » Thu Dec 22, 2016 11:47 pm UTC

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.

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

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

Postby eta oin shrdlu » Thu Dec 22, 2016 11:49 pm UTC

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.

User avatar
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?

Postby gmalivuk » Fri Dec 23, 2016 12:18 am UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Tub
Posts: 465
Joined: Wed Jul 27, 2011 3:13 pm UTC

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

Postby Tub » Fri Dec 23, 2016 7:14 am UTC

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.

DavidSh
Posts: 207
Joined: Thu Feb 25, 2016 6:09 pm UTC

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

Postby DavidSh » Fri Dec 23, 2016 3:14 pm UTC

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.

User avatar
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?

Postby gmalivuk » Fri Dec 23, 2016 3:47 pm UTC

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.
What do you mean "with equal probability p"? There can be no such p if you're considering all of N.

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.
Do you mean 2^-i? Otherwise you have to scale it to get a probability distribution that sums to 1.
---
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).
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

DavidSh
Posts: 207
Joined: Thu Feb 25, 2016 6:09 pm UTC

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

Postby DavidSh » Fri Dec 23, 2016 4:56 pm UTC

gmalivuk wrote:
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.
What do you mean "with equal probability p"? There can be no such p if you're considering all of N.

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.
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.
Do you mean 2^-i? Otherwise you have to scale it to get a probability distribution that sums to 1.

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).

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

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

Postby DavCrav » Mon Dec 26, 2016 12:29 pm UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 5 guests