# Probability of an Event

I have an identity array $S$ of length 100. That is $S[1]=1, S[2]=2, \ldots, S[100]=100.$

Now I do the following experiment:

m=0

For x=1 to 100
Take  two random integers y,z in [1,100]
if(S[x]=x and y=10)
m=1
break
S[y]=z


I want to find the probability of m=1. To calculate it, let $i$ be the value for which previous $y$ values do not touch $i$ th location of $S$ and when $x=i$, $y=10$. So probability should be $\sum_{i=1}^{100}(\frac{99}{100})^{i-1}\frac{1}{100} =0.62$. But my simulation value is 0.48.

-

## 1 Answer

A lot of your code seems redundant. For instance $x=S[x]$ is always true and $z$ never actually comes into play. All you're really doing is choosing a random integer between 1 and 100, 100 times and seeing if it's ever equal to 10. The probability of this will be one subtract the probability that $y$ is never 10 which equals $1-(\frac{99}{100})^{100}=0.634$. The simulation value could be a result of the "randomness" when choosing $y$ or the number of trials.

-
S[x]=x is not always true since I replace S[y]=z. For an example let when x=5, y=16, z=45. So when x=16, we have S[16]=45 if y not equal to 16 for 6<=x <=15 – user12290 Jun 5 '13 at 2:19
ahh, yes, you are quite right. The problem is the probability of S[x]=x is quite complicated then- did the replacement S[y]=z affect future values or past values of x? Did it affect unique values or was the same value affected more than once? If so, did this value happen to return to the original? It will be a while before I have the time to consider this properly unfortunately, but there's some stuff for you to explore yourself. – john Jun 5 '13 at 3:13