# Difference between revisions of "User:Jzhang/Segment2"

(→Activity 1) |
(→Activity 2) |
||

(13 intermediate revisions by the same user not shown) | |||

Line 40: | Line 40: | ||

Here's the python code: | Here's the python code: | ||

<pre> | <pre> | ||

+ | import pylab | ||

+ | import numpy | ||

import random | import random | ||

b1 = [1,1,1,1,1] | b1 = [1,1,1,1,1] | ||

Line 49: | Line 51: | ||

cTroll = 0 | cTroll = 0 | ||

cSafe = 0 | cSafe = 0 | ||

+ | frac_list = [] | ||

for i in range (10**5): | for i in range (10**5): | ||

− | # choose the | + | # choose the world |

bc = world[random.randint(0,4)] | bc = world[random.randint(0,4)] | ||

# capture one random specie | # capture one random specie | ||

Line 57: | Line 60: | ||

if capture < 0: # capture the troll | if capture < 0: # capture the troll | ||

cTroll+=1 | cTroll+=1 | ||

− | if sum(bc)-capture == 4: # | + | if sum(bc)-capture == 4: # cross safely |

cSafe+=1 | cSafe+=1 | ||

+ | |||

+ | # record fraction at every step | ||

+ | if not cTroll: | ||

+ | frac_list.append(0) | ||

+ | else: | ||

+ | frac_list.append(cSafe*1.0/cTroll) | ||

+ | |||

+ | |||

+ | # plot the fraction verse the simulation time | ||

+ | x = numpy.arange(0,10**5,1) | ||

+ | |||

+ | pylab.plot(x,frac_list) | ||

+ | pylab.xlabel('simulation times') | ||

+ | pylab.ylabel('fraction') | ||

+ | pylab.grid(True) | ||

+ | pylab.show() | ||

− | |||

print cSafe | print cSafe | ||

print cTroll | print cTroll | ||

print cSafe*1.0/cTroll | print cSafe*1.0/cTroll | ||

+ | </pre> | ||

+ | |||

+ | The calculated fraction is 0.329046526868.<br/> | ||

+ | The plot is shown here: | ||

+ | |||

+ | [[ Image: Frac vs simulation.png ]] | ||

+ | |||

+ | ===Activity 2=== | ||

+ | *You are an oracle that, when asked, says "yes“ with probability ½ and "no" with probability ½. How do you do this using only a coin that comes up heads with unknown but constant probability P?<br/> | ||

+ | |||

+ | *Simulate your scheme to confirm that it works.<br/> | ||

+ | |||

+ | |||

+ | The initial idea is roughly estimate the p first, and deduce some hypothesis that has an probability of 1/2. | ||

+ | |||

+ | The p can be estimated by flipping the coins a couple of thousand times and calculate the fraction of the times with head facing up. | ||

+ | And then, we can create an artifical case, such as through coin n times, the chance that the first n-1 time the coin is tail and the nth time it's head is following the geometrical distribution: | ||

+ | |||

+ | <math> P = (1-p)^np</math> <br/> | ||

+ | Since we has the estimation of p, we can solve the n in the equation | ||

+ | <math> P = 1/2 </math> | ||

+ | |||

+ | Now we know if we flip the coin n times, the chance of the first n-1 time being tail and last time being head is 1/2, so if this happened, we say yes, otherwise we say know. | ||

+ | |||

+ | '''comment'''<br/> | ||

+ | The problem about this idea is that the n we solve is not necessary to be a number larger than 1 or even positive, for example if p is 0.9, the n we solve is -14.27, there's no way we can flip -14 times. | ||

+ | |||

+ | This fits sorts to the idea of transformation. | ||

+ | |||

+ | The implementation of the really elegant way of solving this problem with rejection is here: | ||

+ | <pre> | ||

+ | import random | ||

+ | |||

+ | # given probability | ||

+ | p=random.random() | ||

+ | |||

+ | # flip coins twice each round, only count the times of tail/head or head/tail | ||

+ | |||

+ | yes=0 | ||

+ | no=0 | ||

+ | |||

+ | for i in range(10**6): | ||

+ | |||

+ | # flip coin for the first time | ||

+ | if random.random() < p: | ||

+ | r1 = 1 | ||

+ | else: | ||

+ | r1 = 0 | ||

+ | |||

+ | # flip coin for the second time | ||

+ | if random.random() < p: | ||

+ | r2 = 1 | ||

+ | else: | ||

+ | r2 = 0 | ||

+ | |||

+ | # head/tail or tail/head | ||

+ | if r1 + r2 == 1: | ||

+ | if r1: | ||

+ | yes+=1 | ||

+ | else: | ||

+ | no+=1 | ||

+ | |||

+ | print p | ||

+ | print yes | ||

+ | print no | ||

+ | print yes*1.0/(yes+no) | ||

</pre> | </pre> |

## Latest revision as of 20:37, 18 January 2013

Solutions for segment 2.

## Contents

