Consider two independent and identically distributed random vectors of dimensionality $N$, $\mathbf{x}$ and $\mathbf{y}$, where their elements are iid generated from a Gaussian with zero mean and variance equal to $\sigma^2$; i.e., $\mathbf{x} , \mathbf{y} \sim \mathcal{N}(0, \sigma^2)$.

What is the probability that $\mathrm{sign}(\mathbf{x})=(\mathrm{sign(x_1)},\mathrm{sign(x_2)}, \ldots, \mathrm{sign(x_N)})$ be equal to $\mathrm{sign}(\mathbf{y})=(\mathrm{sign(y_1)},\mathrm{sign(y_2)}, \ldots, \mathrm{sign(y_N)})$ if their Euclidean distance is smaller than $r$, $r \geq 0$: $\Pr\left[ \mathrm{sign}(\mathbf{x})=\mathrm{sign}(\mathbf{y})\ \vert\ \Vert \mathbf{x} - \mathbf{y} \Vert \leq r\right]$.

Note: $\mathbf{x}$ and $\mathbf{y}$ are independent.

  • 1
    $\begingroup$ I assume you meant $\Vert \mathbf{x} - \mathbf{y} \Vert$ in your last line of math? $\endgroup$ – jbowman Dec 12 '11 at 21:04
  • 2
    $\begingroup$ What kind of answer are you looking for? Even in the case $N=1$ there is no closed form solution (except possibly for special values of $r/\sigma$). $\endgroup$ – whuber Dec 13 '11 at 6:20
  • $\begingroup$ @jbowman: you are right. $\endgroup$ – Farzad Dec 13 '11 at 20:15
  • $\begingroup$ @whuber: any upper or lower bound is quite good for me. $\endgroup$ – Farzad Dec 13 '11 at 20:16
  • $\begingroup$ You mean the obvious bounds of $2^{-N}$ and $1$ will be fine? $\endgroup$ – whuber Dec 13 '11 at 20:23

This is not a complete answer, but may provide you a way to go. As a hands-on-approach I suggest to perform a simulation to get an idea how the resulting property looks like and then start to derive a formula for it.

Here is such a simulation for a fixed standard deviation. Playing around with other standard deviations returned similar results.


stdev <- 1
N <- 5
trials <- 2000

resPerN <- data.frame("N"=rep(1:N,each=trials),

for(n in 1:N){
    res <- data.frame("r"=rep(-1,trials),"signum"=rep(-1,trials))

    for(i in 1:trials){
      x <- rnorm(n,0,stdev)
      y <- rnorm(n,0,stdev)
      diff <- sqrt(sum((x-y)^2))
      signum <- sum(sign(x) == sign(y)) == n
      res[i,] <- c(diff,signum)

    res <- res[order(res$r),]

    range <- (1+(n-1)*trials) : (n*trials)
    resPerN$N[range] <- n
    resPerN$r[range] <-  (res$r - min(res$r))/(max(res$r)-min(res$r))

    invprob <-  1/(cumsum(res$signum)/cumsum(1:trials))
    invprob[which(invprob == Inf)] <- 0
    resPerN$prob[range] <- (invprob - min(invprob))/(max(invprob)-min(invprob))

xyplot(prob~r,data=resPerN,groups=resPerN$N,type="b",xlab="(min-max-transformed) r",ylab="(min-max-transformed) 1/prob | <= r",auto.key=T,
par.settings=list(superpose.line = list(col = rainbow(5),lty = 1),
          superpose.symbol=list(col = rainbow(5),pch=15,cex=0.8)))

which resulted in this plot enter image description here

which indicates a (n inverse) logistic relationship.

Going further by collecting beta-coefficients and intercepts, one pair per dimension, you should be able to derive a function dependent on r. Afterwards I'd vary the standard deviation to include it into the equation.

  • $\begingroup$ There is no need to consider multiple standard deviations. Do you see why? Any answer will be a function of $N$ and $r/\sigma$ only. $\endgroup$ – cardinal Dec 14 '11 at 15:06
  • $\begingroup$ @cardinal yes I see, thank you for the hint. One can transform $N(0,\sigma^2)$ to standard normal distribution and use $||ax-ay||=a||x-y||$ $\endgroup$ – steffen Dec 14 '11 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.