Paradox of uniform prob. distribution on Z+ vs cardinality, etc.

mXSCNT

Well you asked for it, here it is. It was a good deal harder to do than I expected. It took a few wrong turns producing invalid F's (that either weren't surjective, or weren't injective) before I found a solution. Reminder:

First let b be the infinite string of binary digits representing a real number r between 0 and 1 (including 0, but not including 1). For example if r = 0.1101101000011010111... then b = 1101101000011010111.... We adopt the convention that b does NOT end in an infinite series of 1s - because any real number that ends in an infinite series of 1s has an alternate representation that does NOT end in an infinite series of 1s. for example 0.0111111... = 0.100000000... Therefore, b contains an infinite number of 0s.

First, we map b to an infinite series of positive integers [itex]a_i[/itex]. Let p_1 be the position in b of the (i-1)'th 0 in b (or p_1 = 0 if i = 1), and let p_2 be the position in b of the i'th 0 in b. Then define [itex]a_i = p_2 - p_1[/itex].

For example, if b = 10011000... (ending in an infinite series of 0s) then:
[itex]a_1[/itex] = 2 - 0 = 2
[itex]a_2[/itex] = 1
[itex]a_3[/itex] = 1
[itex]a_4[/itex] = 3
[itex]a_5, a_6, a_7,[/itex] etc. = 1

Now, to construct m from the [itex]a_i[/itex], we loop over the [itex]a_i[/itex] building m.

Define a sequence of partial functions [itex]m_i[/itex] (corresponding to our incremental construction of m). Each [itex]m_i[/itex] can be considered as a set of ordered pairs of integers. Define [itex]D_i[/itex] to be the support of [itex]m_i[/itex] (the set of values where it is defined), and [itex]R_i[/itex] to be the image of [itex]D_i[/itex] under [itex]m_i[/itex]. [itex]m_0[/itex] is empty.

Given [itex]a_0, a_1, ..., a_i, a_{i+1}[/itex] and [itex]m_0, m_1, ..., m_i[/itex], we now construct [itex]m_{i+1}[/itex].

Define a function f(S, v) where S is a set of positive integers and v is a positive integer. f(S, v) gives the v'th smallest integer NOT an element of S.

Let [itex]d_{i+1} = f(D_i, 1)[/itex]
Let [itex]r_{i+1} = f(R_i, 1)[/itex]
CASE 1: If [itex]d_{i+1} < r_{i+1}[/itex], then [itex]m_{i+1}[/itex] is the same as [itex]m_i[/itex] except for the additional pair [itex](d_{i+1}, f(R_i, a_{i+1}))[/itex]
CASE 2: Else, If [itex]d_{i+1} \geq r_{i+1}[/itex], then [itex]m_{i+1}[/itex] is the same as [itex]m_i[/itex] except for the additional pair [itex](f(D_i, a_{i+1}), r_{i+1})[/itex].

Define m as the function where m(a) = b if and only if there exists some i where [itex]m_i[/itex](a) = b.

Finally, following this process (starting with r, deriving b from it, deriving the a_i, and finally the [itex]m_i[/itex], and then m), we define F to be the function where F(r) = m.

To produce [itex]F^{-1}(m)[/itex], repeatedly pick the pair (v, w) from m that has not yet been chosen, that minimizes min(v, w). If there is a tie between two different pairs, choose the pair with the larger v and the smaller w. Then, produce the appropriate [itex]a_i[/itex] (based on the domain and range values already used) for the larger element of the pair. Then convert the [itex]\{a_i\}[/itex] back into a binary string b, and finally to the real number r.

Now, I first claim that every m generated by F is an element of M. For that to be true, two things must be true: First, if (v, w) is in m, we can't have either (y, w) or (v, z) also in m, where y [itex]\neq[/itex] v and z [itex]\neq[/itex] w. Second, for every v in [itex]Z^+[/itex], there must exist a (v, w) in m (for some w), and also there must exist an (x, v) in m (for some x).

