This work involves partitioning [itex][ \, 0, 1 ] \,[/itex] into an uncountable number of subsets, using choice to select a single element from each subset, and then defining a bijection from [itex]\mathbb{N}[/itex] onto each subset using that selected element as a reference. The framework allows for proof of two statements.(adsbygoogle = window.adsbygoogle || []).push({});

First Statement to Prove:

Given

1) the axiom of choice,

2) a randomly selected infinite binary sequence [itex]S = s_1, s_2, s_3,[/itex]... (created via the theoretical flipping of a coin infinitely many times where H = 1 and T = 0), and

3) a definition of "select an element of an infinite set uniformly at random" that simply means, in layman's terms, that one and only one element of an infinite set will be selected using a process where all elements of the set have an equal chance of being selected,

then it is possible to select a natural number uniformly at random.

Definitions:

Let [itex]V[/itex] be a set containing one and only one element from each Vitali equivalence class on the interval [itex][ \, 0.5, 1 ] \,[/itex] (Vitali equivalence classes are equivalence classes of the real numbers that partition [itex]\mathbb{R}[/itex] under the relation [itex]x \equiv y \iff ( \, \exists q \in \mathbb{Q} ) \, ( \, x - y = q ) \,[/itex]). The axiom of choice allows for such a selection.

Let [itex]D = \{ r \in [ \, 0, 1 ) \, : r[/itex] is a dyadic rational [itex]\}[/itex] (dyadic rationals are rational numbers whose denominator is a power of two and, as a result, whose binary expansion is finite).

Let [itex]E = \{ r \in \mathbb{Q} ( \, 0, 1 ) \, : r \notin D \}[/itex].

Let [itex]f : \mathbb{N} \longmapsto D[/itex] (here [itex]\longmapsto[/itex] denotes a bijection).

Let [itex]g : \mathbb{N} \longmapsto E[/itex].

Let [itex]h : \mathbb{N} \longmapsto \mathbb{Q} [ \, 0, 1 ) \,[/itex].

Let [itex]x[/itex] be a real number in [itex][ \, 0, 1 ] \,[/itex] selected at random via the binary sequence from (2) above such that [itex]x = 0.s_1s_2s_3[/itex]... .

Let [itex]n \in \mathbb{N}[/itex] denote the natural number that is selected uniformly at random as a result of the following process.

Process for Selecting [itex]n[/itex] Uniformly at Random:

There are three possibilities for [itex]x[/itex]. It may be a dyadic rational, a non-dyadic rational, or an irrational.

1) If [itex]x \in D[/itex] or [itex]x = 1[/itex]:

Each dyadic rational not equal to 0 or 1 has two binary expansions: one finite and one infinite (e.g. 0.1 = 0.0111…). The randomly selected number [itex]x[/itex] may take the form of either expansion. Let [itex]n[/itex] be such that [itex]f(n) = x[/itex] if [itex]0 < x < 1[/itex] and [itex]f(n) = 0[/itex] if [itex]x = 0[/itex] or [itex]x = 1[/itex]. At this point, there are two and only two possible ways of selecting each possible natural number.

2) If [itex]x \in E[/itex]:

Let [itex]n[/itex] be such that [itex]g(n) = x[/itex]. At this point, there are now three and only three ways of selecting each possible natural number.

3) If [itex]x \in [ \, 0, 1 ] \, \setminus \mathbb{Q}[/itex]:

There will exist one and only one element [itex]v \in V[/itex] such that [itex]v - x \in \mathbb{Q}[/itex]. For each rational [itex]q[/itex] on the interval [itex][ \, 0, 1 ) \,[/itex], there will be one and only one corresponding irrational [itex]i[/itex] on the interval [itex][ \, v - 0.5, v + 0.5 ) \,[/itex] such that [itex]q - 0.5 = i - v[/itex].

There are two possibilities for [itex]x[/itex]. It will either fall in the interval [itex][ \, v - 0.5, 1 ) \,[/itex] or in the interval [itex]( \, 0, v - 0.5 ) \,[/itex]. For each irrational [itex]y[/itex] on the interval [itex]( \, 0, v - 0.5 ) \,[/itex], there will be one and only one irrational [itex]z[/itex] on the interval [itex]( \, 1, v + 0.5 ) \,[/itex] where [itex]y + 1 = z[/itex]. In this fashion, we can biject all possible values for [itex]x[/itex] on the interval [itex][ \, 0, 1 ) \,[/itex] that are within the Vitali equivalence class containing [itex]v[/itex] with all possible irrationals on the interval [itex][ \, v - 0.5, v + 0.5 ) \,[/itex] that are also in the Vitali equivalence class containing [itex]v[/itex] (i.e., if [itex]x \in [ \, v - 0.5, 1 ) \,[/itex], then utilize [itex]x[/itex] itself whereas, if [itex]x < v - 0.5[/itex], utilize [itex]x + 1[/itex] instead). Select a suitable [itex]n[/itex] as follows:

If [itex]x \in [ \, v - 0.5, 1 ) \,[/itex], let [itex]n[/itex] be such that [itex]h(n) - 0.5 = x - v[/itex].

If [itex]x \in ( \, 0, v - 0.5 ) \,[/itex], let [itex]n[/itex] be such that [itex]h(n) - 0.5 = (x + 1) - v[/itex].

At this point, all possible values for [itex]x[/itex] will lead to the selection of a distinct value for [itex]n[/itex] and all [itex]n \in \mathbb{N}[/itex] have an equal chance of being selected.

End proof.

Second Statement to Prove:

It is possible to select an element of [itex]\mathbb{R}[/itex] uniformly at random given the first proof above.

Definitions:

Let [itex]j : \mathbb{N} \longmapsto \mathbb{Z}[/itex].

Let [itex]n[/itex] be selected uniformly at random via the above process.

Let [itex]x[/itex] be a real number in [itex][ \, 0, 1 ) \,[/itex] selected uniformly at random. Given the selection process used in the first proof, this requires two additional steps. First, since each dyadic rational has two binary expansions, each of the expansions must be related to a distinct and separate real number (this is trivial in that the dyadics may be listed along with their possible expansions, allowing for a mapping by indexes). Second, it is important that [itex]x \neq 1[/itex], which is again accomplished trivially by bijecting [itex][ \, 0, 1 ] \,[/itex] with [itex][ \, 0, 1 ) \,[/itex].

Let [itex]r \in \mathbb{R}[/itex] denote the real number that is selected uniformly at random as a result of the following process.

Process for Selecting [itex]r[/itex] Uniformly at Random:

[itex]r = j(n) + x[/itex].

End proof.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# I Selecting a Natural and a Real Uniformly at Random

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads for Selecting Natural Real |
---|

I Divisibility of bounded interval of reals |

I Probability of Surviving Pill Selection |

I Bijective function from naturals to primes |

**Physics Forums | Science Articles, Homework Help, Discussion**