I have a 10 character string key field in a database. I&#39;ve used CRC32 to hash this field but I&#39;m worry about duplicates. Could somebody show me the probability of collision in this situation?

p.s. my string field is unique in the database. If the number of string fields is 1 million, what is probability of collision ?

Probability of collision when using a 32 bit hash

I need to normalize a list of values to fit in a probability distribution, i.e. between 0.0 and 1.0.

I understand *how* to normalize, but was curious if Python had a function to automate this.

I&#39;d like to go from:

    raw = [0.07, 0.14, 0.07]  
to  

    normed = [0.25, 0.50, 0.25]

Normalizing a list of numbers in Python

Are there any functions (as part of a math library) which will calculate [mean][1], median, mode and range from a set of numbers. 


  [1]: http://www.cimt.plymouth.ac.uk/projects/mepres/book8/bk8i5/bk8_5i2.htm

How to calculate mean, median, mode and range from a set of numbers

I need to generate a uniformly random point within a circle of radius *R*.

I realize that by just picking a uniformly random angle in the interval [0 ... 2π), and uniformly random radius in the interval (0 ... *R*) I would end up with more points towards the center, since for two given radii, the points in the smaller radius will be closer to each other than for the points in the larger radius.

I found a blog entry on this [over here](http://www.anderswallin.net/2009/05/uniform-random-points-in-a-circle-using-polar-coordinates/) but I don&#39;t understand his reasoning. I suppose it is correct, but **I would really like to understand from where he gets (2/*R*&lt;sup&gt;2&lt;/sup&gt;)&amp;times;*r* and how he derives the final solution.**

---

**Update:** 7 years after posting this question I still hadn&#39;t received a satisfactory answer on the actual question regarding the math behind the square root algorithm. So I spent a day writing an answer myself. [Link to my answer](https://stackoverflow.com/a/50746409/276052).

Generate a random point within a circle (uniformly)

This relates to an earlier question from back in June:

[Calculating expectation for a custom distribution in Mathematica][1]

I have a custom mixed distribution defined using a second custom distribution following along the lines discussed by `@Sasha` in a number of answers over the past year.

Code defining the distributions follows:

    nDist /: CharacteristicFunction[nDist[a_, b_, m_, s_], 
       t_] := (a b E^(I m t - (s^2 t^2)/2))/((I a + t) (-I b + t));
    nDist /: PDF[nDist[a_, b_, m_, s_], x_] := (1/(2*(a + b)))*a* 
       b*(E^(a*(m + (a*s^2)/2 - x))* Erfc[(m + a*s^2 - x)/(Sqrt[2]*s)] + 
         E^(b*(-m + (b*s^2)/2 + x))* 
          Erfc[(-m + b*s^2 + x)/(Sqrt[2]*s)]); 
    nDist /: CDF[nDist[a_, b_, m_, s_], 
       x_] := ((1/(2*(a + b)))*((a + b)*E^(a*x)* 
            Erfc[(m - x)/(Sqrt[2]*s)] - 
           b*E^(a*m + (a^2*s^2)/2)*Erfc[(m + a*s^2 - x)/(Sqrt[2]*s)] + 
           a*E^((-b)*m + (b^2*s^2)/2 + a*x + b*x)*
            Erfc[(-m + b*s^2 + x)/(Sqrt[2]*s)]))/ E^(a*x);         
    
    nDist /: Quantile[nDist[a_, b_, m_, s_], p_] :=  
     Module[{x}, 
       x /. FindRoot[CDF[nDist[a, b, m, s], x] == #, {x, m}] &amp; /@ p] /; 
      VectorQ[p, 0 &lt; # &lt; 1 &amp;]
    nDist /: Quantile[nDist[a_, b_, m_, s_], p_] := 
     Module[{x}, x /. FindRoot[CDF[nDist[a, b, m, s], x] == p, {x, m}]] /;
       0 &lt; p &lt; 1
    nDist /: Quantile[nDist[a_, b_, m_, s_], p_] := -Infinity /; p == 0
    nDist /: Quantile[nDist[a_, b_, m_, s_], p_] := Infinity /; p == 1
    nDist /: Mean[nDist[a_, b_, m_, s_]] := 1/a - 1/b + m;
    nDist /: Variance[nDist[a_, b_, m_, s_]] := 1/a^2 + 1/b^2 + s^2;
    nDist /: StandardDeviation[ nDist[a_, b_, m_, s_]] := 
      Sqrt[ 1/a^2 + 1/b^2 + s^2];
    nDist /: DistributionDomain[nDist[a_, b_, m_, s_]] := 
     Interval[{0, Infinity}]
    nDist /: DistributionParameterQ[nDist[a_, b_, m_, s_]] := ! 
      TrueQ[Not[Element[{a, b, s, m}, Reals] &amp;&amp; a &gt; 0 &amp;&amp; b &gt; 0 &amp;&amp; s &gt; 0]]
    nDist /: DistributionParameterAssumptions[nDist[a_, b_, m_, s_]] := 
     Element[{a, b, s, m}, Reals] &amp;&amp; a &gt; 0 &amp;&amp; b &gt; 0 &amp;&amp; s &gt; 0
    nDist /: Random`DistributionVector[nDist[a_, b_, m_, s_], n_, prec_] :=
    
        RandomVariate[ExponentialDistribution[a], n, 
        WorkingPrecision -&gt; prec] - 
       RandomVariate[ExponentialDistribution[b], n, 
        WorkingPrecision -&gt; prec] + 
       RandomVariate[NormalDistribution[m, s], n, 
        WorkingPrecision -&gt; prec];
    
    (* Fitting: This uses Mean, central moments 2 and 3 and 4th cumulant \
    but it often does not provide a solution *)
    
    nDistParam[data_] := Module[{mn, vv, m3, k4, al, be, m, si},
          mn = Mean[data];
          vv = CentralMoment[data, 2];
          m3 = CentralMoment[data, 3];
          k4 = Cumulant[data, 4];
          al = 
        ConditionalExpression[
         Root[864 - 864 m3 #1^3 - 216 k4 #1^4 + 648 m3^2 #1^6 + 
            36 k4^2 #1^8 - 216 m3^3 #1^9 + (-2 k4^3 + 27 m3^4) #1^12 &amp;, 
          2], k4 &gt; Root[-27 m3^4 + 4 #1^3 &amp;, 1]];
          be = ConditionalExpression[
              
         Root[2 Root[
               864 - 864 m3 #1^3 - 216 k4 #1^4 + 648 m3^2 #1^6 + 
                 36 k4^2 #1^8 - 
                 216 m3^3 #1^9 + (-2 k4^3 + 27 m3^4) #1^12 &amp;, 
               2]^3 + (-2 + 
               m3 Root[
                  864 - 864 m3 #1^3 - 216 k4 #1^4 + 648 m3^2 #1^6 + 
                    36 k4^2 #1^8 - 
                    216 m3^3 #1^9 + (-2 k4^3 + 27 m3^4) #1^12 &amp;, 
                  2]^3) #1^3 &amp;, 1], k4 &gt; Root[-27 m3^4 + 4 #1^3 &amp;, 1]];
          m = mn - 1/al + 1/be;
          si = 
        Sqrt[Abs[-al^-2 - be^-2 + vv ]];(*Ensure positive*)
          {al, 
        be, m, si}];
       
    nDistLL = 
      Compile[{a, b, m, s, {x, _Real, 1}}, 
       Total[Log[
         1/(2 (a + 
               b)) a b (E^(a (m + (a s^2)/2 - x)) Erfc[(m + a s^2 - 
                 x)/(Sqrt[2] s)] + 
            E^(b (-m + (b s^2)/2 + x)) Erfc[(-m + b s^2 + 
                 x)/(Sqrt[2] s)])]](*, CompilationTarget-&gt;&quot;C&quot;, 
       RuntimeAttributes-&gt;{Listable}, Parallelization-&gt;True*)];
      
    nlloglike[data_, a_?NumericQ, b_?NumericQ, m_?NumericQ, s_?NumericQ] := 
      nDistLL[a, b, m, s, data];
       
    nFit[data_] := Module[{a, b, m, s, a0, b0, m0, s0, res},
       
          (* So far have not found a good way to quickly estimate a and \
    b.  Starting assumption is that they both = 2,then m0 ~= 
       Mean and s0 ~= 
       StandardDeviation it seems to work better if a and b are not the \
    same at start. *)
       
       {a0, b0, m0, s0} = nDistParam[data];(*may give Undefined values*)
     
         If[! (VectorQ[{a0, b0, m0, s0}, NumericQ] &amp;&amp; 
           VectorQ[{a0, b0, s0}, # &gt; 0 &amp;]),
           		m0 = Mean[data];
           		s0 = StandardDeviation[data];
           		a0 = 1;
           		b0 = 2;];
       res = {a, b, m, s} /. 
         FindMaximum[
           nlloglike[data, Abs[a], Abs[b], m,  
            Abs[s]], {{a, a0}, {b, b0}, {m, m0}, {s, s0}},
                   Method -&gt; &quot;PrincipalAxis&quot;][[2]];
          {Abs[res[[1]]], Abs[res[[2]]], res[[3]], Abs[res[[4]]]}];
    
    nFit[data_, {a0_, b0_, m0_, s0_}] := Module[{a, b, m, s, res},
          res = {a, b, m, s} /. 
         FindMaximum[
           nlloglike[data, Abs[a], Abs[b], m, 
            Abs[s]], {{a, a0}, {b, b0}, {m, m0}, {s, s0}},
                   Method -&gt; &quot;PrincipalAxis&quot;][[2]];
          {Abs[res[[1]]], Abs[res[[2]]], res[[3]], Abs[res[[4]]]}];

    dDist /: PDF[dDist[a_, b_, m_, s_], x_] := 
      PDF[nDist[a, b, m, s], Log[x]]/x;
    dDist /: CDF[dDist[a_, b_, m_, s_], x_] := 
      CDF[nDist[a, b, m, s], Log[x]];
    dDist /: EstimatedDistribution[data_, dDist[a_, b_, m_, s_]] := 
      dDist[Sequence @@ nFit[Log[data]]];
    dDist /: EstimatedDistribution[data_, 
       dDist[a_, b_, m_, 
        s_], {{a_, a0_}, {b_, b0_}, {m_, m0_}, {s_, s0_}}] := 
      dDist[Sequence @@ nFit[Log[data], {a0, b0, m0, s0}]];
    dDist /: Quantile[dDist[a_, b_, m_, s_], p_] := 
     Module[{x}, x /. FindRoot[CDF[dDist[a, b, m, s], x] == p, {x, s}]] /;
       0 &lt; p &lt; 1
    dDist /: Quantile[dDist[a_, b_, m_, s_], p_] :=  
     Module[{x}, 
       x /. FindRoot[ CDF[dDist[a, b, m, s], x] == #, {x, s}] &amp; /@ p] /; 
      VectorQ[p, 0 &lt; # &lt; 1 &amp;]
    dDist /: Quantile[dDist[a_, b_, m_, s_], p_] := -Infinity /; p == 0
    dDist /: Quantile[dDist[a_, b_, m_, s_], p_] := Infinity /; p == 1
    dDist /: DistributionDomain[dDist[a_, b_, m_, s_]] := 
     Interval[{0, Infinity}]
    dDist /: DistributionParameterQ[dDist[a_, b_, m_, s_]] := ! 
      TrueQ[Not[Element[{a, b, s, m}, Reals] &amp;&amp; a &gt; 0 &amp;&amp; b &gt; 0 &amp;&amp; s &gt; 0]]
    dDist /: DistributionParameterAssumptions[dDist[a_, b_, m_, s_]] := 
     Element[{a, b, s, m}, Reals] &amp;&amp; a &gt; 0 &amp;&amp; b &gt; 0 &amp;&amp; s &gt; 0
    dDist /: Random`DistributionVector[dDist[a_, b_, m_, s_], n_, prec_] :=
       Exp[RandomVariate[ExponentialDistribution[a], n, 
         WorkingPrecision -&gt; prec] - 
           RandomVariate[ExponentialDistribution[b], n, 
         WorkingPrecision -&gt; prec] + 
        RandomVariate[NormalDistribution[m, s], n, 
         WorkingPrecision -&gt; prec]];

This enables me to fit distribution parameters and generate **PDF&#39;s** and **CDF&#39;s**.  An example of the plots:

    Plot[PDF[dDist[3.77, 1.34, -2.65, 0.40], x], {x, 0, .3}, 
     PlotRange -&gt; All]
    Plot[CDF[dDist[3.77, 1.34, -2.65, 0.40], x], {x, 0, .3}, 
     PlotRange -&gt; All]

![enter image description here][2]

Now I&#39;ve defined a `function` to calculate mean residual life (see [this question][3] for an explanation).

    MeanResidualLife[start_, dist_] := 
     NExpectation[X \[Conditioned] X &gt; start, X \[Distributed] dist] - 
      start
    MeanResidualLife[start_, limit_, dist_] := 
     NExpectation[X \[Conditioned] start &lt;= X &lt;= limit, 
       X \[Distributed] dist] - start

The first of these that doesn&#39;t set a limit as in the second takes a long time to calculate, but they both work.

Now I need to find the minimum of the `MeanResidualLife` function for the same distribution (or some variation of it) or minimize it.

I&#39;ve tried a number of variations on this:

    FindMinimum[MeanResidualLife[x, dDist[3.77, 1.34, -2.65, 0.40]], x]
    FindMinimum[MeanResidualLife[x, 1, dDist[3.77, 1.34, -2.65, 0.40]], x]
    
    NMinimize[{MeanResidualLife[x, dDist[3.77, 1.34, -2.65, 0.40]], 
      0 &lt;= x &lt;= 1}, x]
    NMinimize[{MeanResidualLife[x, 1, dDist[3.77, 1.34, -2.65, 0.40]], 0 &lt;= x &lt;= 1}, x]


These either seem to run forever or run into: 

&gt; Power::infy : Infinite expression 1/ 0. encountered. &gt;&gt;

The `MeanResidualLife` function applied to a simpler but similarly shaped distribution shows that it has a single minimum:

    Plot[PDF[LogNormalDistribution[1.75, 0.65], x], {x, 0, 30}, 
     PlotRange -&gt; All]
    Plot[MeanResidualLife[x, LogNormalDistribution[1.75, 0.65]], {x, 0, 
      30},
     PlotRange -&gt; {{0, 30}, {4.5, 8}}]

![enter image description here][4]

Also both:

    FindMinimum[MeanResidualLife[x, LogNormalDistribution[1.75, 0.65]], x]
    FindMinimum[MeanResidualLife[x, 30, LogNormalDistribution[1.75, 0.65]], x]

give me answers (if with a bunch of messages first) when used with the `LogNormalDistribution`.

Any thoughts on how to get this to work for the custom distribution described above?

Do I need to add constraints or options?

Do I need to define something else in the definitions of the custom distributions?

Maybe the `FindMinimum` or `NMinimize` just need to run longer (I&#39;ve run them nearly an hour to no avail).  If so do I just need some way to speed up finding the minimum of the function?  Any suggestions on how?

Does `Mathematica` have another way to do this?

**Added 9 Feb 5:50PM EST:** 

Anyone can download **Oleksandr Pavlyk&#39;s** presentation about creating distributions in Mathematica from the Wolfram Technology Conference 2011 workshop &#39;Create Your Own Distribution&#39; [here][5].  The downloads include the notebook, `&#39;ExampleOfParametricDistribution.nb&#39;` that seems to lays out all the pieces required to create a distribution that one can use like the distributions that come with Mathematica.

It may supply some of the answer.


  [1]: https://stackoverflow.com/questions/6296455/calculating-expectation-for-a-custom-distribution-in-mathematica
  [2]: http://i.stack.imgur.com/0ynOS.png
  [3]: https://math.stackexchange.com/questions/104494/mean-residual-life-clarification-needed
  [4]: http://i.stack.imgur.com/4IpRL.png
  [5]: http://www.wolfram.com/events/technology-conference/2011/mathematics-and-statistics.html

Minimizing NExpectation for a custom distribution in Mathematica

Say you have two hashes `H(A)` and `H(B)` and you want to combine them. I&#39;ve read that a good way to combine two hashes is to `XOR` them, e.g. `XOR( H(A), H(B) )`.

The best explanation I&#39;ve found is touched briefly here on these [hash function guidelines](http://www.javamex.com/tutorials/collections/hash_function_guidelines.shtml):

&lt;blockquote&gt;
XORing two numbers with roughly random distribution results in another number still with roughly random distribution*, but which now depends on the two values.
&lt;br/&gt;
...
&lt;br/&gt;
* At each bit of the two numbers to combine, a 0 is output if the two bits are equal, else a 1. In other words, in 50% of the combinations, a 1 will be output. So if the two input bits each have a roughly 50-50 chance of being 0 or 1, then so too will the output bit.
&lt;/blockquote&gt;

Can you explain the intuition and/or mathematics behind why XOR should be the default operation for combining hash functions (rather than OR or AND etc.)?

Why is XOR the default way to combine hashes?

Suppose that I have an *n*-sided loaded die, where each side&amp;nbsp;*k* has some probability&amp;nbsp;*p*&lt;sub&gt;*k*&lt;/sub&gt; of coming up when I roll it. I’m curious if there is a good data structure for storing this information statically (i.e., for a fixed set of probabilities), so that I can efficiently simulate a random roll of the die.

Currently, I have an O(lg&amp;nbsp;*n*) solution for this problem. The idea is to store a table of the cumulative probability of the first *k*&amp;nbsp;sides for all&amp;nbsp;*k*, then generate a random real number in the range&amp;nbsp;[0,&amp;nbsp;1) and perform a binary search over the table to get the largest index whose cumulative value is no greater than the chosen value.

I rather like this solution, but it seems odd that the runtime doesn’t take the probabilities into account. In particular, in the extreme cases of one side always coming up or the values being uniformly distributed, it’s possible to generate the result of the roll in&amp;nbsp;O(1) using a naive approach, while my solution will still take logarithmically many steps.

Does anyone have any suggestions for how to solve this problem in a way that is somehow “adaptive” in it’s runtime?

**Update:** Based on the answers to this question, I have written up **[an article describing many approaches to this problem][1]**, along with their analyses. It looks like Vose’s implementation of the alias method gives &amp;Theta;(*n*)&amp;nbsp;preprocessing time and O(1)&amp;nbsp;time per die roll, which is truly impressive.  Hopefully this is a useful addition to the information contained in the answers!


  [1]: http://www.keithschwarz.com/darts-dice-coins/

Data structures for loaded dice?

**Edit:** So basically what I&#39;m trying to write is a 1 bit hash for `double`.

I want to map a `double` to `true` or `false` with a 50/50 chance. For that I wrote code that picks some random numbers *(just as an example, I want to use this on data with regularities and still get a 50/50 result)*, checks their last bit and increments `y` if it is 1, or `n` if it is 0. 

However, this code constantly results in 25% `y` and 75% `n`. Why is it not 50/50? And why such a weird, but straight-forward (1/3) distribution?

    public class DoubleToBoolean {
    	@Test
    	public void test() {
    
    		int y = 0;
    		int n = 0;
    		Random r = new Random();
    		for (int i = 0; i &lt; 1000000; i++) {
    			double randomValue = r.nextDouble();
    			long lastBit = Double.doubleToLongBits(randomValue) &amp; 1;
    			if (lastBit == 1) {
    				y++;
    			} else {
    				n++;
    			}
    		}
    		System.out.println(y + &quot; &quot; + n);
    	}
    }

Example output:

    250167 749833

Why does this random value have a 25/75 distribution instead of 50/50?

I know there is a minute possibility of a clash but if I generated a batch of 1000 GUIDs (for example), would it be safe to assume they&#39;re all unique to save testing each one?

**Bonus question**

An optimal way to test a GUID for uniqueness? Bloom filter maybe? 

Is it safe to assume a GUID will always be unique?

Once again I was in a design review, and encountered the claim that the probability of a particular scenario was &quot;less than the risk of cosmic rays&quot; affecting the program, and it occurred to me that I didn&#39;t have the faintest idea what that probability is.

&gt; &quot;Since 2&lt;sup&gt;-128&lt;/sup&gt; is 1 out of 340282366920938463463374607431768211456, I think we&#39;re justified in taking our chances here, even if these computations are off by a factor of a few billion...  We&#39;re way more at risk for cosmic rays to screw us up, I believe.&quot;

Is this programmer correct?
What is the probability of a cosmic ray hitting a computer and affecting the execution of the program?


Cosmic Rays: what is the probability they will affect a program?

How to calculate probability in normal distribution given mean, std in Python? I can always explicitly code my own function according to the definition like the OP in this question did: https://stackoverflow.com/questions/9448246/calculating-probability-of-a-random-variable-in-a-distribution-in-python

Just wondering if there is a library function call will allow you to do this. In my imagine it would like this: 

    nd = NormalDistribution(mu=100, std=12)
    p = nd.prob(98)

There is a similar question in Perl: https://stackoverflow.com/questions/1377003/how-can-i-compute-the-probability-at-a-point-given-a-normal-distribution-in-perl. But I didn&#39;t see one in Python.

`Numpy` has a `random.normal` function, but it&#39;s like sampling, not exactly what I want.


How to calculate probability in a normal distribution given mean &amp; standard deviation?

How do I get the probability of a string being similar to another string in Python?

I want to get a decimal value like 0.9 (meaning 90%) etc. Preferably with standard Python and library.

e.g.

    similar(&quot;Apple&quot;,&quot;Appel&quot;) #would have a high prob.
    
    similar(&quot;Apple&quot;,&quot;Mango&quot;) #would have a lower prob.



Find the similarity metric between two strings

Selecting without any weights (equal probabilities) is beautifully described [here][1].

I was wondering if there is a way to convert this approach to a weighted one.

I am also interested in other approaches as well.

Update: Sampling **without** replacement

  [1]: https://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c/48089#48089

Select k random elements from a list whose elements have weights

This question has been asked in Microsoft interview. Very much curious to know why these people ask so strange questions on probability?

Given a rand(N), a random generator which generates random number from 0 to N-1.

    int A[N]; // An array of size N
    for(i = 0; i &lt; N; i++)
    {
        int m = rand(N);
        int n = rand(N);
        swap(A[m],A[n]);
    }

**EDIT:** Note that the seed is not fixed.

what is the probability that array A remains the same?    
Assume that the array contains unique elements.

What is the probability that the array will remain the same?

I was thinking of creating a chatbot using something like markov chains, but I&#39;m not entirely sure how to get it to work. From what I understand, you create a table from data with a given word and then words which follow. Is it possible to attach any sort of probability or counter while training the bot? Is that even a good idea?

The second part of the problem is with keywords. Assuming I can already identify keywords from user input, how do I generate a sentence which uses that keyword? I don&#39;t always want to start the sentence with the keyword, so how do I seed the markov chain?

How do Markov Chain Chatbots work?

I have a list of items. Each of these items has its own probability.

Can anyone suggest an algorithm to pick an item based on its probability?


How to pick an item by its probability?

Given a set of 100 different strings of equal length, how can you quantify the probability that a SHA1 digest collision for the strings is unlikely... ? 



Probability of SHA1 collisions

Is there any python package that allows the efficient computation of the PDF (probability density function) of a [multivariate normal distribution][1]?

It doesn&#39;t seem to be included in Numpy/Scipy, and surprisingly a Google search didn&#39;t turn up any useful thing.


  [1]: https://en.wikipedia.org/wiki/Multivariate_normal_distribution

Multivariate normal density in Python?

I am wondering what would be the best way (e.g. in Java) to generate random numbers within a particular range where each number has a certain probability to occur or not?

e.g.

Generate random integers from within [1;3] with the following probabilities:

P(1) = 0.2&lt;br&gt;
P(2) = 0.3&lt;br&gt;
P(3) = 0.5&lt;br&gt;

----------

Right now I am considering the approach to generate a random integer within [0;100] and do the following:

If it is within [0;20] --&gt; I got my random number 1.&lt;br&gt;
If it is within [21;50] --&gt; I got my random number 2.&lt;br&gt;
If it is within [51;100] --&gt; I got my random number 3.&lt;br&gt;
&lt;br&gt;
What would you say?

All Probability Solutions on Gang of Coders

Total of 19 Probability Solutions