Sunday, December 04, 2016

Locks in a grid problem

This is a simulation to an interesting problem about a lock. Which has n key slots. These slots are either vertical or horizontal. To open the lock these slots have to be in a particular configuration. If we put the key in one slot and turn its orientation all the other slots in that particular row and column change their configuration. Is it possible to open this lock for a particular configuration of 16 slots ? If yes then how ?
       

"""The purpose of this is to simulate the problem of locks
where when you turn on the key in the grid all the other
keys in the same row and column also turn. I represent this
by 0 and 1
One can experiment and learn that if the grid is even by even
then we can change any particular bit by"""
n = 4
a=[]
sum = 0
# It prints the whole Grid of Locks
def printMatrix(val):
for i in range(n):
print(val[i])

# It flips the entries from 0 to 1 and 1 to 0
def flip(val):
if val == 0:
return 1
return 0

# It changes the entries in a given row and column
def ChangeRowChangeColumn(a,i,j):
a[i][j]=flip(a[i][j])
for k in range(n):
a[i][k]=flip(a[i][k])
for k in range(n):
a[k][j]=flip(a[k][j])

for i in range(1,n+1):
b=[]
for j in range(1,n+1):
b.append(1)
c = b[:]
sum= sum+n
a.append(c)
del b[:]
printMatrix(a)
flag=1
while(flag == 1):
row=int(input("Enter what row you want to change ?"))
col=int(input("Enter what column you want to change?"))
ChangeRowChangeColumn(a,row,col)
printMatrix(a)
flag = int(input("Enter 0 or 1 to continue"))




Labels: ,

Friday, December 02, 2016

Bonferroni Inequality and how to think about it

Bonferroni Inequality provides a lower bound for intersection of sets in terms of the individual probability of sets. For $2$ sets. It says that $P(A \cap B)=P(A)+P(B)-1$

Main Idea: The union of sets is always smaller than the sum of the individual sets. You can basically take this as an axiom.

We start with $P(A \cup B)= P(A)+P(B)-P(A \cap B)$

as $P(A \cup B)\le 1$

$\Rightarrow 1 \ge P(A)+P(B)-P(A \cap P(B))$

$P(A \cap B) \ge P(A)+P(B)-1$

Let's generalize it for

$P(A_1 \cap A_2 \cap \ldots \cap A_n)=P((A_1^c \cup A_2^c \cup\ldots \cup A_n^c)^c)$

Lets start with  the idea that probability of union of sets is always smaller than the sum of probabilities of individual sets.

$\Rightarrow P(A_1^c \cup A_2^c \cup \ldots \cup A_n^c) \le P(A_1^c)+P(A_2^c)+\ldots+P(A_n^c)$

$\Rightarrow P((A_1 \cap A_2 \cap \ldots \cap A_n)^c) \le P(A_1^c)+P(A_2^c)+\ldots+P(A_n^c)$

$\Rightarrow 1-P(A_1 \cap A_2 \ldots \cap A_n) \le 1-P(A_1)+1-P(A_2)+\ldots+1-P(A_n)$

$\Rightarrow 1-P(A_1 \cap A_2 \ldots \cap A_n) \le n-P(A_1)-P(A_2)-\ldots -P(A_n)$

$\Rightarrow P(A_1)+P(A_2)+\ldots+P(A_n)\le P(A_1 \cap A_2 \ldots \cap A_n)+n-1$

Labels: ,

Wednesday, November 30, 2016

Coupon Collector Problem and Python

Collecting Coupons: This is a famous problem in Mosteller's book.
Coupons in cereal boxes are numbered 1 to 5, and a set of one of each is required for a prize. With one coupon per box, how many boxes on the average are required to make a complete set?

Here is a python program to simulate it

"""We store the outputs in a list a until we get all the coupons
The coupons are generated from the randint function which generates
both the end values
The sum variable keep tracks of number of boxes we have been counting
"""
import random
flag = 1
a=[]
sum = 0
n = 1000 # number of times you want to run the experiment
coupNum = 30 # number of different coupons
for i in range(n):
count = 0
a=[]
flag =1
while flag:
x=random.randint(1,coupNum)
#generates random number between 1 and coupNum inclusive
count += 1
#        print(x)
if x not in a:
a.append(x)
flag = 1
elif len(a)==coupNum:
flag=0
#    print(count)
sum = sum+count
#    print(a,count,sum)
del a[:] #delete the list
print(sum/n)

