Circle from (2D) random walk

Moderators: dirkwb, Xilvo

Reageer
Gebruikersavatar
Berichten: 1.130

Circle from (2D) random walk

Afgelopen tijd ben ik bezig geweest met cirkels gecreëerd vanuit polygonen waarbij omtrek=1 of oppervlakte is 1. Hierbij de polygonen op de grens van continu en discreet aan het bestuderen.

Recent heb ik de polygonen aanpak uitgebreid en een random factor toegevoegd. Hierdoor ontstaat deels een random walk (dronkemans loop). De effectieve cirkel omtrek word kleiner, ingezoomd ziet de omtrek willekeurig/kronkelig uit. Er is een treshold waarbij deze cirkels niet meer herkend kunnen worden. Uit mijn bevindingen blijken all deze gekke cirkels te bestaan indien men de treshold verlaagd.

Taal en schrijven is niet mijn specialiteit. Dus hier de Engelstalige versie welke gepost.

Next is the topic I worked on last week. It takes allot effort for me to create something, and making many mistakes but learning allot. I posted question also on SE because I think this topic potentially has more depth then know with my limited knowhow.

Math Stacks Exchange: Circle from (2D) random walk

A method is presented to create circles from sort of random walks. The hobby project is based upon two earlier topics: circles from \(n-\)gons with circumference: \(C=1\) [SE] or area: \(A=1\) [SE].

The \(n-\)gon formula can be extended with a random variable.
\(x(n)=\frac{1}{n} \sum_{k=1}^{q} \cos \left( \frac{X+2k}{n_{i}} \pi \right)\)
\(y(n)=\frac{1}{n} \sum_{k=1}^{q} \sin \left( \frac{Y+2k}{n_{i}} \pi \right)\)

The total step length or "circumference" is set to \(1\). Where \(n\) is the number of \(n-\)gon edges (and steps in the random walk). The summation is discrete with \(k\) usually till \(q=n\), completing a full circle till \(2\pi\). Two random (uniform distributed) variables are introduced: \(X\) and \(Y\). These random variables are defined as an element between: \([0,2]\) \(\pi\). The number of elements is determined by variable \(p\) such that:

\(p=2, \quad X \in \{0,2\} \quad \textrm{and} \quad Y \in \{0,2\}\)
\(p=3, \quad X \in \{0,1,2\} \quad \textrm{and} \quad Y \in \{0,1,2\}\)
\(p=4, \quad X \in \{0,\tfrac{2}{3},\tfrac{4}{3},2\} \quad \textrm{and} \quad Y \in \{0,\tfrac{2}{3},\tfrac{4}{3},2\}\)
\(etc.\)

When \(p=2\) we will get regular \(n-\)gons, while the elements \(0\) and \(\pm 2\pi\) have no effect on \(\sin\) and \(\cos\). When \(p>2\) the number of possible outcomes per step increases. A random walk effect can be observed.

In the video below the circle creation for \(p=2\) till \(6\) is presented. The random walk consists of \(N=1.000.000\) steps, \(k\) is listed as natural numbers from: \(1\) till \(1.000.000\). Every walk is displayed and looped over \(n_i\).



Several observations have been made (see normal picture below).
  • For \(p=2\) the regular \(n-\)gons can be seen (triangle, square, pentagon...) left image GIF file.
  • For \(p>2\) initially random walk structures are seen gradually (multiple) circles appear.
  • After \(1.000.000\) steps single circles can be observed for all presented values of \(p\).
  • The edges of all circles for \(p>2\) have rough and overlapping edges.
  • The effective circle diameter decreases. Empirical: it is found that the circumference decreases with: \(1/p\) see picture.
  • The effective walk length is calculated as the sum of all: \(\Delta r=\sqrt{\Delta x^2+\Delta y^2}\). Observation: the total path length for \(p>3\) is less than \(1\) on average: \(0.96\). This is one of key questions.
Random Walk00100 1920.png
Random Walk00100 1920.png

For the decrease in diameter, I came up with the following explanation. But not sure if it is completely valid (I struggled with $\arcsin$ distribution and various other deviations).

First assume \((1)\) as continuous and integrate:

