All Questions
46
questions
1
vote
0
answers
86
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,350
4
votes
3
answers
214
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
97
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
71
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,761
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,170
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,524
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:
$$...
- 117
0
votes
1
answer
985
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
64
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