# Questions tagged [probability-theory]

Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

341 questions
Filter by
Sorted by
Tagged with
62 views

### Sampling numbers from a weighted set that sum to constant value

So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
68 views

### Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...
32 views

### Complexity/Hardness of a generalization of an Inclusion/Exclusion problem

I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#...
44 views

### How to generate a random number in a given range with uniform probability [closed]

I have used programming languages which generate a random number in a given range. Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
94 views

### Proof of an Infinite Binary Sequence

I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}* such that ww is a prefix of S. I need to prove that if ...
32 views

### Probability lower bound on a double cycle on two vertices in random cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
55 views

### Probability of a double cycle in cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
38 views

### Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...
30 views

### Expectation of $u'^t v$ = $u^t v$

I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d$. I need to ...
38 views

I'm reading this article. In particular I'm having some trouble trying to replicate the results of the first image in that article. For x=9, the graph says that the probability is 0.20 aprox. But ...
23 views

### Expectation of $\langle s,x \rangle^2$

I'm studying dimensionality reduction (SVD in particular), and I saw the following question: Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ , where $s$ is a $d$-...
106 views

### probability of collision

my data's range is from 1 to 9 and I have two subsets of integers from this range. the hash function takes each of this subsets and calculate product of these three integers and maps this set to the ...
9 views

46 views

This is a question about Markov Models. Let's say we have the following situation Let's say that we want to find the probability that $2$ rainy days follow a nice day. You'd simply have $0.25 \cdot ... 1answer 61 views ### Avoiding correlated values and reduced collision resistance in multiple hash states I need to design a hash function that fits this criteria: Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system) Produces an n-bit hash digest, ... 1answer 23 views ### Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1 This is an exam question from my algorithms and data structures course. You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n ... 2answers 57 views ### Why does the distribution of pseudorandom numbers change when operating like this? We were introduced to the standard C rand() function, and how to use it. At some point during the class we were asked how to roll a die. The simple answer was to ... 0answers 16 views ### Presentation topic for computational solutions to problems involving probability I'm looking for interesting applications of computing science for finding the probability of otherwise difficult problems. This is for an undergraduate level presentation in a probability course of ... 1answer 564 views ### Applying a Chernoff bound with Only an Upper Bound of the Expectation First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The ... 1answer 329 views ### ALOHA - Throughput and probabilities I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25. 1) What is the throughput and what is the probability that a user will ... 1answer 1k views ### Reservoir sampling algorithm probability I'm reading about the reservoir sampling technique called Algorithm R. The idea is we can take a sample of size$n$from a population of size$N$even when$N\$ is unknown/too expensive to retrieve in ...
I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states: $$E[{n_i^2}] = 2 - \frac{1}{n}$$ To prove, CLRS: Random variable denoting number of elements ...