\(x(n)=\frac{1}{n} \int \cos \left( \frac{X+2k}{n_{i}} \pi \right) dk = \frac{1}{2 \pi} \sin \left( \frac{X+2k}{n_{i}} \pi \right) \tag{2}\)

With the sum formula for cosine (and sine) formula \((2)\) can be rewritten:

\(x(n) = \frac{\sin \left( X \pi \right)}{2 \pi} \cdot \cos \left( \frac{2k}{n_{i}} \pi \right) + \frac{\cos \left( X \pi \right)}{2 \pi} \cdot \sin \left( \frac{2k}{n_{i}} \pi \right) \tag{3}\)

The random parts of the radius are: \(\sin \left( X \pi \right)\) and \(\cos \left( X \pi \right)\). These have influence on the radius.

After trial and error, I came up with the following formula calculating the mean radius error\( \Delta \bar{R}\) (not sure about this):

\(\Delta \bar{R_{x}}=\frac{1}{p} \sum_{m=0}^{p-1} \cos \left( \frac{ 2 \pi \ m }{p-1} \right) \)
\(\Delta \bar{R_{y}}=\frac{1}{p} \sum_{m=0}^{p-1} \sin \left( \frac{ 2 \pi \ m}{p-1} \right) \)

Found a solution with help of Wolfram Alpha:

\( \Delta \bar{R_{x}}= \frac{1}{2p} \left[ \sin \left( \frac{\pi p}{1-p}\right) \csc \left( \frac{\pi}{p-1} \right) +1 \right] \)

\(\Delta \bar{R_{y}}=\frac{1}{2p} \left[ \cos \left( \frac{\pi }{p-1}\right) +\cos \left( \frac{\pi p}{1-p}\right) \right] \csc \left(\frac{\pi}{p-1} \right) \)

When analyzing these functions (discrete \(p\)) I found that \(\Delta \bar{R_{x}}\) decreases with \(1/p\) just like the simulation. However the \(\Delta \bar{R_{y}}\) seems to be \(0\) for discrete values of \(p\). Not sure but then formula \((3)\) (and \(y\) counter part) simplifies. Also: there exists no solution for \(p=2\) according Wolfram Alpha in this context. So, for \(p>2\):

\(\boxed {x(n) = \frac{1}{2 \pi p} \cdot \sin \left( \frac{2k}{n_{i}} \pi \right) \\ y(n) = - \frac{1}{2 \pi p} \cdot \cos \left( \frac{2k}{n_{i}} \pi \right)}\)

I would like to have feedback if method is acceptable thus far. Note that this is a hobby project by amateur.

Open question:
  • How can the total path length be smaller for random walk circles? I observed that when the random variables for axis \(x\) and \(y\) are equal: \(X=Y\) then the total path lengt is: \(1\).
  • Do all presented random walk circles exists for $p \rightarrow \infty$ and the number of steps is infinate?
Seems I have found on answer to point 1 I am running a better plot like posted on SE. Any advice and feedback on topic is welcome. Basic code below (full code here Github: [Github]):

Code: Selecteer alles

import numpy as np
import matplotlib.pyplot as plt

fig, ax = plt.subplots(1, figsize=(12,12))
ax.axis('equal')

n=10000
steps=10000
p=4

N=np.arange(0,steps)
t=N/n

px=2*np.random.choice(p,steps)/(p-1)
py=2*np.random.choice(p,steps)/(p-1)

x=1/(steps)*np.cos((px+t*2)*np.pi)
x=np.append(x,x[0])

y=1/(steps)*np.sin((py+t*2)*np.pi)
y=np.append(y,y[0])

xc=np.cumsum(x)
yc=np.cumsum(y)

xd=np.diff(xc)
yd=np.diff(yc)
dr=np.sqrt(xd**2+yd**2)
circum=np.sum(dr)

ax.plot(xc[:n],yc[:n],linewidth=0.15,color='black')
plt.show()

Gebruikersavatar
Berichten: 1.130

Re: Circle from (2D) random walk

Door numerieke analyse ben ik meer te weten gekomen gisteravond. Ik het gegevens geplot waarbij ik ook alleen de random variabelen: \(X\) en \(Y\) alleen geplot heb.

