Wat is de kans dat n random walks (1D) samenkomen in een punt na s stappen.

[OOOVincentOOO]

Afgelopen weken ben ik bezig geweest met de volgende vraag:

"Wat is de kans dat n random walks (1D) samenkomen in een punt na s stappen?"

Op math stacks exchange heb ik een vraag gesteld onderstaand volgt een vertaling.

https://math.stackexchange.com/q/3986806/650339

De vraag heb ik mijzelf gesteld omdat iemand op een ander forum schreef dat het samenkomen van de cumulatieve som van de decimalen van: e, π en φ (golden ratio) "cosmologische" betekenis heeft MF (wat hij geobserveerd heeft). Ik heb mezelf tot proef gesteld te bewijzen of dit waar is (intuitief: vind ik het een crackpot idee maar laat de wetenschap spreken). Indien e, π en φ normale getallen zijn (zoals voor miljoenen decimalen is aangetoond) komen de decimalen van deze even vaak voor. Op deze manier is de decimalen progressie van deze constanten als een random walk te zien.

Methode:
Voor iedere stap s van een random walk (1D) kan de kans dichtheids functie bepaald worden. Hiervoor dient de standaard deviatie per stap bepaald te worden.

De standaard deviatie per stap kan bepaald worden uit een "discrete uniform distribution", hierbij heeft ieder element een gelijke kans van optreden. We stellen q het aantal mogelijkheden bijvoorbeeld het aantal decimalen: [0,1,2,3,4,5,6,7,8,9], dus q=10:
$$\sigma=\sqrt{\frac{q^{2}-1}{12}} $$
Voorlopig in dit voorbeeld word gesteld dat alle random walks (1D) starten in de oorsprong. De variantie van de random walk neemt proportioneel toe met het aantal stappen SE link. We kunnen nu de standaard afwijking bepalen voor iedere stap s:
$$Var(s)=s \cdot \sigma^{2}$$
$$\sigma(s)=\sqrt{s} \cdot \sigma$$
Het aantal bins per stap neemt snel toe. Hierdoor kan de normale verdeling benadering van de Binomiale verdeling gebruikt worden:
$$f(x)=\int_{-\infty}^{\infty} {\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x}{\sigma }}\right)^{2}}dx $$
De kans dat n random walks (1D) samenkomen in een punt/stap s kan bepaald worden met:
$$p(s)=\int_{-\infty}^{\infty} \left[ {\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x}{\sigma }}\right)^{2}} \right]^n dx$$
Empirsch zijn oplossingen gevonden met behulp van Wolfram Alpha WA. De gevonden relatie is dan de kans op interctie op stap s, en ziet uit als:
$$p(s)= \frac{1}{g(n) \cdot \sigma ^{(n-1)} } \cdot s^{-\frac{1}{2}(n-1)} $$
Waar de functie g(n) gevonden is als:
$$g(n)=\sqrt { n} \cdot (2 \pi)^{\frac{1}{2}(n-1)}$$
Onderstaand een voorbeeld van n=3 random walks. Te zien is dat het samenkomen van 3 random walks in een punt niet uniek is. Bij minder dan 1200 stappen is de kans ~8% dat dit voorkomt (zowel theoretisch als numeriek aangetoond). Er is dus geen cosmologische of bijzondere reden waarom de cumulatieve decimalen som van e, π en φ samenkomen.

De totale kans over alle stappen s is dan alleen afhankelijk van de p-series gevormd door s. De sommatie kan dus ook bepaald worden door de Riemann Zeta function:
$$\zeta(\tiny{\frac{1}{2}(n-1)} \normalsize) =\sum\limits_{s=1}^{\infty}s^{- \frac{1}{2}(n-1)}$$
$$p(n)=\frac{1}{g(n) \cdot \sigma^{(n-1)}} \cdot \sum\limits_{s=1}^{\infty}s^{- \frac{1}{2}(n-1)} $$
Grafiek informatie.
Onderstaand een tabel en grafiek van de totale kans p(n) van het samenkomten van n random walks (1D) in een punt. Details:

• De standaard deviatie is gekozen als 10 gelijke kansen per stap: \(\sigma=\sqrt{\frac{99}{12}}\)

• Voor oneindige random walks \(n \rightarrow \infty\) convergeert de p-serie naar 1. Deze kan is geplot als: \(p_{\infty}(n)\).

• p(n) kan als continue functie geplot worden.

Observaties.

• n=3 random walks zullen elkaar altijd oneindig maal treffen in een enkel punt. p-series: \(\sum\limits_{s=1}^{\infty}s^{-1}=\infty\), Riemann Zeta: \(\zeta(1)=\infty\) beide geven oneindige kans \(p(n)\rightarrow \infty\).

• n=2 random walks zullen elkaar altijd oneindig maal treffen in een punt. Volgens de p-series: \(\sum\limits_{s=1}^{\infty} s^{-\frac{1}{2}}=\infty\), echter de interpretatie Riemann Zeta is onduidelijk: \(\zeta(\frac{1}{2})=-1.46035...\) de geeft een negatieve kans \(p(2)\).