The first thing is guaranteed because every time we added a new pair (v, w) to [itex]m_{i+1}[/itex], the values used were guaranteed not to have been used before in [itex]m_i[/itex], because v was of the form [itex]f(D_i, *)[/itex] and w was of the form [itex]f(R_i, *)[/itex].

The second thing is guaranteed because at each step, either v or w was the smallest unused element of either the domain or the range. So after 2n steps, [itex]m_{2n}[/itex] is guaranteed to have pairs (v, w) and (x, v) for any v < n.

So, every m generated by F is an element of M. Next we need to show that F is one-to-one. Suppose we had different real numbers r1, r2 with binary expansions b1, b2, and f(r1) = m = f(r2). Because b1 != b2, the [itex]a_i[/itex] must also differ. So choose the smallest i where [itex]a_{1,i} \neq a_{2,i}[/itex] (denoting the difference between the [itex]a_i[/itex] for b1 vs the [itex]a_i[/itex] for b2 by 1 or 2 in the subscript). Since that was the smallest i, [itex]m_{i-1}[/itex] must be the same for both b1 and b2. So if CASE 1 from the calculation procedure for m_i is met, then it must be met for both, and m1 has [itex](d_{1,i+1}, f(R_{1,i}, a_{1,i+1}))[/itex], whereas m2 has [itex](d_{2,i+1}, f(R_{2,i}, a_{2,i+1}))[/itex]. Since [itex]d_{1, i+1} = d_{2, i+1}[/itex], m1 and m2 have different values for the same element of their domain, so they are different functions. If instead CASE 2 is met, a similar argument shows that again, m1 [itex]\neq[/itex] m2. So, F is one-to-one.

Next, F is surjective because the method described earlier to construct [itex]F^{-1}(m)[/itex] will always produce a real number r where F(r) = m.



OKAY!

So what can we tell about this F in the context of your original question?

Well, it's certainly not "uniform." For example, there's at least a 1/2 chance that given a random real number r between 0 and 1, F(r)(1) = 1. Any binary string that begins with 0 will have that property, corresponding to a real number between 0.0 (zero) and 0.1 (one half). With a random r, m = F(r) is likely to map small numbers to other small numbers.

Stephen Tashi

In the recursion, I don't understand the initialization step. How are [itex] D_1 [/itex] and [itex] R_1 [/itex] defined? (i.e. I'm asking about the subscript that is the number 1, not the letter "i" ).

mXSCNT

D_i is the set of all numbers v where (v, w) is in m_i, and R_i is the set of all numbers w where (v, w) is in m_i. They don't really need a base case, but you could say that D_0 and R_0 = the empty set.

mXSCNT

Perhaps an example would help. [itex]\pi - 3 = 0.14159... = 0.001001000011111101101010...[/itex] in binary. Calculating [itex]F(\pi - 3) = m[/itex] we find:
[itex] a_1 = 1, d_1 = 1, r_1 = 1, m(1) = 1[/itex]
[itex] a_2 = 1, d_2 = 2, r_2 = 2, m(2) = 2[/itex]
[itex] a_3 = 2, d_3 = 3, r_3 = 3, m(4) = 3[/itex]
[itex] a_4 = 1, d_4 = 3, r_4 = 4, m(3) = 4[/itex]
[itex] a_5 = 2, d_5 = 5, r_5 = 5, m(6) = 5[/itex]
[itex] a_6 = 1, d_6 = 5, r_6 = 6, m(5) = 6[/itex]
[itex] a_7 = 1, d_7 = 7, r_7 = 7, m(7) = 7[/itex]
[itex] a_8 = 1, d_8 = 8, r_8 = 8, m(8) = 8[/itex]
[itex] a_9 = 7, d_9 = 9, r_9 = 9, m(15) = 9[/itex]
[itex] a_{10} = 3, d_{10} = 9, r_{10} = 10, m(9) = 12[/itex]
[itex] a_{11} = 2, d_{11} = 10, r_{11} = 10, m(12) = 10[/itex]
[itex] a_{12} = 2, d_{11} = 10, r_{11} = 11, m(10) = 13[/itex]
and so on.