Totaal:
\(x(n)=\frac{1}{n} \sum_{k=1}^{q} \cos \left( \frac{X+2k}{n_{i}} \pi \right)\)

Alleen de pure random walk:
\(x(n)=\frac{1}{n} \sum_{k=1}^{q} \cos \left( \frac{X}{n_{i}} \pi \right)\)

Eerst merkte ik op dat de horizontale waarneming grens in de buurt van \(1/\sqrt{N}\) lag (in de buurt van blauwe lijn in grafiek). Een random walk groeit met \(\sqrt{N}\) de stap grootte is \(1/N\) wat resulteert in: \(1/\sqrt{N}\).

Hiermee was ik niet tevreden. De waarneming grens is beter beschreven door het volgende (excuses wederom Engels, daar het ook op SE staat):

Last night I realized that the observation threshold can be calculated more accurate. The previous post was not accurate enough. For big values of \(p\) meaning there are: many steps between interval \([0,2] \pi\) for random variable \(X, Y\) to pick from. This will form a \(\arcsin\) distribution.

A random walk grows with the square root of the step(size) [SE]. The random walk tends towards a \(\arcsin\) distribution [Wiki] with \(stdev\):

\(\sigma^2=\frac{(b-a)^{2}}{8}\)

Where: \(|a|=|b|=1/N\):

\(\sigma=\frac{1}{N \sqrt{2}}\)

The \(\sigma\) will grow with \(\sqrt{N}\) see previous link (and CLT: central limit theorm). So \(\sigma\) after \(N\) steps:

\(\sigma_t=\frac{1}{\sqrt{2N}}\)

This limit for \(3 \sigma\) \((99.7 \%)\) is plotted: blue line graph. This is the circle observation threshold.

When the number of steps increases (smaller step size) the observation threshold reduces making the random walk circles visible. I am not sure how all statistics is properly involved while my method is rather empirical based.
Not All Circles Log.png

Gebruikersavatar
Berichten: 1.130

Re: Circle from (2D) random walk

Net voor het einde van het weekeinde een mogelijke beschrijving waarom de afgelegde afstand bij statistisch onafhankelijke \(x\) en \(y\) iets korter is. Dat is een hele rit na dik een week zitten puzzelen en analyseren. Voor mijzelf zijn alle hoofdvragen dan ook beantwoord.

-----------------------
Pfew, these things really get into my head and really hard to find (possible) solution with I understand. I think to have found a explanation why the path length is shorter in case of random walks with independent \(x\) and \(y\) with more outcomes per step.

The other question was: why is the total walked path shorter then \(1\) when random variables \(X\) and \(Y\) are independent? \(X\) and \(Y\) are uniform distributed elements between \([0,2]\pi\).

\(x(n)=\frac{1}{n} \sum_{k=1}^{q} \cos \left(X \pi \right)\)
\(y(n)=\frac{1}{n} \sum_{k=1}^{q} \sin \left( Y \pi \right)\)

In case \(X\) and \(Y\) are independent any result vector can be created between: \(x \in [0,1]\) and \(y \in [0,1]\), where \(1\): is the single step length.
800 Walked Path dependant and independant.jpg
In case \(X\) and \(Y\) are independent: any vector start in \([0,0]\) and endpoint within the rectangle \(x \in [0,1]\) and \(y \in [0,1]\) is possible.

When \(x\) and \(y\) would be uniform distributed the average vector length \(\bar{R}\) can be calculated. The following integral was found after study and checking numerical (Python code discrete):

\(\bar{R}=\frac{1}{a^{2}}\int_{0}^{a} \int_{0}^{a} \sqrt{ x^2+y^2} \ dx dy\)

Where \(a\) is the maximum step size single step. For \(a=1\) we find a solution with Wolfram Alpha: \(\bar{R}=0.765196...\). The total walked path would be \(0.765196...\) in case \(x\) and \(y\) are uniform distributed.

However: the angles \(X\) and \(Y\) are uniform distributed and not \(x\) and \(y\). The integral then converts to:

\(\bar{R}=\frac{4}{\pi^{2}}\int_{0}^{\pi /2} \int_{- \pi/2}^{0} \sqrt{ \cos^{2}(X \pi)+\sin^{2}(Y \pi)} \ dX dY\)

