Skip to main content
added 123 characters in body
Source Link
Will Sawin
  • 148.5k
  • 9
  • 324
  • 563

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last inequality for $\gamma \leq 1/2$.

This in particular implies that $\lim_{n\to\infty} p_{2^{cn^\alpha}, n,\gamma}=1$ for all $\gamma < 1/2$ and $\alpha<1$, as well as for $\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - \log 2 )/2$$\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - 1 )/2$ (with the logarithms to base $2$).

I would guess that this value of $c$ is actually the transition point.

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last inequality for $\gamma \leq 1/2$.

This in particular implies that $\lim_{n\to\infty} p_{2^{cn^\alpha}, n,\gamma}=1$ for all $\gamma < 1/2$ and $\alpha<1$, as well as for $\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - \log 2 )/2$.

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last inequality for $\gamma \leq 1/2$.

This in particular implies that $\lim_{n\to\infty} p_{2^{cn^\alpha}, n,\gamma}=1$ for all $\gamma < 1/2$ and $\alpha<1$, as well as for $\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - 1 )/2$ (with the logarithms to base $2$).

I would guess that this value of $c$ is actually the transition point.

Source Link
Will Sawin
  • 148.5k
  • 9
  • 324
  • 563

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last inequality for $\gamma \leq 1/2$.

This in particular implies that $\lim_{n\to\infty} p_{2^{cn^\alpha}, n,\gamma}=1$ for all $\gamma < 1/2$ and $\alpha<1$, as well as for $\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - \log 2 )/2$.