Labels: , ,

Odds of Craps

Craps

The game of craps, played with two dice, is one of America's fastest and most popular gambling games. Calculating the odds associated with it is an instructive exercise. The rules are these. Only totals for the two dice count. The player throws the dice and wins at once if the total for the first throw is 7 or 11, loses at once if it is 2, 3 or 12. Any other throw is called his "point". If the first throw is a point, the player throws the dice repeatedly until he either wins by throwing his point again or loses by throwing 7. What is the player's chance to win.

Python Program to find the final probability
sum = 8/36
a = {4:3/36,5:4/36,6:5/36,8:5/36,9:4/36,10:3/36}
for i in a:
sum = sum+6*(a[i])**2/(6*a[i]+1)
print(sum)

Labels: , ,

Friday, November 18, 2016

Prisoner hat problem

This is a problem about a prison where an evil wizard comes and tell the 64 inmates there that tomorrow he will come and put a hat of either black or white color on their head after making them stand in a line. So that they can only see the prisoners in front of them and their hat. He would then start from the inmate at the very end who can see everyone else's hat except for his own. He would ask each of them what color is their hat. They can only answer black or white and no other words. If they are correct he would leave them otherwise he will kill them. They have a whole night to plan their strategy once he puts them in line they cannot communicate.

The problem is to find out a strategy which would allow maximum number of inmates to escape death.

[sourcecode language="python"]
# -*- coding: utf-8 -*-
"""
Created on Wed Nov 16 21:03:20 2016

@author: Sumant
The hats take the input as a STRING of Black and White
Black: Represents even number of black hats
White: Represents odd number of black hats
Black = 1
White = 0
def whatTheySee()
returns an array which contains the parity of black hats they see in front
of them

def whatTheySay()
returns an array which contains what they say

Algorithm: WhatTheySay
We need to use the array whatTheySee and we return an array which contains
what each person should say: except for the first entry which corresponds to
the last number we see. All others are always correct.
The nth position of the array we return populates itself with the responses
of previous n-1 responses and add what the parity of black hats the person
standing at nth position sees.

Input: WWWWBB
Output: WWWWBB

Input: BBBBB
Output: BBBBB

Input: BBBB
Output: WBBB

Input: BWBWBB
Output: WWBWBB
"""

hats="BWBWBB"

def binaryTohat(hat):
change=[]
for i in hat:
if i == 1:
change.append('B')
else:
change.append('W')
return change

def hatTobinary(hat):
change=[]
for i in hat:
if i == 'B':
change.append(1)
else:
change.append(0)
return change

HATS=hatTobinary(hats)

def whatTheySee(hats):

a=[]
for j in range(len(hats)):
sum = 1
for i in range(j+1,len(hats)):
sum= sum+HATS[i]
sum = sum %2
a.append(sum)

return a

def whatTheySay(hats):
a=[]
val=0
a.append(hats[0])
for i in range(1,len(hats)):
val=sum(a)+hats[i]
a.append(val%2)
return a

def stringArraytoString(st):
a=""
for i in st:
a+=i
return a
print("What wizard see",hats)
print("What they say",stringArraytoString(binaryTohat(whatTheySay(whatTheySee(HATS)))))

[/sourcecode]

Labels: ,

Wednesday, November 09, 2016

Donald Trump's Win a slap to Islamists

Donald Trump win is finally a big slap to islamists who have been infiltrating the western world and yet keeping their islamic identities. Islam is not compatible with modern view of the world and its a known fact that when muslims grow above 10 percent in any society they start to impose their sharia centric view on their hosts. A barometer test to tell if a particular muslim is a threat to a civil society is to check their views about Sharia laws. No matter how liberal they call themselves if they have any sympathy for Sharia law sooner or later they will be threat to their host. So its the first time a nation has taken a collective step to stop Sharia laws. Sharia laws are the most regressive set of laws which discriminate women, gays and atheists. Hopefully this will lead more countries to curb this barbaric, outdated laws.
Borak Obama will be remembered as one of the most charasmatic leader but his weakness to condemn Islam was the sole reason democrats lost and Trump won! The rise of islamic terrorism is so widespread and yet people till before this election were not saying the spade a spade has forever changed with this election. Officially over 60 percent of Americans have a negative view of Islam and in reality this is much higher. Hopefully Americans now can build a better society from here. They finally have a person who seems to look after American interests. Congratulations to Americans for taking this courageous step

Labels: , ,