So even the combined efforts of my professor, my book and the internet have not been able to make me understand the concept of Importance Sampling.  I know that it is a way to help with estimating the probability of the occurance of very rare events, however, I have no idea how it works.  For instance, let's assume I start a random walk at $x_0=1$ and $x_i = x_{i-1}+y_i$, where $y_i=1$ with chance $p=0.2$ and $y_i=-1$ with chance $1-p=0.8$. Therefore, the random walk will probably go to lower values. I am told that IS is useful if we want to estimate the probability that the random walk will reach a high value (for instance, $100$), before reaching $0$ (the chance for this is of course at most $0.2^{100} \approx 1.27 \cdot 10^{-70}$). How would IS help for a problem like this?
31732
My background is computer science. I am fairly new to monte carlo sampling methods and, although I understand the math, I have hard time coming up with intuitive examples for importance sampling. More precisely, could someone provide examples of:    an original distribution one cannot sample from but one can estimate an importance distribution which can be sampled from and adequate for this original distribution.
23485
Problem 3: Central Limit      Consider tossing a fair coin $100n$ times, where n is geometrically distributed with mean 6. Due to a counting error, it is reported that the fraction of heads is in $[0.5,0.51]$. What is the most likely value for $n$?   We've been using the de Moivre Laplace approximation using a standardized sum.     $$ P\left(.50\times100n\leq \frac{S_n -\frac{1}{p}}{\frac{\sqrt{1-p}}{p}}\leq .51\times100n\right) = S_n \Phi(b) - \Phi(a) $$  and we start with $\frac{S_n}{n}$ and manipulate the bounds so we have $S_n^*$.  Which $\approx \Phi(285.34n) - \Phi(279.86n)$  I can't imagine this is correct. How does the Bernoulli trial enter the calculation?
110924
I was wondering if someone could explain the following passage from my textbook.    In the third paragraph from the bottom it is stated that the simulated values come from the marginal distributions. How is this so? We simulate the value x2 from the condition density f(x2|x1)..  Also, there is mention of independence and again because of the dependence of the value of x2 on x1 and so forth, I do not see how this occurs.   Would greatly appreciate your help
13560
Consider the random walk $S_n$ given by $ S_{n+1} =  \left\{   \begin{array}{l}     S_n+2 &amp; \text{with probability $p$}\\     S_n - 1 &amp; \text{with probability $1-p$}   \end{array} \right. \ $  Assume that $S_0 = n &gt;0 $. What is the probability of eventually reaching the the point $0$?  Seems that the probability for this must be less than one; since it is not symmetric, it is not guaranteed to reach the origin if $p&gt;0.5$. It also seems like the positive starting value not being at the origin matters too, but I'm not sure how to compute the probability of eventually reaching the origin.
90539
Apparently, the solution to the  is that a uniform probability distribution over the positive real numbers doesn't exist. Can anyone explain why this is the case and what probability distributions can exist over the positive real numbers (it seems that this would be quite limited, given that such a simple distribution is impossible)?
8200
I was wondering what is the best way to determine the effect of each random parameter on the result obtained from a Monte Carlo Simulation.  I realise I have asked a similar question , but this time I am making this question in a more general manner as I didn't get any answers previously.   Background: I'm essentially running a Monte Carlo Simulation where I sample randomly from 65 Normal Distributions and 2 Uniform Distributions. Then, i then input these values to a linear equation and run this for 500.000 iterations. I just wanted to determine the best way to establish the relative effect of each of these 67 (in total) random variables on the final outcome from my Monte Carlo Simulation.
116974
Can anyone explain simply why Monte-Carlo works better than naive Riemann integration in high dimensions? I do not understand how chosing randomly the points on which you evaluate the function can yield a more precise result than distributing these points evenly on the domain.  More precisely:  Let $f:[0,1]^d \to \mathbb{R}$ be a continuous bounded integrable function, with $d\geq3$. I want to compute $A=\int_{[0,1]^d} f(x)dx$ using $n$ points. Compare 2 simple methods.  The first method is the Riemann approach. Let $x_1, \dots, x_n$ be $n$ regularly spaced points in $[0,1]^d$ and $A_r=\frac{1}{n}\sum_{i=1}^n f(x_i)$. I have that $A_r \to A$ as $n\to\infty$. The error will be of order $O(\frac{1}{n^{1/d}})$.  The second method is the Monte-Carlo approach. Let $u_1, \dots, u_n$ be $n$ points chosen randomly but uniformly over $[0,1]^d$. Let $A_{mc}=\frac{1}{n}\sum_{i=1}^n f(u_i)$. The central limit theorem tells me that $A_{mc} \to A$ as $n\to \infty$ and that $A_{mc}-A$ will be in the limit a gaussian random variable centered on $0$ with variance $O(\frac{1}{n})$. So with a high probability the error will be smaller than $\frac{C}{\sqrt{n}}$ where $C$ does not depend (much?) on $d$.  An obvious problem with the Riemann approach is that if I want to increase the number of points while keeping a regular grid I have to go from $n=k^d$ to $n=(k+1)^d$ which adds a lots of points. I do not have this problem with Monte-Carlo.  But if the number of points is fixed at $n$, does Monte-Carlo really yield better results than Riemann? It seems true in most cases. But I do not understand how chosing the points randomly can be better. Does anybody have an intuitive explanation for this?
79721
Take the square $[0,1]^2$ we take $n$ random lines through the square. You can choose random lines by choosing a point on one of the sides of the squares and randomly choosing a different point on any of the other three sides and then drawing a line connecting them.   What is the probability that after $n$ of these random lines the largest region is greater than or equal to $0.5$?  Any tips or cases help, thanks.
119537
I used to work with Monte-Carlo simulations for a while. In my case, I generated random data for a variety of input parameters according to uniform distributions (with non-negative support), say for example two variables $a$ and $b$ where data is generated: $a_1, \dots, a_n \leftarrow U(1,2)$ and $b_1, \dots, b_n \leftarrow U(4,5)$.   Eventually, I evaluated a deterministic model $M$ for all generated pairs $(a_i,b_i)$ and calculate some statistics, like sample average of $\frac{M(a_1,b_1) + \dots + M(a_n,b_n)}{n}$.  Here is my question: What is the purpose of drawing random samples from the uniform distribution, rather than deterministically select $n$ equally distributed point from the interval $[1,2]$ and $[4,5]$ respectively and simply evaluate $M$ with those points? So, what would be the purpose of doing this stochastically rather than deterministically?
72516
Having read a little about exchangeability, I went back to thinking about the iid condition required for the central limit theorem. It struck me that if two random variables are drawn from an identical distribution, the occurrence of one event does not make it more or less probable for the occurrence of another event. I have no doubts that I am wrong and there is a reason why both independence and identical distribution are required. I just don't know why!
83100
A subset of $\{1, 2, 3, \dots, 20\}$ containing 10 elements is chosen at random. The largest element of this subset is noted. Find the expected value of the largest element.  I tried to solve this problem by finding the probability of each element being the largest one, but I got confused and would like some help. :)
17348
I have this question that I don't know where to begin, any help will be greatly appreciated.  Consider the following random experiment. Toss a coin until the same number of heads and tails have been observed. Take as random variable, X, the observed number of heads (or tails). Determine the first few values in the probability distribution and calculate  $\sum^{5}_{n=1} nP (X = n)$  I'm not sure exactly where to start, if someone could point me in the right direction that would be great! thanks
20329
Suppose we flip a coin until we see a head. What is the expected value of the number of flips we will take?  I am pretty new to expected value, so I tried to evaluate it by multiplying the probability of each scenario with the number of flips it took to get there (like taking the arithmetic mean). This didn't work though, because of the infinite possibilities. I'm really confused, and if someone were to provide an answer, I would really appreciate it if they could go into detail.
17501
give a simple symmetric random walk, denote $\mathbb P_0(T_1 &lt; \infty)$ the probability that starting at $0$ and the first time reaching level 1 within finite discrete time steps. What is $\mathbb P_0(T_1 &lt; \infty)$?  So can I assume that it hits level $1$ within $n$ steps, then use the hitting time thm to calculate the probability? Or is there another way to this?
92546
I have a symmetric random walk that starts at the origin. With probability $1/6$ it goes right by one and with probability $1/6$ it goes left by one. With probability $4/6$ it stays put.  After $n$ time steps, what is the probability that it is at the origin?  The answer should be the probability that you go left by the same amount you go right.  I am having difficulty working this out however.
23566
I read upon  Gambler’s Ruin problem and encountered this interesting question. Consider a simple random walk on $\{0, 1, \ldots, N\}$ with absorbing barriers at $0$ and $N$. What is the probability $u_k$ that the walk is absorbed at $N$ if it begins at a point $k$, $0 \leq k \leq N$?  If the question doesn't indicate anything, does it mean this is symmetric? If so, would it be $u_k=\left(\frac{1}{2}\right)^{(N-k)}$?
96192
I am modeling a random variable ($Y$) which is the sum of some ~15-40k independent Bernoulli random variables ($X_i$), each with a different success probability ($p_i$). Formally, $Y=\sum X_i$ where $\Pr(X_i=1)=p_i$ and $\Pr(X_i=0)=1-p_i$.  I am interested in quickly answering queries such as $\Pr(Y&lt;=k)$ (where $k$ is given).  Currently, I use random simulations to answer such queries. I randomly draw each $X_i$ according to its $p_i$, then sum all $X_i$ values to get $Y&#39;$. I repeat this process a few thousand times and return the fraction of times $\Pr(Y&#39;\leq k)$.  Obviously, this is not totally accurate (although accuracy greatly increases as the number of simulations increases). Also, it seems I have enough data about the distribution to avoid the use simulations. Can you think of a reasonable way to get the exact probability $\Pr(Y\leq k)$?  p.s.  I use Perl &amp; R.  EDIT  Following the responses I thought some clarifications might be needed. I will shortly describe the setting of my problem. Given is a circular genome with  circumference c and a set of n ranges mapped to it. For example, c=3*10^9 and ranges={[100,200],[50,1000],[3*10^9-1,1000],...}. Note all ranges are closed (both ends are inclusive). Also note that we only deal with integers (whole units).  I am looking for regions on the circle that are undercovered by the given n mapped ranges. So to test whether a given a range of length x on the circle is undercovered, I test the hypothesis that the n ranges are mapped randomly. The probability a mapped range of length q&gt;x will fully cover the given range of length x is (q-x)/c. This probability becomes quite small when c is large and/or q is small. What I'm interested is the number of ranges (out of n) which cover x. This is how Y is formed.   I test my null hypothesis vs. one sided alternative (undercoverage). Also note I am testing multiple hypothesis (different x lengths), and sure to correct for this.