Also with Wolfram Alpha a solution is found:

\(\bar{R}=0.958091...\)

This result is confirmed (discrete) numerical (see code below).

My conclusion:
The difference in the walked path when \(X\) and \(Y\) are independent can be found by averaging the length of all possible vectors. Numerical summation gives result as found in original question. The used calculus might require improvement while not my specialty. So if someone could give more information of more neat calculus. I do not have the capabilities and knowhow to solve the integrals myself.

Code: Selecteer alles

import numpy as np
x=np.linspace(-np.pi/2,0,1001)
y=np.linspace(0,np.pi/2,1001)

X,Y =np.meshgrid(x,y)

def radius(x,y):
    return np.sqrt((np.cos(x))**2+(np.sin(y))**2)

z=np.array([radius(x,y) for (x,y) in zip(np.ravel(X), np.ravel(Y))])

print(np.mean(z))
Het is trouwens jammer dat Latex niet goed integreert hier op het forum. Dut de tekst ziet wat chaotisch uit.

Gebruikersavatar
Berichten: 1.130

Re: Circle from (2D) random walk

Nog een typefout ontdekt de laatste integraal. Dient limieten tussen \(0\) and \(2\) te zijn:

\(\bar{R}=\frac{1}{4}\int_{0}^{2} \int_{0}^{2} \sqrt{ \cos^{2}(X \pi)+\sin^{2}(Y \pi)} \ dX dY\)

Het ging om een type fout dus gelopen weglengte voor onafhankelijke \(X\) en \(Y\) is:

\(\bar{R}=0.958091...\)

Zoals gezien in simuatie (zie plaatje eerste post). Discrete berekening (Python voorgaande mail) en de integraal.

Gebruikersavatar
Berichten: 1.130

Re: Circle from (2D) random walk

Merkte nog een typefout op in de openings post. Weet niet of strikeout mathjax werkt heb een truckje toegepast:

Toegevoegd in tekst:

Code: Selecteer alles

[itex]\require{cancel}[/itex]
\(\require{cancel}\)
$$\cancel{x(n)=\frac{1}{n} \sum_{k=1}^{q} \cos \left( \frac{X+2k}{n_{i}} \pi \right)}$$
$$x(n)=\frac{1}{n} \sum_{k=1}^{q} \cos \left( \left( X+ \frac{2k}{n_{i}} \right) \pi \right)$$

De essentie blijft hetzelfde. Zo krijg je respect voor prof. theoretisch wiskundigen als je alleen tekst voor je hebt. Wanneer je programmeert zie je het effect van een type fout met schrijven niet!

Zie updated versie op SE:
https://math.stackexchange.com/q/4194503/650339

Mijn hoofdvragen zijn voorlopig beantwoord.
  • Men kan oneindig veel random walk circles creëren indien men het aantal stappen in de random walk verhoogt.
  • De diameter van een random walk cirkel word kleiner als men meer een (continue) arcsin distributie nadert. De diameter neemt as met: \(1/p\). Waarbij \(p\) is aantal stappen random variabele tussen \([0,2]\pi\)
  • Indien de random variabelen \(X\) en \(Y\) onafhankelijk zijn, voor \(p>2\) is de (gemiddelde) afgelegde loop lengte: \(0.958091...\) en niet \(1\)!
Hier nog enkele plaatjes van niet perfecte cirkels (wie is perfect?) voor kleinere aantal stappen:
Figure_1.png
Figure_2.png
Figure_3.png

Berichten: 229

Re: Circle from (2D) random walk

Benieuwd wat de toepassingen zijn voor de random walk in een cirkel. Uiteraard heeft de algemene random walk veel toepassingen zoals de weg die een molecule aflegt in een vloeistof. Wat het zo mogelijk nog interessanter maakt is dat er ook random quantum walks zijn. Ik ga daar weer eens in duiken. Wellicht lukt het behalve het algemene quantum walk model ook een cirkelvormige quantum walk te maken.
Wel vraag ik mij af wat de toepassing is van een cirkelvormige quantum walk