• Het is mogelijk dat meer dan n=4 random walks zich nooit treffen in een enkel punt. Voor n=4 is een kans van ~0.35 % dat random walks zich treffen in een enkel punt (met 10 evenredige kansen per stap).

• Dit beschreven verschijnsel is in de literatuur bekend als: recurrence and transience.

Vraag.
Voor de kans dat n=2 random walks erlkaar treffen in een punt is direct gerelateerd aan de positie van de critische lijn van de Riemann zeta functie \(\zeta(0.5)\). Heeft iemand een idee hoe de negatieve kans te interpreteren is?

[OOOVincentOOO]

De laatste dagen heb ik nog wat verder gestoeid met de kans op het doorkruisen van n random walks.

Ik ben geïnteresseerd in de vraag wat de kans is dat n aantal random walks bij elkaar komen na s stappen. Hierbij laat ik de random walk voor iedere stap d willekeurige posities toe. Voor d=2 betekend [-1,1] of voor d=4 [-3,-1,1,3].

Enkele tijd geleden had ik al een continue vergelijking (normale benadering) gevonden deze werkte perfect voor grote aantal stappen. Hiermee kan ik bepalen of het aantal doorkruisingen convergeerde of divergeerde. Zo blijkt dat voor drie of minder random walks elkaar oneindig kruisen. Voor meer dan 4 random walks is er een grens slechts een aantal doorkruisen sommige geheel niet!

Met behulp van een generating functie ben ik in staat de kans nauwkeurig te bereken voor kleine aan stappen. Hier alles een beetje samengevat, welke diepe dalen en bergen ik heb doorkruist staat er niet bij vermeld. Maar ik heb wel veel geleerd. Na zwoegen en veel fouten maken is het leuk te zien dat theorie en praktijk (simulatie) samenkomen.

Zie het antwoord op mijn eigen vraag op SE:

https://math.stackexchange.com/q/3986806/650339

=========================================
After studying I think I answered my own question.

In my earlier answer I demonstrated how to determine the probability of n intersecting random walks with 2 or more likely outcomes per step. The method used a normal approximation making an error in the probability for small numbers of steps.

The probability of intersection for small number of steps can be calculated with an discrete method. By using generating functions, a solution is found and is based upon: [SE].

The probabilities of a single random walk at step s is determined by the coefficients of the generating function below. Where d is the number of equal likely possibilities per step e.g. d=2 for random walk: [-1,1]:

$$\left( \frac{1}{d}x^{0}+\frac{1}{d}x^{1}+\frac{1}{d}x^{2}...+\frac{1}{d}x^{d-1} \right)^{s}=\frac{1}{ d^{s}} \left( \frac{1-x^{d}}{1-x} \right)^{s}$$

The coefficients can be calculated by applying the generalized binomial theorem. Where n is the number of intersecting random walks. p(s) is the total probability for an intersection occurring on step s:

Discrete method, s<=20:
$$p(s)=\frac{1}{d^s} \sum_{i=0} \left( \sum_{r=0} (-1)^{r} \binom{s}{r} \binom{s+i-dr-1}{i-dr} \right)^{n}$$

The discrete method is realistic for s<20 steps. For more than s\geq20 the normal approximation is more efficient. Using my earlier answer for empirical found formula [SE]:

Continuous method, s>=20:
$$\sigma=\sqrt{\frac{d^{2}-1}{12}}$$
$$p(s)= \frac{1}{\sqrt { n} \cdot (2 \pi)^{\frac{1}{2}(n-1)} \cdot \sigma ^{(n-1)} } \cdot s^{-\frac{1}{2}(n-1)} $$

Both functions have been verified in a simulation. The intersections of n=4 random walks where counted. Random walks were used with d=4 likely outcomes per step [-3,-1,1,3]. The graphs show the discrete method is accurate for s<20 the normal approximation is useful for s>=20.

---
Finally, I want to summarize that the total probability: the sum over all steps p(n) can be calculated by using the p-series (or Riemann Zeta function):

$$p(n)=\frac{1}{\sqrt { n} \cdot (2 \pi)^{\frac{1}{2}(n-1)} \cdot \sigma ^{(n-1)} } \sum\limits_{s=1}^{\infty}s^{- \frac{1}{2}(n-1)}$$

$$p(n)=\frac{1}{\sqrt { n} \cdot (2 \pi)^{\frac{1}{2}(n-1)} \cdot \sigma ^{(n-1)} } \zeta(\small{\frac{1}{2}(n-1)} \normalsize) $$

However these formulas have been found empyrically and I am still looking for confirmation.

For n<=3 intersecting random walks the series diverges resulting in infinite intersections. For n>=4 the series converges resulting in finite number of intersections. Interesting is that n=2 intersecting random walks coincides with the critical line on the Riemann Zeta function.