Mixing
Compute closed form for probability of some event
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let $(d, m) in mathbbN^2$, and let $X_1, dots, X_m$ be drawn identically uniformly and independently over $[d]$. For $(i,j,k) in [d]^3$ we define the event $S_ijk$ in the following way
$$S_ijk = left sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = j right = 1 text and sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = k right = 1 right$$
I am interesting in finding a closed form expression for $mathbfP(S_ijk)$, the probability of that event.
Please correct me if I am wrong, but here are a few elements I gathered so far:
- For $t in [2 dots m]$ the $(X_t-1, X_t)$ are uniformly distributed over $[d] times [d]$, although (as @did pointed out) they are not independent.
- The value of $mathbfP(S_ijk)$ should be independent of $i$.
- It seems reasonable to split into two cases depending on whether $j = k$ or not.
probability combinatorics probability-theory closed-form
edited Jul 25 at 18:08
E-A
1,8051312
asked Jul 25 at 12:03
ippiki-ookami
303216
add a comment |Â
up vote
1
down vote
favorite
Let $(d, m) in mathbbN^2$, and let $X_1, dots, X_m$ be drawn identically uniformly and independently over $[d]$. For $(i,j,k) in [d]^3$ we define the event $S_ijk$ in the following way
$$S_ijk = left sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = j right = 1 text and sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = k right = 1 right$$
I am interesting in finding a closed form expression for $mathbfP(S_ijk)$, the probability of that event.
Please correct me if I am wrong, but here are a few elements I gathered so far:
- For $t in [2 dots m]$ the $(X_t-1, X_t)$ are uniformly distributed over $[d] times [d]$, although (as @did pointed out) they are not independent.
- The value of $mathbfP(S_ijk)$ should be independent of $i$.
- It seems reasonable to split into two cases depending on whether $j = k$ or not.
probability combinatorics probability-theory closed-form
edited Jul 25 at 18:08
E-A
1,8051312
asked Jul 25 at 12:03
ippiki-ookami
303216
1
When $j=k$, you seem to be assuming that the events $$S_ij^t = left X_t-1 = i,, X_t = j right$$ are independent, for $(i,j)$ fixed, when $t$ varies. They are not.
– Did
Jul 25 at 12:14
You are right, I mistakenly assumed their independence. Let me fix the question.
– ippiki-ookami
Jul 25 at 12:24
2
This fundamentally seems like a combinatorics question (This is akin to "How many 10 digit numbers exist that have one "11" and one "12" in it?); if you wanted those sums to equal 0 as opposed to 1, I can see a dynamic programming solution (i.e. a recursive solution (still not closed form)), not sure if that helps though.
– E-A
Jul 25 at 17:47
I agree with your comment (although one can argue that when dealing with finite support, many probability problems amount to combinatoric questions). The event I am interested in has the sums equal to one, and I am not so much interested in programmatic solutions rather analytical ones.
– ippiki-ookami
Aug 5 at 6:16
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $(d, m) in mathbbN^2$, and let $X_1, dots, X_m$ be drawn identically uniformly and independently over $[d]$. For $(i,j,k) in [d]^3$ we define the event $S_ijk$ in the following way
$$S_ijk = left sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = j right = 1 text and sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = k right = 1 right$$
I am interesting in finding a closed form expression for $mathbfP(S_ijk)$, the probability of that event.
Please correct me if I am wrong, but here are a few elements I gathered so far:
- For $t in [2 dots m]$ the $(X_t-1, X_t)$ are uniformly distributed over $[d] times [d]$, although (as @did pointed out) they are not independent.
- The value of $mathbfP(S_ijk)$ should be independent of $i$.
- It seems reasonable to split into two cases depending on whether $j = k$ or not.
probability combinatorics probability-theory closed-form
edited Jul 25 at 18:08
E-A
1,8051312
asked Jul 25 at 12:03
ippiki-ookami
303216
Let $(d, m) in mathbbN^2$, and let $X_1, dots, X_m$ be drawn identically uniformly and independently over $[d]$. For $(i,j,k) in [d]^3$ we define the event $S_ijk$ in the following way
$$S_ijk = left sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = j right = 1 text and sum_t = 2^m boldsymbol1left X_t-1 = i right cdot boldsymbol1left X_t = k right = 1 right$$
I am interesting in finding a closed form expression for $mathbfP(S_ijk)$, the probability of that event.
Please correct me if I am wrong, but here are a few elements I gathered so far:
- For $t in [2 dots m]$ the $(X_t-1, X_t)$ are uniformly distributed over $[d] times [d]$, although (as @did pointed out) they are not independent.
- The value of $mathbfP(S_ijk)$ should be independent of $i$.
- It seems reasonable to split into two cases depending on whether $j = k$ or not.
probability combinatorics probability-theory closed-form
edited Jul 25 at 18:08
E-A
1,8051312
asked Jul 25 at 12:03
ippiki-ookami
303216
edited Jul 25 at 18:08
E-A
1,8051312
edited Jul 25 at 18:08
E-A
1,8051312
edited Jul 25 at 18:08
E-A
1,8051312
1,8051312
asked Jul 25 at 12:03
ippiki-ookami
303216
asked Jul 25 at 12:03
ippiki-ookami
303216
asked Jul 25 at 12:03
ippiki-ookami
303216
303216
1
When $j=k$, you seem to be assuming that the events $$S_ij^t = left X_t-1 = i,, X_t = j right$$ are independent, for $(i,j)$ fixed, when $t$ varies. They are not.
– Did
Jul 25 at 12:14
You are right, I mistakenly assumed their independence. Let me fix the question.
– ippiki-ookami
Jul 25 at 12:24
2
This fundamentally seems like a combinatorics question (This is akin to "How many 10 digit numbers exist that have one "11" and one "12" in it?); if you wanted those sums to equal 0 as opposed to 1, I can see a dynamic programming solution (i.e. a recursive solution (still not closed form)), not sure if that helps though.
– E-A
Jul 25 at 17:47
I agree with your comment (although one can argue that when dealing with finite support, many probability problems amount to combinatoric questions). The event I am interested in has the sums equal to one, and I am not so much interested in programmatic solutions rather analytical ones.
– ippiki-ookami
Aug 5 at 6:16
add a comment |Â
1
When $j=k$, you seem to be assuming that the events $$S_ij^t = left X_t-1 = i,, X_t = j right$$ are independent, for $(i,j)$ fixed, when $t$ varies. They are not.
– Did
Jul 25 at 12:14
You are right, I mistakenly assumed their independence. Let me fix the question.
– ippiki-ookami
Jul 25 at 12:24
2
This fundamentally seems like a combinatorics question (This is akin to "How many 10 digit numbers exist that have one "11" and one "12" in it?); if you wanted those sums to equal 0 as opposed to 1, I can see a dynamic programming solution (i.e. a recursive solution (still not closed form)), not sure if that helps though.
– E-A
Jul 25 at 17:47
I agree with your comment (although one can argue that when dealing with finite support, many probability problems amount to combinatoric questions). The event I am interested in has the sums equal to one, and I am not so much interested in programmatic solutions rather analytical ones.
– ippiki-ookami
Aug 5 at 6:16
1
1
When $j=k$, you seem to be assuming that the events $$S_ij^t = left X_t-1 = i,, X_t = j right$$ are independent, for $(i,j)$ fixed, when $t$ varies. They are not.
– Did
Jul 25 at 12:14
When $j=k$, you seem to be assuming that the events $$S_ij^t = left X_t-1 = i,, X_t = j right$$ are independent, for $(i,j)$ fixed, when $t$ varies. They are not.
– Did
Jul 25 at 12:14
You are right, I mistakenly assumed their independence. Let me fix the question.
– ippiki-ookami
Jul 25 at 12:24
You are right, I mistakenly assumed their independence. Let me fix the question.
– ippiki-ookami
Jul 25 at 12:24
2
2
This fundamentally seems like a combinatorics question (This is akin to "How many 10 digit numbers exist that have one "11" and one "12" in it?); if you wanted those sums to equal 0 as opposed to 1, I can see a dynamic programming solution (i.e. a recursive solution (still not closed form)), not sure if that helps though.
– E-A
Jul 25 at 17:47
This fundamentally seems like a combinatorics question (This is akin to "How many 10 digit numbers exist that have one "11" and one "12" in it?); if you wanted those sums to equal 0 as opposed to 1, I can see a dynamic programming solution (i.e. a recursive solution (still not closed form)), not sure if that helps though.
– E-A
Jul 25 at 17:47
I agree with your comment (although one can argue that when dealing with finite support, many probability problems amount to combinatoric questions). The event I am interested in has the sums equal to one, and I am not so much interested in programmatic solutions rather analytical ones.
– ippiki-ookami
Aug 5 at 6:16
I agree with your comment (although one can argue that when dealing with finite support, many probability problems amount to combinatoric questions). The event I am interested in has the sums equal to one, and I am not so much interested in programmatic solutions rather analytical ones.
– ippiki-ookami
Aug 5 at 6:16
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862362%2fcompute-closed-form-for-probability-of-some-event%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
When $j=k$, you seem to be assuming that the events $$S_ij^t = left X_t-1 = i,, X_t = j right$$ are independent, for $(i,j)$ fixed, when $t$ varies. They are not.
– Did
Jul 25 at 12:14
You are right, I mistakenly assumed their independence. Let me fix the question.
– ippiki-ookami
Jul 25 at 12:24
2
This fundamentally seems like a combinatorics question (This is akin to "How many 10 digit numbers exist that have one "11" and one "12" in it?); if you wanted those sums to equal 0 as opposed to 1, I can see a dynamic programming solution (i.e. a recursive solution (still not closed form)), not sure if that helps though.
– E-A
Jul 25 at 17:47
I agree with your comment (although one can argue that when dealing with finite support, many probability problems amount to combinatoric questions). The event I am interested in has the sums equal to one, and I am not so much interested in programmatic solutions rather analytical ones.
– ippiki-ookami
Aug 5 at 6:16