Return to Question

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.

Let me start the discussion with deterministic algorithms. Suppose I use some iterative algorithm to compute say the $\sqrt{2}$ (for example, using Newton's method) and I claim that if I run $n$ iterations of the algorithm, then the answer I obtain has an error of at most $\epsilon_n$. The precise meaning of this statement is that $$ |x_n - \sqrt{2}| \leq \epsilon_n,$$ where $x_n$ is the answer I get in the $n^{th}$ iteration.

Now suppose I have some iterative Monte Carlo algorithm. To take a simple example, suppose I want to compute the value of $\pi$ using the well known Monte Carlo algorithm: consider a square of side length $1$ and at each iteration, generate a pair of random numbers between $0$ and $1$. Check whether the point lies inside the circle quadrant or not. After $n$ iterations, calculate the fraction of points that are inside that circle quadrant. Call this number $\frac{\pi_n}{4}$.

$\textbf{Question 1:}$ What is a meaningful question one can ask about $\pi_n$? Saying something like $$ |\pi - \pi_n| \leq \epsilon_n $$
doesn't make any sense, because there is a small chance that $\epsilon_n$ could we very big (even if $n$ is very large).

$\textbf{Note:}$ To keep things simple let us assume that the random numbers we produce are "truly random" (whatever that means).

$\textbf{Question 2}:$ I now have a more specific question. It seems that using a Monte Carlo algorithm (called the Pivot Method), one can numerically compute the connective constant of a lattice (for this discussion it doesn't matter too much what connective constant means except that its a real number, so I won't bother defining it). Now consider the following statement:

The connective constant ($\mu$) of the square lattice upto two decimal places is $2.63$.

What does this statement mean? If that $2.63$ was obtained by an ordinary algorithm, then it would have meant $$|\mu-2.63| \leq 0.01. $$ But this $2.63$ was obtained by a Monte Carlo Algorithm. So its not clear to me what is actually meant by saying a number has been computed to some accuracy.

A discussion on connective constant (and their known numerical values) is available in the wikipedia page

http://en.wikipedia.org/wiki/Connective_constant

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.

Let me start the discussion with deterministic algorithms. Suppose I use some iterative algorithm to compute say the $\sqrt{2}$ (for example, using Newton's method) and I claim that if I run $n$ iterations of the algorithm, then the answer I obtain has an error of at most $\epsilon_n$. The precise meaning of this statement is that $$ |x_n - \sqrt{2}| \leq \epsilon_n,$$ where $x_n$ is the answer I get in the $n^{th}$ iteration.

Now suppose I have some iterative Monte Carlo algorithm. To take a simple example, suppose I want to compute the value of $\pi$ using the well known Monte Carlo algorithm: consider a square of side length $1$ and at each iteration, generate a pair of random numbers between $0$ and $1$. Check whether the point lies inside the circle quadrant or not. After $n$ iterations, calculate the fraction of points that are inside that circle quadrant. Call this number $\frac{\pi_n}{4}$.

$\textbf{Question 1:}$ What is a meaningful question one can ask about $\pi_n$? Saying something like $$ |\pi - \pi_n| \leq \epsilon_n $$
doesn't make any sense, because there is a small chance that $\epsilon_n$ could we very big (even if $n$ is very large).

$\textbf{Note:}$ To keep things simple let us assume that the random numbers we produce are "truly random" (whatever that means).

$\textbf{Question 2}:$ I now have a more specific question. It seems that using a Monte Carlo algorithm (called the Pivot Method), one can numerically compute the connective constant of a lattice (for this discussion it doesn't matter too much what connective constant means except that its a real number, so I won't bother defining it). Now consider the following statement:

The connective constant ($\mu$) of the square lattice upto two decimal places is $2.63$.

What does this statement mean? If that $2.63$ was obtained by an ordinary algorithm, then it would have meant $$|\mu-2.63| \leq 0.005. $$ But this $2.63$ was obtained by a Monte Carlo Algorithm. So its not clear to me what is actually meant by saying a number has been computed to some accuracy.

A discussion on connective constant (and their known numerical values) is available in the wikipedia page

http://en.wikipedia.org/wiki/Connective_constant

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.

Let me start the discussion with deterministic algorithms. Suppose I use some iterative algorithm to compute say the $\sqrt{2}$ (for example, using Newton's method) and I claim that if I run $n$ iterations of the algorithm, then the answer I obtain has an error of at most $\epsilon_n$. The precise meaning of this statement is that $$ |x_n - \sqrt{2}| \leq \epsilon_n,$$ where $x_n$ is the answer I get in the $n^{th}$ iteration.

Now suppose I have some iterative Monte Carlo algorithm. To take a simple example, suppose I want to compute the value of $\pi$ using the well known Monte Carlo algorithm: consider a square of side length $1$ and at each iteration, generate a pair of random numbers between $0$ and $1$. Check whether the point lies inside the circle quadrant or not. After $n$ iterations, calculate the fraction of points that are inside that circle quadrant. Call this number $\frac{3 \pi_n}{4}$.

$\textbf{Question 1:}$ What is a meaningful question one can ask about $\pi_n$? Saying something like $$ |\pi - \pi_n| \leq \epsilon_n $$
doesn't make any sense, because there is a small chance that $\epsilon_n$ could we very big (even if $n$ is very large).

$\textbf{Note:}$ To keep things simple let us assume that the random numbers we produce are "truly random" (whatever that means).

$\textbf{Question 2}:$ I now have a more specific question. It seems that using a Monte Carlo algorithm (called the Pivot Method), one can numerically compute the connective constant of a lattice (for this discussion it doesn't matter too much what connective constant means except that its a real number, so I won't bother defining it). Now consider the following statement:

The connective constant of the square lattice upto two decimal places is $2.63$.

What does this statement mean? If that $2.63$ was obtained by an ordinary algorithm, then it would have meant $$|\mu-2.63| \leq 0.01. $$ But this $2.63$ was obtained by a Monte Carlo Algorithm. So its not clear to me what is actually meant by saying a number has been computed to some accuracy.

A discussion on connective constant (and their known numerical values) is available in the wikipedia page

http://en.wikipedia.org/wiki/Connective_constant

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.

Let me start the discussion with deterministic algorithms. Suppose I use some iterative algorithm to compute say the $\sqrt{2}$ (for example, using Newton's method) and I claim that if I run $n$ iterations of the algorithm, then the answer I obtain has an error of at most $\epsilon_n$. The precise meaning of this statement is that $$ |x_n - \sqrt{2}| \leq \epsilon_n,$$ where $x_n$ is the answer I get in the $n^{th}$ iteration.

Now suppose I have some iterative Monte Carlo algorithm. To take a simple example, suppose I want to compute the value of $\pi$ using the well known Monte Carlo algorithm: consider a square of side length $1$ and at each iteration, generate a pair of random numbers between $0$ and $1$. Check whether the point lies inside the circle quadrant or not. After $n$ iterations, calculate the fraction of points that are inside that circle quadrant. Call this number $\frac{\pi_n}{4}$.

$\textbf{Question 1:}$ What is a meaningful question one can ask about $\pi_n$? Saying something like $$ |\pi - \pi_n| \leq \epsilon_n $$
doesn't make any sense, because there is a small chance that $\epsilon_n$ could we very big (even if $n$ is very large).

$\textbf{Note:}$ To keep things simple let us assume that the random numbers we produce are "truly random" (whatever that means).

$\textbf{Question 2}:$ I now have a more specific question. It seems that using a Monte Carlo algorithm (called the Pivot Method), one can numerically compute the connective constant of a lattice (for this discussion it doesn't matter too much what connective constant means except that its a real number, so I won't bother defining it). Now consider the following statement:

The connective constant ($\mu$) of the square lattice upto two decimal places is $2.63$.

What does this statement mean? If that $2.63$ was obtained by an ordinary algorithm, then it would have meant $$|\mu-2.63| \leq 0.01. $$ But this $2.63$ was obtained by a Monte Carlo Algorithm. So its not clear to me what is actually meant by saying a number has been computed to some accuracy.

A discussion on connective constant (and their known numerical values) is available in the wikipedia page

http://en.wikipedia.org/wiki/Connective_constant