# Questions tagged [probability-theory]

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

477 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

### Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
88 views

### How many random bits does this algorithm use on average?

Here, flip() is a function that returns 0 or 1 with equal probability. It can be proved ...
23 views

### Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing

I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition): Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = ...
1 vote
38 views

1 vote
66 views

### Generate uniform random vectors

Problem : Consider a random vector $v$ which is uniformly distributed over the sample space $S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$ . How to efficiently generate such random vector ? note :...
1 vote
120 views

### Distributing cards randomly given constraints

We want to distribute 3*n known cards among 3 players evenly given a set of constraints that prohibits some players from having certain suits. For example: We want to distribute 1H, 2H, 3S, 4S, 5D, 6D ...
93 views

102 views

### Rank in a Convex Combination

Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let $$Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\}$$ denote the number of elements in the ...
49 views

29 views

12 views

### Algorithmic Complexity of Enqueue and Dequeue of a Special Queue [duplicate]

The Canteen Queue Problem: There is a common canteen for $K$ hostels. Each hostel (co-ed) has some $N_1, N_2,...,N_K$ students. These students line up to pick up their trays in the common canteen, in ...
1 vote
73 views

### Most Likely Number of Winners - Dynamic Programming

You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Give a dynamic programming algorithm that returns the most ...
43 views

The following question is taken from the book titled "Probability models for Computer Science" written by Sheldon M. Ross. Question: A particle moves along n + 1 vertices that are situated ...
134 views

### Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...