All Questions
Tagged with probability algorithm
422
questions
148
votes
4
answers
15k
views
Data structures for loaded dice?
Suppose that I have an n-sided loaded die, where each side k has some probability pk of coming up when I roll it. I’m curious if there is a good data structure for storing this information statically (...
- 367k
79
votes
14
answers
41k
views
Select k random elements from a list whose elements have weights
Selecting without any weights (equal probabilities) is beautifully described here.
I was wondering if there is a way to convert this approach to a weighted one.
I am also interested in other ...
- 10.2k
74
votes
15
answers
7k
views
What is the probability that the array will remain the same?
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 ...
- 9,936
57
votes
2
answers
59k
views
Probability of collision when using a 32-bit hash
I have a 10-character string key field in a database. I've used CRC32 to hash this field, but I'm worrying about duplicates. Could somebody show me the probability of collision in this situation?
P.S.:...
- 1,211
38
votes
10
answers
5k
views
An interview question: About Probability
An interview question:
Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1.
Write a function g(x) using f(x) that 1/2 times returns 0, 1/2 times returns 1.
My implementation is:
...
- 15.7k
31
votes
5
answers
20k
views
What are probabilistic data structures?
I have read about "probabilistic" data structures like bloom filters and skip lists.
What are the common characteristics of probabilistic data structures and what are they used for?
- 5,079
30
votes
4
answers
9k
views
How to generate random numbers biased towards one value in a range?
Say, if I wanted to generate an unbiased random number between min and max, I'd do:
var rand = function(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
};
But what if I ...
- 21.7k
28
votes
6
answers
13k
views
How much can you truncate a SHA1 hash and be reasonably sure of having an unique ID?
I am making an application that stores documents and gives each one a UID based on a SHA1 digest of a few things including the timestamp. The digest has a lot of characters, and I want to allow users ...
- 44.7k
26
votes
7
answers
13k
views
C puzzle: Make a fair coin from a biased coin
How can I determine the probability that a function would return 0 or 1 in the following case:
Let the function_A return 0 with
probability 40% and 1 with probability
60%. Generate a ...
- 5,194
26
votes
3
answers
21k
views
Fastest primality test
Could you suggest a fast, deterministic method that is usable in practice, for testing if a large number is prime or not?
Also, I would like to know how to use non-deterministic primality tests ...
user500944
25
votes
12
answers
6k
views
Python - Is a dictionary slow to find frequency of each character?
I am trying to find a frequency of each symbol in any given text using an algorithm of O(n) complexity. My algorithm looks like:
s = len(text)
P = 1.0/s
freqs = {}
for char in text:
try:
...
- 29.9k
24
votes
7
answers
12k
views
Computing similarity between two lists
EDIT:
as everyone is getting confused, I want to simplify my question. I have two ordered lists. Now, I just want to compute how similar one list is to the other.
Eg,
1,7,4,5,8,9
1,7,5,4,9,6
What ...
- 333
22
votes
10
answers
4k
views
Representing continuous probability distributions
I have a problem involving a collection of continuous probability distribution functions, most of which are determined empirically (e.g. departure times, transit times). What I need is some way of ...
21
votes
12
answers
21k
views
Probability distribution in Python
I have a bunch of keys that each have an unlikeliness variable. I want to randomly choose one of these keys, yet I want it to be more unlikely for unlikely (key, values) to be chosen than a less ...
21
votes
9
answers
28k
views
Optimal Algorithm for Winning Hangman
In the game Hangman, is it the case that a greedy letter-frequency algorithm is equivalent to a best-chance-of-winning algorithm?
Is there ever a case where it's worth sacrificing preservation of ...
- 325
20
votes
7
answers
12k
views
Unbiased random number generator using a biased one
You have a biased random number generator that produces a 1 with a probability p and 0 with a probability (1-p). You do not know the value of p. Using this make an unbiased random number generator ...
- 18.6k
19
votes
4
answers
14k
views
Calculate the number of ways to roll a certain number
I'm a high school Computer Science student, and today I was given a problem to:
Program Description: There is a belief among dice players that in
throwing three dice a ten is easier to get than ...
- 7,328
18
votes
10
answers
30k
views
How can I efficiently calculate the binomial cumulative distribution function?
Let's say that I know the probability of a "success" is P. I run the test N times, and I see S successes. The test is akin to tossing an unevenly weighted coin (perhaps heads is a success, tails is ...
- 35.5k
18
votes
3
answers
4k
views
Probability of Outcomes Algorithm
I have a probability problem, which I need to simulate in a reasonable amount of time. In simplified form, I have 30 unfair coins each with a different known probability. I then want to ask things ...
- 183
17
votes
8
answers
12k
views
Creating your own Tinyurl style uid
I'm writing a small article on humanly readable alternatives to Guids/UIDs, for example those used on TinyURL for the url hashes (which are often printed in magazines, so need to be short).
The ...
- 65.1k
16
votes
4
answers
24k
views
Probability of 64bit Hash Code Collisions
The book Numerical Recipes offers a method to calculate 64bit hash codes in order to reduce the number of collisions.
The algorithm is shown at http://www.javamex.com/tutorials/collections/...
- 22.3k
15
votes
5
answers
4k
views
Estimating/forecasting download completion time
We've all poked fun at the 'X minutes remaining' dialog which seems to be too simplistic, but how can we improve it?
Effectively, the input is the set of download speeds up to the current time, and ...
- 20k
14
votes
5
answers
3k
views
Choose random array element satisfying certain property
Suppose I have a list, called elements, each of which does or does not satisfy some boolean property p. I want to choose one of the elements that satisfies p by random with uniform distribution. I ...
- 7,706
14
votes
6
answers
3k
views
Implementation of a simple algorithm (to calculate probability)
I've been asked (as part of homework) to design a Java program that does the following:
Basically there are 3 cards:
Black coloured on both sides
Red coloured on both sides
Black on one side, red on ...
- 143
13
votes
6
answers
6k
views
Probabilty based on quicksort partition
I have come across this question:
Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
- 2,315
13
votes
2
answers
13k
views
Algorithms/theory behind predictive autocomplete?
Simple word autocomplete just displays a list of words that match the characters that were already typed. But I would like to order the words in the autocomplete list according to the probability of ...
- 27.5k
13
votes
2
answers
2k
views
Fisher Yates variation
The classic Fisher Yates looks something like this:
void shuffle1(std::vector<int>& vec)
{
int n = vec.size();
for (int i = n - 1; i > 0; --i)
{
std::swap(vec[i], vec[...
- 260k
12
votes
7
answers
9k
views
How to implement Random(a,b) with only Random(0,1)? [duplicate]
Possible Duplicate:
how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)
In the book of Introduction to algorithms, there is an excise:
Describe an ...
- 25.6k
12
votes
4
answers
671
views
How to update a matrix of probabilities
I am trying to find/figure out a function that can update probabilities.
Suppose there are three players and each of them get a fruit out of a basket: ["apple", "orange", "...
- 1,621
12
votes
6
answers
4k
views
How to generate correlated binary variables
I need to generate a series of N random binary variables with a given correlation function. Let x = {xi} be a series of binary variables (taking the value 0 or 1, i running from 1 to N). The marginal ...
- 935
11
votes
6
answers
3k
views
How do I generate points that match a histogram?
I am working on a simulation system. I will soon have experimental data (histograms) for the real-world distribution of values for several simulation inputs.
When the simulation runs, I would ...
- 35k
11
votes
1
answer
343
views
Creating all strongly connected graphs with given in-degree with equal probability
I am looking for a way to sample uniformly from the space of all strongly connected directed graphs (without self-loops) of n nodes and in-degree k=(k_1,...,k_n), 1 <= k_i <= n-1.
Input
n, the ...
- 143
10
votes
4
answers
12k
views
An algorithm to calculate probability of a sum of the results happening
The algorithm I'm talking about using would allow you to present it with x number of items with each having a range of a to b with the result being y. I would like to have an algorithm which would, ...
- 5,078
10
votes
1
answer
607
views
Space-efficient probabilistic data structures for number retrieval
Consider we have an algorithm that receives a hypothetically long stream of keys. It then generates a value between 0 and 1 for each key, as we process it, for posterior retrieval. The input set is ...
- 93.9k
9
votes
2
answers
8k
views
randomized quicksort: probability of two elements comparison?
I am reading "Probability and Computing" by M.Mitzenmacher and E.Upfal. I am having problems understanding how the probability of comparison of two elements is calculated.
Input: sorted list (y1,y2,.....
- 131
9
votes
3
answers
2k
views
What is the optimal winning strategy for this modified blackjack game?
Questions
Is there a best value to stay on so that I win the greatest percentage of games possible? If so, what is it?
Edit: Is there an exact probability of winning that can be calculated for a ...
- 29.1k
9
votes
2
answers
990
views
Probability of finding the median with finite space
This is a spin off of this StackOverflow question.
Assume that you have a fixed number k of storage locations, and space for two counters. You will receive n items in random order (all permutations ...
- 18.6k
9
votes
1
answer
552
views
Probability computation and algorithm for subsequences
Here is a game where cards 1-50 are distributed to two players each having 10 cards which are in random order. Aim is to sort all the cards and whoever does it first is the winner. Every time a person ...
- 2,726
8
votes
4
answers
5k
views
Computing a binomial probability for huge numbers
I want to compute binomial probabilities on python. I tried to apply the formula:
probability = scipy.misc.comb(n,k)*(p**k)*((1-p)**(n-k))
Some of the probabilities I get are infinite. I checked ...
- 2,143
8
votes
7
answers
15k
views
generate random numbers within a range with different probabilities
How can i generate a random number between A = 1 and B = 10 where each number has a different probability?
Example: number / probability
1 - 20%
2 - 20%
3 - 10%
4 - 5%
5 - 5%
...and so on.
I'...
- 33k
8
votes
2
answers
167
views
What's the term to describe this combination?
There are 4 items: 1, 2, 3, and 4. If we just allow the following combinations, what should we call them? I forgot it. Is it called nCr?
1 2 3 4
1 2 3
1 2 4
2 3 4
1 2
1 3
1 4
2 3
2 4
3 4
1
2
3
4
- 903
8
votes
1
answer
1k
views
Merkle Tree Data Synchronization False Positives
Merkle trees (aka hash trees) are used for data synchronization in both "Cassandra" & "Dynamo".
As with any hash function, there is a probability that different data can have the same hash value:
...
- 3,083
8
votes
4
answers
6k
views
how to numerically sample from a joint, discrete, probability distribution function
I have a 2D "heat map" or PDF that I need to recreate by random sampling. I.E. I have a 2D probability density map showing starting locations. I need to randomly choose starting locations with the ...
- 875
8
votes
2
answers
4k
views
Algorithm for calculating probabilities of a number being drawn opening a book
I have a book with N<10000 pages, and a number x(in the range 1<=x<=40).
I want to calculate the probability that, opening that book at random, the combination of the digits of the opened ...
- 3,053
7
votes
3
answers
8k
views
Choosing n numbers with fixed sum
In some code I want to choose n random numbers in [0,1) which sum to 1.
I do so by choosing the numbers independently in [0,1) and normalizing them by dividing each one by the total sum:
numbers = [...
- 31.2k
7
votes
2
answers
1k
views
Computing the approximate population of a bloom filter
Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.
Is it possible to approximate the number of elements inserted into the bloom filter?
...
- 1,468
7
votes
5
answers
13k
views
Create constrained random numbers?
CLEANED UP TEXT:
How can I create m=5 random numbers that add upp to, say n=100. But, the first random number is say, 10 < x1 < 30, the second random nr is 5 < x2 < 20, the third random ...
- 975
7
votes
3
answers
2k
views
Group detection in data sets
Assume a group of data points, such as one plotted here (this graph isn't specific to my problem, but just used as a suitable example):
Inspecting the scatter graph visually, it's fairly obvious the ...
- 3,263
7
votes
5
answers
2k
views
Efficiently summing log quantities
Working in C++, I'd like to find the sum of some quantities, and then take the log of the sum:
log(a_1 + a_2 + a_3 + ... + a_n)
However, I do not have the quantities themselves, I only have their ...
- 175
7
votes
2
answers
436
views
Sorting with stochastic comparisions
Given a list where for every pair of elements (A, B) the probabilities P(A > B), P(A < B), and P(A = B) is known, how do you determine the most probable sorted permutation?
- 81