Stephen Tashi

mXSCNT,

I see what you did. That is a very ingenious example.

My intuitive interpretation of that example is an [itex] F^-1 [/itex] that sends all maps with the same initial sequence of ordered pairs into the same set of intevals, then to further parcel out the maps defined by longer sequences, you must subdivide the first set of intervals. This gives more measure to the events defined earlier in the sequences than to events defined later.

That would (intuitively) imply that an algorithm to get a 'uniform" [itex] F^-1 [/itex] would have to assign sequences in a manner that didn't make decisions by processing the ordered pairs in a sequential manner. It would have to make decisions based on some overall property of the sequence. For example, mapping the sequence to a function and using the fourier series for it, or something like that.

Of course, such attempts should fail. But how strong an impossibility result can be shown by an indirect proof of the form:

It is possible to ..... because to do so would imply there was a translation invariant probability distribution on the nonzero integers (?)


Putting things in a slightly postive way, can it be as general as the following: (?)

Let M be a set of mappings of the nonzero integers into themselves (no requirement that these be 1-1 mappings or that they be subjective.)

Let [itex] (X,\mu,\sigma) [/itex] be a measure space (no requirement that [itex] X [/itex] be [0,1] or that the measure [itex] \mu [/itex] be Lebesgue measure)

Let [itex] F [/itex] be a mapping whose domain is [itex] X [/itex] and whose range is [itex] M [/itex].

Let [itex] S_{i,j} [/itex] denote the subset of [itex] X [/itex] defined by [itex] \{x: F(x)(i) = j\} [/itex]

Then at least one of the following must be true.

1) There exists nonzero integers i,j such that [itex] S_{i,j} [/itex] is not a [itex]\mu[/itex]-measureable set.

2) There exists nonzero integers j,k such that [itex] \sum_{i=0}^{\infty} \mu( S_{i,j}) \ne \sum_{i=0}^{\infty}\mu(S_{i,k}) [/itex]

mXSCNT

Where are you getting these statements from? Using my example of F, both of those statements are false. (1) is false because [itex]S_{i,j}[/itex] is a countable union of intervals within [0, 1) so it is measurable. (2) is false because [itex] \sum_{i=0}^{\infty} \mu(S_{i,j}) = 1 [/itex] for all j, because [itex]\bigcup_{i=0}^{\infty} S_{i,j}[/itex] is the set of all real numbers r where if m = F(r) then [itex]m(i) = j[/itex] for some [itex]i[/itex], which is just [itex][0, 1)[/itex] because m is always a bijection.

Stephen Tashi

I agree
I agree. I was trying to express the probability that [itex] j [/itex] is the final outcome of the random sampling. The correct way to to do that is simply to say

2) There exists nonzero integers i,j,k such that [itex] \mu(S_{i,j}) \ne \mu(S_{i,k}) [/itex]

This takes the view that we can sample the integers by fixing an arbitrary [itex] i [/itex] and then let the randomly selected [itex] r [/itex] define a m = F(r) that maps it to another integer.

In my original scenario, I was selecting [itex] i [/itex] at random from a distribution and also selecting [itex] r [/itex] at random. So comparing the probability of getting [itex] j [/itex] to the probability of getting [itex] k [/itex] would compare sums taken over [itex] i [/itex] but they would involve products of the [itex] \mu(S_{i,j}) [/itex] and the density [itex] g(i) [/itex].

mXSCNT

I think you do want to restrict X to be [0, 1). Because if X were all the real numbers, even if you could define a map where [itex]\mu(S_{i, j})[/itex] is the same for any i, j, that wouldn't help you since you can't uniformly sample from all the real numbers.

Anyway you've basically just stated an impossibility result. You know it's impossible to have a uniform distribution over the integers.