All Questions
46
questions
1
vote
0
answers
87
views
Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?
Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ....
- 8,424
4
votes
3
answers
218
views
Proof for Particular Fair Shuffle Algorithm
I ran multiple simulations of the following function, and it seems to be fair shuffling, given that all permutations were roughly equal, but I don't understand why it works. It's just inserting at ...
- 41
0
votes
0
answers
48
views
Coin weighting with constraints
Consider the following $(d,k,n)$-coin weighting (with spring scale):
You possess an electronic scale, $n$ coins, and $d$ of them are magnetic. Moreover, you always need to weight at least $k$ coins at ...
- 183
1
vote
1
answer
92
views
A shuffling algorithm that limits the number of consecutive repetitions?
This question comes from Stack Overflow. I feel that we need more of a mathematical breakthrough, so I forward the question here.
I also found a similar problem that seems to be a special case of this ...
- 11
3
votes
1
answer
98
views
Expected Length of Maximum Decreasing Subsequences in Random Sequences
Given $ n $ distinct numbers that are randomly shuffled to form a sequence $ A = [a_1, a_2, \ldots, a_n] $, we select the largest number $ x_1 $ from the sequence. Subsequently, we pick the largest ...
- 1,231
1
vote
2
answers
73
views
When can a deck be shuffled by shuffling fixed subdecks?
Suppose I want to shuffle a deck of $n$ cards, but I have a problem -- for some reason, I am only able to shuffle at most $n-1$ cards at a time at some fixed indices. For example, if $n=5$, I could ...
- 685
1
vote
0
answers
32
views
Given $M$ biased coins, what's the probability of drawing $K$ heads? Can we compute it efficiently? [duplicate]
We have $M$ coins, with biases $p_1,\dots,p_M$. I draw all of them and count the total number of heads. What's the probability of observing $K$ heads?
I realize the solution can be formally written as ...
- 6,771
3
votes
2
answers
87
views
Dividing distinguishable cards into distinguishable hands where some hands cannot contain some cards
I am making a computer program to play cards, for this algorithm to work I need to deal cards out randomly.
However, I know that some people cannot have some cards due to the rules of the card game.
...
- 2,305
1
vote
0
answers
30
views
Can we find a proper $\phi$ so that maps each interval to its center?
For a compact interval $[0,1]$, we divide it into $N^{1/3}$ subintervals with length $N^{-1/3}$. Define a map $\phi: [0,1]\mapsto [0,1]$ maps each subintervals to its center.
For example, let $X\sim ...
- 1,520
0
votes
1
answer
99
views
What is the name of this variant of n choose k but with multiple subsets to pick?
$n$ choose $k$ can be seen as permuting a binary string with $k$ of the digits set to $1$, and $n - k$ of them to $0$. For example if the string is length $n=6$ and $k=3$, one permutation would be:
$$...
- 127
0
votes
1
answer
1k
views
Probability of getting 2 Consecutive heads in N throws.
We have to Find a Probability of Getting ${2}$ consecutive Heads in ${N}$ throws Given that $N^{th}$ throw will always be Head.
For Example:- N = 3,
Possible Conditions = HHH, HTH, THH, TTH = 4 ...
- 5
3
votes
1
answer
48
views
Random seat assignments probability/algorithms question
Suppose there are $M$ seats and $N \leq M/2$ people for those seats.
The seats are assigned as follows:
Each person generates uniformly a random permutation of the $M$ seats. When it is their turn ...
- 31
1
vote
0
answers
35
views
Approximate estimation of number of occurrences using hash functions
Let $h: U \to \{0, \dots, M-1\}$ be a universal hash function.
Let $C$ be a counter of size $M$, initially $C[i] = 0$ for $i \in \{0, \dots, M-1\}$
Define $\operatorname{update}(x): C[h(x)] = C[h(x)] +...
- 11
1
vote
0
answers
65
views
How to construct a set system with given set and pairwise intersection sizes
Consider a finite set $X$ and some subsets $X_i \subset X$, $i = 1,\dots,n$, with $\bigcup_i X_i = X$, of which one only knows the sizes $|X_i|$ and $|X_i \cap X_j|$.
How do I systematically ...
- 18.2k
0
votes
1
answer
46
views
Positive bit count of the $S(n):=\sum_{i=1}^{n} 2^{(i-1)}$ always $n$?
From a discussion on a stack about the programing, I got the following mathematical Conjectures:
Conjectures:
Let n,m be positive integer, $S(n)$ and $CountPosbit(m)$ be as follows.
$S(n):=\sum_{i=1}...
- 665
1
vote
1
answer
101
views
Closed form for Chu–Vandermonde identity-like summations
I have been trying to analyze a randomized algorithm I cooked up and have found the need to compute some moments of a random variable modeling an aspect of the algorithm but I am unsure if there is a ...
- 549
1
vote
0
answers
36
views
General equation for the number of combinations that connect upper part and lower part of grid
Given a square grid with either open or closed cells where open allows a path to be created across the cell. What would be the general equation that describes how many combinations create a path from ...
- 241
0
votes
1
answer
106
views
Efficiently modify the combined probability of many independent events when variable values change
Question:
Let $C_1$ and $C_2$ be two events that are independent and not mutually exclusive that occur with different probabilities $p_1$ and $p_2$.
For these two events, I understand that:
$$ P(C_1 \...
- 31
0
votes
0
answers
34
views
Expected size of a set with iterative probabilistic growth
We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches.
We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At ...
1
vote
0
answers
105
views
Does "expected entropy" make sense?
This question is inspired by Determining information in minimum trials (combinatorics problem). Here is the problem statement with some modifications
A student has to pass an exam, with $k$ ...
- 836
0
votes
0
answers
185
views
Greedy Algorithm on Knockout Tournaments: Proof of Correctness
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
- 11
1
vote
1
answer
63
views
Binary search on positive integer valued random variable
Let $X$ be a random variable taking values in $\{1,2,3,...\}$ and $\mathbb{E}(X)<+\infty$. $A$ has a realization of $X$. $B$ wants to guess what value does $A$ have and $B$ knows the distribution ...
- 351
1
vote
0
answers
40
views
Choosing my most preferred card from a set of n cards.
I have $n$ cards, however, I like only 1 card the most out of all the $n$ cards and that card is my favourite. I consider the cards one by one, giving each an integer score, where the higher the score ...
- 11
1
vote
0
answers
21
views
Minimum 1-D finite pavement to fit in varying-length K bricks
Suppose you have a set of $k$ bricks, each of varying sizes. we want to fit all these brings one by one on a straight pavement of length $N$. we know the sizes of each brick but we do not know
a) ...
1
vote
0
answers
57
views
What does the 8 stand for in the Cantor pairing function?
What does the "8" stand for in the Cantor pairing function (which assigns a natural number to each pair of natural numbers)?
Can I change it, or is it constant?
The other function for getting the ...
- 17
7
votes
1
answer
3k
views
Turning a Biased Coin into an Unbiased one Deterministically
Non-deterministic Exact Algorithm
There is a simple algorithm to turn a biased coin into a fair one:
Flip the coin twice.
Identify HT with H and TH with T.
Discard cases HH and TT.
This algorithm ...
- 583
0
votes
0
answers
37
views
Probabilistic selection of fruits against adversarial seller
Suppose a seller has $n$ fruits and you would like to buy $n/3$ of them. Now you know that $k$ of those fruits are rotten inside (but you do not know which $k$ are rotten while buying, but the seller ...
- 2,517
2
votes
1
answer
484
views
Beggar-my-neighbour possible games [closed]
How many Beggar-my-neighbour possible games are there?
There are 5 types of card: a, b, c, d, e.
In a bundle of 52 cards there are 4 cards of type a, 4 of type b, 4 of type c, 4 of type d and 36 of ...
- 123
3
votes
2
answers
254
views
What is probability that a line joining two randomly selected coordinates from set form an angle $45°$ with one of axes?
What is probability that a line joining two randomly selected coordinates from a set form an angle $45°$ with one of the axes?
For example, if we have set of coordinates $$\{(1, 2), (1, 3), (3, 3), ...
- 365
5
votes
3
answers
2k
views
Calculating a random "blob" in a 10 x 10 grid
The problem:
You have a 10 x 10 grid where each cell can be either occupied (1) or unoccupied (0).
All occupied cells in the grid are part of a single "blob": a single shape defined by a set of ...
- 163
2
votes
2
answers
154
views
Expected value of circles in case of Christmas gifting in a class
Let's suppose there is a class of n children, where everyone gives a present to somebody, and it is possible to give a gift to yourself. During the event, the first child stands up, and passes his or ...
- 23
1
vote
1
answer
65
views
Expected cost of algorithm based on hypergeometrical distribution
I am having an algorithm which cost I want to determine, but I am having trouble to do so. In order to do so, I tried to break it down to a well known scenario, to be able to communicate the issue:
...
- 1,131
1
vote
0
answers
185
views
Determine Huffman Tree Depth Using any combinactory ways?
I see this link for determining depth (height) of Huffman tree, but not useful for me.
My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
0
votes
1
answer
67
views
How to generate all possible SEC matrices for $n$-bit
I want to know if there is an algorithm with which man can generate all possible forms of single error correction matrices for n bits of data, both linear and non-linear. For example all possible $32$-...
14
votes
4
answers
3k
views
Minesweeper probability
I ran into the situation pictured in the minesweeper game below. Note that the picture is only a small section of the entire board.
Note: The bottom right $1$ is the bottom right corner tile of the ...
- 151
0
votes
0
answers
87
views
Minimum movements to arrange fruits in boxes
I have $3$ boxes - $B_1, B_2, B_3$. Each box initially contains a mixture of $3$ different kind of fruits say - Apple, Orange, Mango. Our goal is to arrange the fruits in the boxes in such a manner ...
- 101
4
votes
1
answer
2k
views
Expected value when die is rolled $N$ times
Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
- 235
5
votes
0
answers
131
views
Analysis of sorting Algorithm with probably wrong comparator?
It is an interesting question from an Interview, I failed it.
An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ （random order）.
We have a comparator $C$, but it has a probability $p$ to ...
- 61
0
votes
1
answer
450
views
Randomized algorithm for coloring with monochromatic copies
Consider the complete graph $K_n$. Give a randomized algorithm for finding a coloring by two colors with at most $\binom{n}{4}2^{-5}$ monochromatic copies of $K_4$ that runs in expected time ...
- 2,673
-1
votes
1
answer
56
views
Probability of 1 at both end of string
Given a string S having N characters long and consists of only 1s and 0s.
Now given an integer K, let us pick two indexes i and j at random between 1 and N, both inclusive.
What's the probability ...
- 311
1
vote
2
answers
739
views
Game of cards and GCD
Alice and Bob play the game. The rules are as follows:
Initially, there are n cards on the table, each card has a positive integer written on it.
At the beginning Alice writes down the number 0 on ...
- 11
2
votes
1
answer
128
views
Expected Value of this function
Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where
...
- 1,056
6
votes
2
answers
164
views
Puzzle about voting
I came across about this puzzle which I'm not sure how to go about.
Suppose there are $L$ leaders and $F$ followers, with $1 < L<<F$. A leader makes a binary decision, $0$ or $1$ with same ...
- 1,511
0
votes
1
answer
613
views
probability of sum of a given set of whole numbers being greater than a certain number
There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a ...
- 275
2
votes
1
answer
216
views
Bounding the power of expected value of functions of a random variable.
I am interested in a problem and I do not know where to start looking for possible similar setting. If anyone has a direction to suggest, it would be greatly appreciated.
Consider a (finite) set $\...
- 121
9
votes
3
answers
9k
views
How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?
I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice.
I've spent quite ...
- 557