Skip to main content
added 262 characters in body
Source Link
Sal
  • 4.8k
  • 1
  • 7
  • 25

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{-iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of. If it were the case that we draw $n$ draws oftimes from $Q$. The, the distribution of the maximum iswould be

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which the expectation is

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

which is correct if the draws are independent- I am uncertain if this last part is the correct model for the problem in OP because it seems the $n$ draws from $Q$ are not independent there.

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral awaiting in (12)

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{-iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{-iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum. If it were the case that we draw $n$ times from $Q$, the distribution of the maximum would be

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which the expectation is

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

which is correct if the draws are independent- I am uncertain if this last part is the correct model for the problem in OP because it seems the $n$ draws from $Q$ are not independent there.

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral awaiting in (12)

added 1 character in body
Source Link
Sal
  • 4.8k
  • 1
  • 7
  • 25

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{iqt} \varphi_Q(t) $$$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{-iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{-iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

added 3 characters in body
Source Link
Sal
  • 4.8k
  • 1
  • 7
  • 25

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

$L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

Large $n$ asymptotics

Let $S$ be the position of a random walk with steps $X_j$ which are uniformly distributed unit vectors :

$$\tag{1} S=\sum\limits_{j=1}^nX_j $$

Then using the multivariate CLT the distribution of $S$ as $n\to\infty$ is a multivariate Gaussian

$$\tag{2} f_S(s)=\frac{\exp\left(-sM^{-1}s/2 \right)}{\sqrt{(2\pi)^k|M|}} $$

where $M$ is the covariance matrix, $|M|$ is the determinant, and $s \in \mathbb{R}^k$. By symmetry we have for the components $X_j^m$ of each vector $X_j$

$$\tag{3} \mathbb{E}(X_j^mX_j^{m'})=\alpha\delta_{mm'} $$

where $\delta$ is the Kroneckar delta and $\alpha$ is a constant. Using (3) we have $M=\mathbb{I}\alpha$. To find the radial distribution of $r=|s|$ we integrate (2) over the hypersphere $S_{k-1}(r)$ yielding

$$\tag{4} f_R(r)=\frac{2\pi^{k/2}r^{k-1}}{\Gamma(k/2)}\frac{\exp\left(-r^2/2\alpha \right)}{\sqrt{(2\pi\alpha)^k}} $$

To determine $\alpha$ we use $\mathbb{E}(X_iX_j)=\delta_{ij}$ with (1) to show $\mathbb{E}(S^2)=n$ then compare to $\mathbb{E}(r^2)=\int_0^\infty dr \ r^2 f_R(r)$ using (4). The result is $\alpha=n/k$. Finally we may evaluate

$$\tag{6} \mathbb{E}(|S|)=\mathbb{E}(r)=\int\limits_0^\infty dr \ r f_R(r) = \sqrt{\frac{2n}{k}}\frac{\Gamma((1+k)/2)}{\Gamma(k/2)} $$

which is identical to the analogous result for the random walk on a lattice!

If we argue that your expression: $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle$ is asymptotically equal to $\mathbb{E}(|S|)$ then we have the large $n$ behavior (as done in the answer by @Chris Sanders).

Finite $n$

We can expand the quantity $Q$ within the maximum

$$\tag{7} Q=X_i\cdot S = 1 + \sum\limits_{j\neq i} X_i \cdot X_j $$

If $L=X_i\cdot X_j$ then $L_j=Y\cdot X_j$ has the same distribution as $L$ with $Y$ a fixed unit vector $(1,0,0,\cdots)$, so that

$$\tag{8} Q=1+\sum\limits_{j=1}^{n-1} L_j $$

I will describe in principle how I think we can find the distribution of $\text{max}(Q)$. The distribution of the dot product of unit vectors is known:

$$\tag{9} f_L(l)=\frac{\Gamma \left(\frac{k}{2}\right)}{\sqrt{\pi }\, \Gamma \left(\frac{k-1}{2}\right)}\,\left(1-l^2\right)^{\frac{k-3}{2}}\qquad , \qquad |l|<1 $$

To find the distribution of a sum, we can use the characteristic function

$$\tag{10} \varphi_L(t)=\mathbb{E}(e^{itL})=\int\limits_{-1}^1 dl \ f_L(l) e^{itl} $$

which a CAS evaluates to hypergeometricFPQ functions$^\dagger$. The characteristic function of $Q$ is

$$\tag{11} \varphi_Q(t)=e^{it}[\varphi_L(t)]^{n-1} $$

so that we have

$$\tag{12} f_Q(q)=\frac{1}{2\pi}\int\limits_{-\infty}^\infty dt \ e^{iqt} \varphi_Q(t) $$

from which the CDF $F_Q$ may be found. Then we need to take care of the maximum of $n$ draws of $Q$. The distribution of the maximum is

$$\tag{13} f_+(q)=nf_Q(q)[F_Q(q)]^{n-1} $$

from which

$$\tag{14} \mathbb{E}(Q_\text{max})=\int dq \ q f_+(q) $$

From (12) onwards, I suspect that analytical progress will be very difficult, but at least the steps are possible numerically.

$\dagger$ Actually the result simplifies to Bessel $J$ functions in even dimensions and sums of trig functions in odd dimensions. I do not dwell on this because of the formidable integral in (12)

added 212 characters in body
Source Link
Sal
  • 4.8k
  • 1
  • 7
  • 25
Loading
Source Link
Sal
  • 4.8k
  • 1
  • 7
  • 25
Loading