I am struggling finding a relation to determine the probability $n$ random walks (1D) intersect in a single point at step $s$. In the method below my attempts. My method is somewhat intuitive based. I am looking for more rigorous proof.
note: This question arises from someone who claims that a matching cumulative digit sum of: $\pi$, $e$ and $\varphi$ (golden ratio) is unique and "cosmological" [1]. I tend to disprove it. This digit sum can be seen as a random walk if the constants are normal (every digit occurs with same frequency).
Method:
For every step $s$ on the random walk we can determine the probability density function if we know the standard deviation on every step $s$.
The standard deviation of a single step can be calculated it's a discrete uniform distribution "equally likely outcomes", where $q$ is the number of outcomes e.g. the number of digits $[0,1,2,3,4,5,6,7,8,9]$, $q=10$:
$$\sigma=\sqrt{\frac{q^{2}-1}{12}} $$
All the (1D) random walks start in the origin for this example. The standard deviation will grow with every step $s$, the variance is proportional to the number of steps [2].
$$Var(s)=s \cdot \sigma^{2}$$
$$\sigma(s)=\sqrt{s} \cdot \sigma$$
While the bins grow rapid I assume a normal approximation of the Binomial distribution.
$$f(x)=\int_{-\infty}^{\infty} {\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x}{\sigma }}\right)^{2}}dx $$
The probability that $n$ random walks intercept in a single point is (not sure):
$$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 $$
With help of Wolfram Alpha [3] the solution is found for $n=3$ meaning the probability of $3$ point intersecting random walks.
$$p(s)=\frac{1}{2 \sqrt{3} \ \pi \ \sigma^{2}} \cdot \frac{1}{s}$$
The total probability $p(n)$ is proportional to the reciprocal sum of $s$. So the total probability is proportional to the harmonic series:
$$p(n)=\frac{1}{2 \sqrt{3} \ \pi \ \sigma^{2}} \cdot \sum_{s=1}^{\infty}\frac{1}{s}$$
This series diverges, meaning there are infinate point intersections of $n=3$ random walks. So a matching cumulative digit sum of $\pi$, $e$ and $\varphi$ is not unique, probability $\sim 8 \%$ for the first 1200 digits (see graph).
Question
Does anyone know the general formula for the probability $p(n)$ that $n$ random walks (1D) intersect a single point?
import numpy as np
#Elements of digits [0,1,2,3,4,5,6,7,8,9] rescaled to fit random walk
array=[-9,-7,-5,-3,-1,1,3,5,7,9]
#steps, in single random walk, x walks to intercept, number of trial to find intercept
steps=2500
xwalks=3
trials=1500
#Set output array to zero
count=np.full([steps],0)
for n in range(trials):
#Identify initial array, set total array to zero
w0=np.random.choice(array,steps)
w0=np.cumsum(w0)
total=np.full([steps],0)
#Select x random walk check for intercept
for m in range(xwalks-1):
#Next current random walk
w=np.random.choice(array,steps)
w=np.cumsum(w)
#Compare previous and current random walk
eq=np.equal(w0,w)
eq=eq.astype(int)
#Count intercepts
total=total+eq
#Set current walk to previous
w0=w
#Sum all interceptions for all trials
count=count+np.where(total==(xwalks-1),1,0)
#Print output
print(count)
print(np.sum(count))
print(np.sum(count)/trials)
After studying I think I answered my own question. The method has similarities corresponding with: SE.
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$: $$\boxed{p(s)=\sum_{i=0} \left[\frac{1}{d^s} \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.
$$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$$
An empirical formula was found see; my question and first own answer (confirmation here: SE). The standard deviation is determined from a discrete uniform distribution, growing with $\sqrt{s}$ per step while a random walk SE:
Continuous method, $s\geq20$: $$\sigma=\sqrt{\frac{(d^{2}-1)}{12}}$$ $$\boxed{p(s)= \frac{1}{\sqrt { n} \cdot (\sigma \sqrt{2 \pi})^{(n-1)} } \cdot s^{-\frac{1}{2}(n-1)}} $$
Both functions: discrete and continuous have been verified in a simulation. The intersections of $n=4$ random walks where counted. Random walks were used with $d=4$ equal likely outcomes per step $[-3,-1,1,3]$. The graphs show the discrete method is practical and accurate for $s<20$ the normal approximation is useful for $s\geq20$.
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 (\sigma \sqrt{2 \pi})^{(n-1)} } \cdot \sum\limits_{s=1}^{\infty}s^{- \frac{1}{2}(n-1)}$$
$$p(n)=\frac{1}{\sqrt { n} \cdot (\sigma \sqrt{2 \pi})^{(n-1)} } \cdot\zeta(\small{\frac{1}{2}(n-1)} \normalsize) $$
For $n\leq3$ point intersecting random walks the series diverges resulting in infinite intersections. For $n\geq4$ the series converges resulting in finite number of intersections. This recurrence and transience is also seen with random walks returning to the origin (one more degree of freedom) and related to Markov processes.
Interesting is that $n=2$ intersecting random walks coincides with the critical line on the Riemann Zeta function.