Gebruikersavatar
Berichten: 1.130

Re: Circle from (2D) random walk

@sensor, Enige toepassingen??? Geen idee verrijking van de geest :o .

Afgelopen weken vakantie gehad en kunnen reflecteren op de random walk circles.

Inmiddels heb ik een intuitive verklaring gevonden waarom de omtrek afneemt met \(1/p\).

Terugblik:
Een standaard \(n\)-gon formule (driehoek, vierkant, vijfhoek, zeshoek.....circel) waarbij \(n\) het aantal zijden is. Deze kan men uitbreiden met een random variabele \(X\) en \(Y\) zo creëert men een random walk:
$$x(n)=\frac{1}{n} \sum_{k=1}^{n} \cos \left(X+ \frac{2k}{n} \pi \right)\\
y(n)=\frac{1}{n} \sum_{k=1}^{n} \sin \left(Y+ \frac{2k}{n} \pi \right)$$
De random variabelen zijn uniform verdeeld en onderdeel van een van de verzamelingen \(p\):
$$p=2, \quad X \in \{0,2\} \quad \textrm{and} \quad Y \in \{0,2\}\\p=3, \quad X \in \{0,1,2\} \quad \textrm{and} \quad Y \in \{0,1,2\}\\p=4, \quad X \in \{0,\tfrac{2}{3},\tfrac{4}{3},2\} \quad \textrm{and} \quad Y \in \{0,\tfrac{2}{3},\tfrac{4}{3},2\}\\etc.$$

Verklaring omtrek \(1/p\):
Met de methode in OP kan ik dit ook aantonen. Echter op een manier wat door niemand te volgen is! Soms bewandel ik bij onderzoekjes ook een random walk! Je weet nooit wat te ontdekken is. Zo leer je veel (van soms omwegen) :D .

Uit de simulaties en meetgegevens kon ik vaststellen dat de omtrek afneemt met: \(1/p\).

In iedere verzameling komen twee de gelijke hoeken voor namelijk: \(0(\pi)\) en \(2(\pi)\). Dit betekend dat \(1/p\) kans op een gelijke hoek is.

Dus voor \(1/p\) "procent" van de stappen in de random walk vormen de omtrek van de cirkel. En dit is precies wat word waargenomen!
Random Walk00111.png

Effectief gelopen pad:
Tevens had ik vorige maand een verklaring/inzicht gevonden voor effectief gelopen afstand random walk. Dit zijn alle kleine vectoren die iedere stap verbinden. Dit is niet:
\(1\) maar \(0.95802...\)

Via de integraal (ik heb geen wiskunde SW (behalve Wolfram online limited) maar gooi die maar eens in Mathematica ofzo!):
$$\bar{R}=\int_0^1 \int_0^1 \sqrt{\cos^2(X \pi)+\sin^2(Y \pi)} \ dX\,dY=0.95802 \ldots$$
Dit is een echt monster en ben blij inzicht verkregen te hebben. Dit ga ik niet hier delen dan kan ik een boek schrijven. Hier echt tot het limiet van mijn kunnen gegaan. Respect voor professionele wiskundigen, zoveel moeten studeren en erkennen wat men niet weet! Bijna alles zelf gedaan, en een heel klein beetje hulp van MSE summiere comments.

Toolbox:
roteren functie \([x,y,z]\) over \(z\)-as, arcsine distributies, convolutie hiervan, elliptische integraal, transponeren verdeling van \(R^2-1\) naar \(R\), gemiddelde bepalen \(pdf\) (probability density functie).
Random Walk Dingetjes.jpg
Misschien dat mensen iets hebben aan mijn zoektocht en leercurve. Wilde dit graag delen en kan men leren van mijn fouten en goede dingen. Zie MSE voor mijn pijnlijke leercurve:
https://math.stackexchange.com/q/4196822/650339

Zo eindelijk een berichtje waar ik plezier aan heb. Dankjewel als sommigen misschien passief mijn onzin volgen. Veel feedback krijg ik nooit, maar fictief in mijn hoofd verbeeld ik mij allerhande reacties en kritiek!!! Sick mind is a joy forever!!! :D :P :!: :?: :?: :geek:

Reageer