Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Consider the block diagram above which descibes the evolution of a point

(x,y)N×N. Suppose
Δ
is drawn from a random distribution with values spanning
[0,2π)
. What happens to the value of the radius (r) over time?

First, I'll show the radius never increases (Lemma 1). Then, I'll show for all possible values of the radius, there exists

Δ which results in the radius decreasing (Lemma 4). Thus, given sufficent time the radius goes to zero.

Lemma 1: The radius never increases.

rn=xn2+yn2=(rncos(θ))2+(rnsin(θ))2=rncos(θ)2+sin(θ)2=rncos(θ+Δ)2+sin(θ+Δ)2(by Pythagorean identity)=(rncos(θ+Δ))2+(rnsin(θ+Δ))2rncos(θ+Δ)2+rnsin(θ+Δ)2=rn+1

Lemma 2: If

xN, then
x2<x2
.

Proof. If

xN, then
x
has a non-zero decimal component, so flooring
x
decreases its magnitude.

Lemma 3: If

x is not irrational and
k
is irrational, then
x×kN
.

Proof. Because

x is not irrational,
x
can be expressed as the ratio of two natural numbers
xab
. Suppose
x×kmN
, then
kmxmabm×ba
, but then
k
is not irrational as it can be expressed as the ratio of two natural numbers.

Lemma 4: For all

rn there is a
Δ
for which
rn>rn+1
.

Proof.

rn is irrational or not.

Case I:

rn is irrational. Setting
Δ=θ
:

rn=(rncos(θ+Δ))2+(rnsin(θ+Δ))2=(rncos(0))2+(rnsin(0))2=rn2>rn2(by Lemma 2)=rn+1

Case II:

rn is not irrational. Setting
Δ=π4θ
:

rn=(rncos(θ+Δ))2+(rnsin(θ+Δ))2=(rncos(π4))2+(rnsin(π4))2=(rn2/2)2+(rn2/2)2(by Lemma 3, rn22N)>rn2/22+rn2/22(by Lemma 2)=rn+1