- 1 Skilled problem
- 1.1 Problem 1: If the knight had captured a Gnome instead of a Troll, what would his chances be of crossing safely?
- 1.2 Problem 2: Suppose that we have two identical boxes, A and B. A contains 5 red balls and 3 blue balls. B contains 2 red balls and 4 blue balls. A box is selected at random and exactly one ball is drawn from the box. What is the probability that it is blue? If it is blue, what is the probability that it came from box B?

- 2 Thought problem

## Skilled problem

### Problem 1: If the knight had captured a Gnome instead of a Troll, what would his chances be of crossing safely?

Let

<math>H_1</math> be the hypothesis that he is on bridge without troll

<math>H_2</math> be that he is on bridge with one troll

<math>H_3</math> be that he is on bridge with two trolls

The probability of crossing safely(or on the bridge without troll) is:

<math> P(H_1|G) = \frac{P(G|H_1)*P(H_1)}{P(G)} = \frac{P(G|H_1)*P(H_1)}{P(GH_1)+P(GH_2)+P(GH_3)} = \frac{1*\frac{3}{5}}{1*\frac{3}{5}+\frac{4}{5}*\frac{1}{5}+\frac{3}{5}*\frac{1}{5}} = \frac{15}{22}</math>

### Problem 2: Suppose that we have two identical boxes, A and B. A contains 5 red balls and 3 blue balls. B contains 2 red balls and 4 blue balls. A box is selected at random and exactly one ball is drawn from the box. What is the probability that it is blue? If it is blue, what is the probability that it came from box B?

The probability of be blue ball is:
<math> P(b) = P(bA)+P(bB) = \frac{1}{2}*\frac{3}{8}+\frac{1}{2}*\frac{4}{6} = \frac{25}{48}</math>

The probability of being box B given blue ball is:
<math> P(B|b) = \frac{P(b|B)*P(B)}{P(b)} = \frac{16}{25}</math>

## Thought problem

All the work is done in team with Sean Trettel

### Activity 1

- Simulate the Knight/Troll/Gnome problem 100,000 times.

- Plot (fraction of safe crossings so far) vs. (number of simulated trials so far) to confirm that this fraction converges to the probability calculated in the segment.

The idea is simulating the whole world with a list of bridges, each bridge is represented with a list, there're five species on each bridge, which are represented with 5 numbers in the list, 1 means Gnome, -1 means Troll.

In each run of the simulation, a random integer number between 0~4 will determine which bridge the knight is on, and another random integer number between 0~4 will determine which specie the knight capture. If the knight capture a Troll, the number of capturing Troll is incremented, and whether he can cross safely is calculated (If the rest four species are Gnomes, it's safe) by summing rest of the list, if it's equal to 4, there're 4 Gnomes left, it's safe, and number that he can cross safely is incremented.

Here's the python code:

import pylab import numpy import random b1 = [1,1,1,1,1] b2 = [-1,1,1,1,1] b3 = [-1,-1,1,1,1] world = [b1,b1,b1,b2,b3] cTroll = 0 cSafe = 0 frac_list = [] for i in range (10**5): # choose the world bc = world[random.randint(0,4)] # capture one random specie capture = bc[random.randint(0,4)] if capture < 0: # capture the troll cTroll+=1 if sum(bc)-capture == 4: # cross safely cSafe+=1 # record fraction at every step if not cTroll: frac_list.append(0) else: frac_list.append(cSafe*1.0/cTroll) # plot the fraction verse the simulation time x = numpy.arange(0,10**5,1) pylab.plot(x,frac_list) pylab.xlabel('simulation times') pylab.ylabel('fraction') pylab.grid(True) pylab.show() print cSafe print cTroll print cSafe*1.0/cTroll

The calculated fraction is 0.329046526868.

The plot is shown here:

### Activity 2

- You are an oracle that, when asked, says "yes“ with probability ½ and "no" with probability ½. How do you do this using only a coin that comes up heads with unknown but constant probability P?

- Simulate your scheme to confirm that it works.

The initial idea is roughly estimate the p first, and deduce some hypothesis that has an probability of 1/2.

The p can be estimated by flipping the coins a couple of thousand times and calculate the fraction of the times with head facing up. And then, we can create an artifical case, such as through coin n times, the chance that the first n-1 time the coin is tail and the nth time it's head is following the geometrical distribution:

<math> P = (1-p)^np</math>

Since we has the estimation of p, we can solve the n in the equation
<math> P = 1/2 </math>

Now we know if we flip the coin n times, the chance of the first n-1 time being tail and last time being head is 1/2, so if this happened, we say yes, otherwise we say know.

**comment**

The problem about this idea is that the n we solve is not necessary to be a number larger than 1 or even positive, for example if p is 0.9, the n we solve is -14.27, there's no way we can flip -14 times.

This fits sorts to the idea of transformation.

The implementation of the really elegant way of solving this problem with rejection is here:

import random # given probability p=random.random() # flip coins twice each round, only count the times of tail/head or head/tail yes=0 no=0 for i in range(10**6): # flip coin for the first time if random.random() < p: r1 = 1 else: r1 = 0 # flip coin for the second time if random.random() < p: r2 = 1 else: r2 = 0 # head/tail or tail/head if r1 + r2 == 1: if r1: yes+=1 else: no+=1 print p print yes print no print yes*1.0/(yes+no)